mayoko’s diary

プロコンとかいろいろ。

TypeScript を使ってオセロを実装してみた

オセロです。
index.html, style.css, main.ts を同じフォルダに入れ, main.ts をコンパイルして main.js を作って, index.html をブラウザで開くと一人二役のオセロで遊ぶことが出来ます。
github.com

追記：こちらから遊べます
オセロ

通信対戦までやりたいので, まだ途中ですがある程度まとまったのでとりあえず公開です。
通信対戦は typing war みたいなのかっこいいので真似出来ればしたいです。
Typing War | traP

微妙にオブジェクト指向を意識しました。
クラス間の関係みたいのをメモした図はこちらです(オブジェクト指向の考えかたわからん)。
f:id:mayokoex:20180617100712j:plain

途中でめんどくさくなって if (this.board.state.board[i][j].get() === Cell.white) とか書いてあるのは御愛嬌です。
本当は Board クラスに get(i, j) っていうのを入れておいたほうが良さそうです。

今一番気になってるのは, createElement の型をどう書くのってところです(無理なのかな？)。
this.elem = createElement("div");
とか書くのですが, クラスのメンバとして elem を入れてないとダメなのでその時に elem: type みたいな感じで書かないとダメですが, type が分からないので人生終了です。

一時変数だったら const elem = createElement("div") とか書けば賢い visual studio code 君がインテリセンスを発動してくれるのですが, クラスのメンバだとダメです。

追記：しょラーさんに教えていただきました。ありがとうございます！

AGC016 B: Colorful Hats

面白かったので考察をメモしておこうかなと思いました。
B - Colorful Hats

考察

こういう問題は必要十分条件を考えるのが定石だろうと思います。
とりあえず考察として, 「数字は x か x+1 に絞られる」というのはちょっと考えてわかりましたが, それ以外は特に検討がつかないのでとりあえず実験してみます。

N <= 5 程度で可能なリスト, 不可能なリストを適当にピックアップしました。
実験してる間に気づいた一般的なことは, 「長さ N に対して, 全員が x 種類と主張する場合には, x <= N/2 または x = N-1 の時は必ず OK」だけでした。

「単純な例から初めて決まった動きをさせると解が構成できる」みたいな方法もできるかなと思いました。
今回の場合は, それぞれの人の帽子の色を始めに固定しておいて, そこから一人ずつ帽子の色を変えていく, みたいな方針です。
一番基本的な形とその時に感じた, 「それぞれの人の帽子がバラバラ」というのから初めて色を変えていきます。
以下は左が帽子の色で, 右がその時のそれぞれの人々の主張です。

  • ABCDE: 44444
  • BCDAA: 33344
  • BCAAA: 22333
  • BAAAA: 12222
  • BCBAA: 32333
  • ...

この実験をやって突然「帽子がユニークな人は x と主張してユニークでない人は x+1 と主張する」ことに気づきました。
全体で x 種類の帽子があり, かつ帽子がユニークな人が y 種類いる場合, (y <= x)

  • (1, 2, 3, ..., y), (y+1, y+2, ..., x), (y+1, y+2, ..., x), (...)

というように帽子がかぶられればよく, このような解が生成できる必要十分条件は, y + (x-y) * 2 <= N です。

とりあえずこれで実装して実は全てが x の場合でもうまくいかないかなーと思いましたが, そううまくは行かなかったので, 場合分けしてホイっと解きました。

感想

考察書いてみれば思考過程振り返れるかなーと思ったけど結局一番大事な考察に突然気づいてやがるのでなんかなぁ。
「どうやって思いつくか」が大事だと思うけど実験してたら突然思いついた感がある

javascript で 2048 を実装してみた

何をやったのか

javascript 初心者が javascript で 2048 を実装した話です。

javascript で初めてアプリっぽいものを作ったのでやったことを残しておこうかなーと思って書いています。
作ったものはこちらです。
github.com

  • index.html, main.js, style.css を同じフォルダに置いて index.html をブラウザで開くと遊べます。
  • 「AUTO」を押すと AI が起動して勝手に動かしてくれます。「AUTO」を押すとボタンが「STOP」に変わりますが, それを押すと AI が止まります。

追記：遊べるようにしました
https://mayoko.github.io/myGame/
AI はなんとモンテカルロをやっているのでかなり重いです

クラス構成

javascript は private とかなくてガバガバですが 一応クラスがあります(altjs とか使うとそういうのもちゃんとするんですかね？)。
作法的に private method を作りたいときは 関数名の最初に "_" を付けるっぽいです。

で, クラス構成ですが, 以下のようになっています。

  • Game クラス
    • 以下で述べる State クラス, Animation クラスをまとめて動かします
  • State クラス
    • ゲームの論理部分を担当するクラスです(上に動かしたらセルがどう動くーとか)(セルというのは「2」とか「128」とか書いてある一マスのことです)
    • 本当は分けて書いた方が良いと思うのですが, 面倒なのでアニメーションに必要な情報もここで計算しています
  • Animation クラス
    • 下で述べる Cell クラスを用いて, セルが動くとかセルが表れるといった Animation を制御します
  • Cell クラス
    • セル単体のアニメーションをサポートするクラスです
  • GameAI クラス
  • State を受け取って, どういう風に動けば良さそうかを考えるクラスです

以下で各クラスの説明をしていきます

State クラス

主な役割は, 「上/右/下/左に動かしたときに, 各セルがどこに行くか」を計算することです。
これは calcNextState というメソッドて計算しているのですが, まぁこの記事を見ている人なら簡単に実装できると思います。
といいつつ定数倍遅くなりつつ楽に実装できる方針をとったのでちょっと説明します。

  • まず, 上に動かしたときにどういう風に動くかを計算できるようにしましょう。
    • これは, 上の行から順番に上に動かす, というような方針を取れば実装できます。
  • 上に動いた場合さえ計算できれば, 例えば右に動いた場合の計算は, 「board を 3 回時計回りする -> 上に動かす -> board を 1 回時計回りする」というように実装することによって, 上に動かすのを利用して実現することができます。

Animation クラス, Cell クラス

これが一番大変でした。
アニメーションは結局要するに,

  • アニメーション開始からどれくらい時間たったかを計算することによって, 進捗率を求める
  • 進捗率に応じて, 位置なり角度なりを制御する
  • 進捗率が 100% 出ないのであれば, setTimeout なり requestAnimationFrame なりを呼び出して続きをやらせる

ということをやればいいです。

コードにして書くと以下の通りです(適当に書いたので間違ってるかもしれません。また, const に値を入れていないので当然コピペしても動きません)。

// アニメーション開始時間
let start = null;
// アニメーションにかける時間[ms]
const time = 1000;
// 例えば fromX から toX に動かすアニメーションを作りたい
const fromX, toX;
// 動かす対象
const elem;

// アニメーション更新関数
const update = () => {
    if (!start) {
        start = new Date();
    }
    // 進捗率
    let progress = (new Date() - start) / time;
    progress = Math.min(1, progress);
    const x = fromX + (toX - fromX) * progress;
    // 位置指定
    elem.style.left = `${x}px`;
    // まだ進捗率 100% でないなら続き
    if (progress < 1) {
        requestAnimationFrame(update);
    }
};
// アニメーション開始
requestAnimationFrame(update);

これだけ聞くとかなり簡単に聞こえるのですが, 個人的にややこしかったのは, setTimeout なり requestAnimationFrame は, while 文みたいに「一回実行したらアニメーションが終わるまで続きを実行しないで待つ」みたいな関数ではないということです。

これのどこに注意が必要なのかというと, 例えば今回の場合, 4 と 4 が合体して 8 になる, というようなアニメーションをする場合,

  • 2 つの 4 が移動するアニメーションをやる
  • アニメーションが終わったのを確認してから合体して消える片方の 4 を消す
  • 4 を 8 に変化させるアニメーションを入れる

というようにアニメーションを進行させていきたいわけですが, 

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 合体して消える要素は削除
removeChild(elem);

というように書いてしまうと, アニメーションをしている間に elem 要素が消えてしまうので, update 関数から「そんな要素ねぇぞオラァ」と怒られてしまいます。

また, 

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 2 つ目のアニメーション更新関数定義
const update2 = () => {...};
// アニメーション2開始
requestAnimationFrame(update2);

という風に書いてしまうと, 1 つ目のアニメーションが終わる前に 2 つ目のアニメーションが始まるので「オイオイ待ってくれよ」ということになります。

ただ逆に, アニメーションを同時に動かしたいときは, for 文で requestAnimationFrame を発火させておくだけでいいので楽っちゃ楽かもしれないです。
2048 の場合, 複数セルを同時に動かさなければならないことが多々あるので, for 文 requestAnimationFrame 同時発火手法はイケそうな感じがしましたが, 今回はそのような実装方針にしていません(後で説明します)。

で, じゃあどうすれば良いかということなんですが, 主に 3 つ工夫(?) しました。

  • アニメーションされる要素を用いずに, どういうアニメーションがされるのかを前計算しておく
  • アニメーションを連続させるときは, 1 つ目のアニメーションが終了したタイミングで次のアニメーションが発火するように setTimeout でタイミングを測る(これもっとうまくできる方法あったら知りたいです。知っている方いたらお知らせください。)
  • 進捗ごとにどのように要素が動くのか定義する関数(progress を引数にとって要素を動かす関数) と アニメーション更新関数(update 関数) を分ける

それぞれについて説明していくのですが, その前に Animation クラス, Cell クラスがどのようなクラスなのかを説明しておきます。
2048 のアニメーションですが, 大きく分けると「移動」, 「出現」に分けられて, 「出現」はさらに 2 つに分けられます。

  • ランダムにセルが出現するときにあるような, 何もないところからだんだん膨らんで現れるやつ
  • 2 と 2 が合体して 4 が表れるときにあるような, セルが普段の高さ, 幅よりもちょっと膨らんでからもとに戻るやつ
  • Cell クラス
    • アニメーションの進捗率を受け取ると, 「移動」の場合は今セルがどこにいるべきか, 「出現」の場合は今セルがどれくらいの大きさか, を計算してくれる
  • Animation クラス
    • Cell クラスの集合を保持しておく
    • アニメーションするときには, 進捗率を管理しながら, 「移動」, 「出現」を各 Cell にやらせる
    • アニメーション更新関数(update) を呼び出すのはここであって Cell クラスの中でではない
前計算

これはまぁわかりやすいですね。
どういうアニメーションにするかあらかじめ計算しておくことによって, コードが読みやすくなります。
javascript はオブジェクトを参照で受け取るっぽいので, Cell のまま管理しようとすると想定外の Cell がいつの間にか消えていたりしてややこしいです。

発火タイミングを調整

1 個目のアニメーションに 100ms 使うとかわかっている場合には, 2 個目のアニメーションは 1 個目のアニメーションが発火した 110ms 後とかに発火すると良さげですね, というようなことです。setTimeout は呼び出す関数が次にいつ呼び出されるかを指定できるので, 最初の呼び出しだけ setTimout を使って後は requestAnimationFrame を使う, みたいなことをやりました。

javascript のライブラリで anime.js というアニメーションをやってくれるすごいやつがいるっぽいです。
anime.js で連続したアニメーションをやりたい場合は, 1 個目が発火した後何秒後に次のアニメーションを発火させるか, みたいのを指定して連続アニメーションを実現しているようです。
今回のやり方も同じように発火させるタイミングを時間で指定しているので, 結局やったことは anime.js 手法を自分で書いた感じになったのでしょうか(詳しく知らないので想像でしかないですが)。

animejs.com

Animation クラスと Cell クラスで役割を分割

今回は, Cell クラスは「進捗率を受け取ると, それに合わせて二次元位置であったりセルの大きさを調整する」ということを行い, Animation 関数の中でアニメーション更新関数(update)を呼び出すようにしました。
こっちの実装方針の方が, アニメーションが終了したときの処理を柔軟に書きやすいという利点があるような気がします。

例えば, セルの「移動」, 「出現」のアニメーションが終わるまでは, 別の矢印キーが押されても反応しないようにするために, Animation クラスには finish という bool 値があるのですが, これは update 関数内の進捗率が 100% になったら finish を true にする, というような処理を行うことによって簡単にできます。
一方で, Cell の中で update 関数を書くような方式にした場合, 全ての Cell のアニメーションが終わってから finish を true にする, というような処理を書くのが面倒な気がします。
(一つの方法として, ある Cell にのみ finish を参照渡しして, その Cell のアニメーションが終わったら finish = true にする, という方法があると思いますが, あんまりきれいじゃない)

なんか冷静に考えると別にどっちでもいいような気がしてきました, はい。

ACM-ICPC 2017 アジア予選に参加しました

参加しました。しばらく競プロはお別れな気がする。

前日まで

前回のDCCCでなんか言っていたが特に達成していない(9/25 AC)

せっかくなので JAXA エクスカーションに行った


なんかあるのかと思ったけど普通の見学だったのでうん, まぁという感じ
せっかくなので風船飛行機を買った(324 円)
たまに飛行機を飛ばして害悪行為をしておりましたすみません

割とグダグダしながら会場入り

会場も割とグダグダだったけどホイホイしながら練習
まぁここらへんは逆に企業間イベントが頑張ってるんだよなぁとか思った
ddccとかこどふぇすとかのスタッフさんすごい

  • 英字キーボードヤバすぎて vim を使う気を起させなかった
  • gedit で行こうかなぁとか思ったけど最後何気なく使った eclipse が案外優秀だったので eclipse で行くことに

ごはんを目の前にひたすら待たされる作業
早く食べたかったよー

ホテル
OpenGL の勉強しようかと思ったけどそういえば環境は my PC にはなかったのでスプラをやる
丁度ガチアサリをやっていたのでやったけどなかなか難しいね


C帯で 29 キルするな

本番

8:00 頃に起床 AC
風船飛行機をしぼませるストローをなくして邪魔だったのでストローを買った

本番の動き
僕がログインしてる間にどりきゃすに A 問題, 住建に B 問題を読んでもらった
A は dp らしいので書き書き
B は全探索らしいので書き書き
C はどりきゃすが式を生成していたので書き書き
I は住建が解いてくれたので一部書き書き
G はなんか知らんけど解かれてた
ここまでで 2 時間半で, ここからの 2 時間半は,

  • 僕とどりきゃすが E 問題で適当な貪欲をして意味不明をする
  • 住建が F 問題を解こうとしてなんかダメ

で終了。コンテスト時間 3 時間で良かったよ

11 位でした。10 位からなんかいい感じだったので惜しい

解説
ただでさえわからない競プロ解説を英語でやるとどうなるか…

閉会式

一位114514知ってた
sigmaさんが負けたの辛いみたいなツイートしてたけどそれでも続けてるのすごいなぁとか思った

懇親会

思ったより就活イベントっぽかった
たまに就活イベントとか行ってるんですけど、そこであった人が割りといてビックリ
いい生活とレトリバから景品もらえたのでハッピー
バランスボールはとりあえず家に一週間くらいおいて使ってみたいです
あとは知り合いも新しい知り合いも含めて色んな人と話せたので良かったです

mayoko と競プロ お別れの時

実際のところ, 国内予選で終わりかなぁと思っていたんですが, なぜかアジア予選に通ってしまったのでここまで伸びてしまいました。
競プロは楽しいんですけど, 解けないと面白くないのでちゃんと練習したいんですが, 最近は別の娯楽(switch とかね)をやってるし研究室とか別のことが忙しいので, 全然解けなくて面白くないを錬成しているのでまた時間が取れたら戻ってきます。

戻って来れるのかは分かりませんが・・・・・・・・・・・

まとめ

SHIROBAKO はいいぞ

ISUCON 7 final に参加しました

ISUCON 7 final になぞなぞチームで参加しました。
意外に座るだけじゃなかったので良かったです。

チームリーダー(?) が詳しいことを書いている
brookbach.com

競技前



やったこと
  • 二人が構成を頑張っている間に app.py とか game.py とか見て遅そうなところを見つける
    • 僕は完全にのんびり読んでたんですけど, 二人はプロファイル作るのに苦戦していた模様
  • 1 秒先までの未来を見るみたいのが calc_status にあったけど遅いやろって思ってたら実際に遅いらしいので適当に実装
    • test_game.py と言うのがあったので非常にありがたかった
    • test_game.py のテストは通るけどベンチは通らないみたいな感じだったので相談しながら実装して点数上げる(イエーイ)
  • なんかこれが一番やった感あるやつで, あとはいろいろ試したけどベンチ通らなくて悲しいというやつだった
    • 点数上がりそうだなーと思っていたのは, calc_state まわりで前のデータから更新された新しいところだけとってくるってことだけど無理でした
      • 今更ながら, これと Redis に乗り換えるの同時進行でやるのは難しかったのではとか思った
      • データベースは実質グローバル変数だからちょっと変えようと思うだけでもめっちゃコードいじらないといけなくて難しい
へーとか思ったこと

python は型がなくてクソと思ってたけど一応 total_milli_isu : int = 0とかで宣言出来たりするらしい(関数の引数の定義でも似たようなことが出来る)(少し見直した)

  • 3.6 からだった(自分の PC に入っていたのが 3.5 のため)
終わり
  • 去年の反省を生かさずまた大量に食べてしまう
    • おいしいから仕方ないね
    • ケーキ久しぶりに食べた




(解説：僕は web サービスとかサーバーとか全然知らないのに ISUCON に出ている)

模擬地区予選に参加しました

shuriken チーム(僕, 住建, どりきゃす)で参加しました。
jag2017autumn.contest.atcoder.jp

国内予選が初手で僕が早解きする流れだったのでその流れを踏襲

コンテスト

A 問題を見たんだけど, イマイチサンプルの意味がわからず
他の二人が B, C あたりを相談してて話しかけづらい雰囲気だったんだけどわからないのはマズイので聞いてみる->解決
かなりデオクレティアヌス帝だけどまぁなんとか AC

B 問題を住建が読んでたので任せる(エディタ慣れてないのも合わせてかなり時間食ってしまったので僕に実装投げてくれたほうが良かったかも)
その間にどりきゃすと C 問題を見る
ふーん…とか思って 5 分 10 分考えたらわかったので次に行く
E, H が問題文短くてすぐ読めたけど解法はわからず～とか言ってる
その後 F を見て, どうせ全部通れるやろｗとか思いながら解法を考えたらなんか浮かぶ
実装めんどくせーとか言いながらもまぁなんとなく実装方針は立つ

B で割と詰まってたのでコーディング変わって C, F を解きにかかる(なんか B はエディタが保存してなかったのが原因だったらしい)

C はまぁあっさりAC
F は途中まで書いたところで出力見たらバグってて, 住建が B 変わりたいとのことだったので印刷して交代
どりきゃすとコードにらめっこして間違い見つける
B 問題 AC

その後 1 WA のち F 問題 AC
僕が F 書いてる間に G 解けるやろと後ろで相談していたらしく, G 実装してあっさり AC

順位表見て, E と H がねらい目だよねという話をしつつもよくわからないので暇
適当にみんなでバラバラに考え始めるけど結局 E 問題を僕とどりきゃすで, H 問題を住建が考える形になった
最終的に解けたのは H なので住建すごい(解説聞いてえぇ…と思ってしまったけどそういうのも出るんですね)

E 問題は 3 回くらい印刷してどりきゃすとにらめっこしてたけど結局解けなくて悲しい
後で結果見たらスターグラフの場合で落ちているらしい

解説

tokoharu さんが全体的に難しい問題を解説してたんだけど, 知らんってのが多くてあんまりわからなかった(すみません)
今回は全体的に短い行数で書けるのが多かったらしい

解散後

計数の人々がめっちゃいたので, 住建と後 4 年メンバーでご飯を食べに行く
計数 3 年生が競プロ部作ってるとかいろいろあるらしくて計数が競プロ学部になってる感ある(頑張ってくれ)

感想

つくばでも頑張ります

DDCC 2017 に参加しました

参加しました。久しぶりに競技プログラミング系イベントに出た感じがしますが楽しかったです。

前日

やざてんさんに誘われて飲み会に行ってきました。


コンテスト前

10:00 くらいに行けばよかったので 30 分くらい前に着けば良いかなぁと思っていたら 8:30 とか 9:00 とかに会場入りしてる人がいてビビった


後最近僕がファンになっているチノちゃん競プロなりきり bot の中の人に会えました。チノちゃんかわいい。
他にも昔なじみの知り合いとか Indeed ツアーで知り合った人とか前日の飲み会で知り合った人とか次々と会いました。

コンテスト中

A, B の 2 完でした。
20 分程度で 2 問解いたので残り 1 時間 40 分座っているだけでした。

山本一成さん, 西尾さん, chokudai さん対談

面白い話が聞けました。
印象に残ったことを書いていく(575)

  • 競技プログラミング AI がいつ超えるのか？
    • 今も論文が出ているらしい
      • 入力, 出力の関係を見てそれに合致するアルゴリズムをひたすら提出するらしい
      • AtCoder レート 1000 程度は出るとか
    • 競技プログラミングはプログラミングの中ではある意味単純(入力, 出力がきれいにフォーマットされている)ので問題文解釈して論理的にそれに答える等価なコードを書いていけば案外早く超えられるのではと
    • そういうことでまだまだ若い人には競プロ以外のチャネルを試してほしい
  • 人間機械学習千田さん
    • (将棋盤面の)学習セットとテストセットを分けて学習セットの評価値を学習しながらテストセットの盤面の評価値を最小二乗法で最小化する(は？)
  • プログラマーは PC に論理を与えるのをやっている
    • プログラム自体は論理を理解していない

DISCO 紹介, 見学

就活性だし聞いておくべきだったのではとか思ったけどあんまり聞いてない
ていうかどこも調子の良いことしか言わないからか, 話を聞く任意の企業が優良企業に見える

懇親会

btk さんとかヘクトさんとかとしゃべる
btk さんに 114514 回競プロやってと言われた

  • のでちょっと自分にしては珍しいことをやった(今いいねしても遅いですよ)

  • kuuso さん初めてお会いした気がする(ありがとうございました)
  • 他にもいろいろな人に会った気がするけど忘れた(ごめん)