Marathon Match 46 KnightsMoveCipher

http://www.topcoder.com/longcontest/?module=ViewStandings&rd=13679

久しぶりに参加。Coding phase が終わったところで暫定3位で、とりあえず賞金はもらえそう。

図のように正方形の盤面に文字が並べられていて、盤上をチェスのナイトの駒のように移動しながら文字を読んでいく。出てくる文章を答えてね!という問題。例えばこの図だと赤いところから順に IN.THIS.SHORT.NOTE... という具合。

ナイトのように、といっても移動する距離は4マス以上の場合もあって(例えば図の I→N)、各ステップで何マス離れた場所に動くかの情報は与えられている。スタート地点は与えられない。

平文は約8万通りの文章からランダムに選ばれる。この文章は配布されてるけど、ソースコードのサイズが 500KB に制限されてるので全部は埋め込めない。ただし getWords() という関数が用意されていて、上記の文章全体で出てくる単語と出現回数のリストが実行時に得られる。

以下自分の戦略。

まず getWords() で得られる単語表を 512 個のグループに分ける。このとき、グループ内の単語の出現頻度の合計が平均的になるようにする。頻度の高い "THE" や "OF" は単独でひとつのグループになるし、1回しか出現しない単語は 7000 語くらいのグループになる。
で、各グループのペア(512×512通り)について、グループ内の単語が平文中の連続した2単語として現れる確率を求めて、コードに埋め込んでおく。このテーブルが 512×512×1byte で 256KB。圧縮すればもっとグループの数を増やせるけど、増やしてもあまりスコアに影響なかったので無圧縮で。

実行時はこの表を使って順位をつけて、単語単位で順位優先探索。この方針で暫定スコア 42/100点くらい。

あとは枝刈りのために、3語・4語・5語まで探索したところで使った単語からハッシュ値を計算し、平文から生成したハッシュ値と符合するかチェックするようにした。これで暫定スコア 49/100 点くらい。平文のハッシュ値を格納するテーブルが約64KB×3個で、ソースコード全体のサイズは 460KB ほど。

Forum を見るといろんなアプローチがあったみたいで、なかなか面白い問題だったと思う。あと上位2人が際限なくスコアを伸ばしていくのが凄かった。