CodinGameに新しくDots and BoxesがCONTRIBUTEされていたので遊んでみます。
実に他愛もないアルゴリズムなんですが、たまたま当たり、
まだ参加者が少ないのでとりあえずトップに、そして高速化することにしてみました。
ルール
お互いに線をひいていきます。
ボックスの4つで獲得、獲得した時まわりも3つになればボックス獲得で線も追加され連鎖していくようです。
最終的にどちらが多くのボックスを取るか。
初期作成
周囲のボックス情報を取得するのに都度、
周囲のボックス名を計算、
そしてボックス情報を全ループしてその周囲のボックス名と一致したら取得しています。
高速化
１）ボックス情報をボックス名をキーに辞書登録してみたところ、20％ほど速度アップ（思ったよりあがってない）
２）ボックス名、方向をキーに周囲のボックス名の入った、テーブルを最初に全作成して5％ほどアップ
３）辞書のない場合にgetとdefaultを使用せず、キーがあるか判定して条件分岐をして5％ほどアップしました
感想
1ターンに100手ぐらい読むアルゴリズム、56ターンほどの全計算がわずか13ms
こんなのに計算で人間が勝てるわけがない。棋士が数年前まで勝っていたというのがすごいと思いました。
うまいこと分配するアルゴリズムがあれば、 物資面ではあっという間に幸せになれそうな気がします。
関数名がtotoroになっているのはコーディング中 neighborのつづり確認するのが面倒だったからです。
テーブルに置き換わってなくなりましたが、となりのボックス名を取得する関数はmeiと名付けてました。
コーディング中、ちょっとしたいたずらが、ささやかなモチベーション維持になったりします。
