phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない！

Topcoder MM108 CrosswordPuzzler

概要

1週間マラソンはきつい。
最終順位は、20位(58人参加)で、結構良かった。

問題

W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。
このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場合、必ず辞書にある単語になるようにしなければならないし、2回以上同じ単語がでてくるようにはしてはいけない。
スコアは、フィボナッチ数列fib(x)を用いて「Σ_{グリッドに出現する単語i} fib(i)」とするとき、スコアができるだけ高くなるようなグリッド敷き詰めを返せ。

最終的に提出したアプローチ


  • ベースはビームサーチ
    • ただし、計算時間の都合で、グリッドのサイズでパラメータを調整
    • 単語は、真ん中付近(サイズが小さかったら微妙にずらしたものも候補に入れた)
  • 評価関数は「単語スコア合計+文字を置いていないマスの数-使ったマス数」
    • お気持ちは、重なりが多いほどよさそうと思ったので、できるだけマスを使わずにたくさん置いた方がいい、という感じ
    • 単純なスコアにしてしまうと、終盤までスコアに差が出ずに、ビーム幅を必要としそうだったので、できるだけ序盤でも差がでるようにしたかった
  • 辞書は、長さ順にkグループに分け、順番にビームサーチで最適化するようにした
    • 単語数が減るので、最適解が得られない可能性があるが、計算量が減らせて、辞書サイズが多くてもまわせた

振り返り

1週間マラソンで、土日が腰痛でダメで何も手を付けられなかったのがかなり痛かった。

方針決め

これまでのマラソンの反省として、「最適解の形がどんな形か？」のイメージをミスるとお話しにならないと思ったので、ざっくりでも最適解の形を考えた。

具体的な形まではわからなかったけど、

  • 長い単語をできるだけ使う
  • 単語がクロスしている方が、少ないマスで表現できるので、よさそう

は間違いなさそうで、クロスを多く作るような形を目指すことに。

(最初の時点での理想イメージとしては、以下のような図でいくつか歯抜けになるようなものなんじゃないか？を考えていた)
f:id:phyllo_algo:20190311005756p:plain

最初は、焼きなましが適用できないか？と考えていたけど、単語を消したときの処理が面倒そう、と思ってビームサーチ方面で考えることにした。
(この時点で、最適解はぐちゃぐちゃ絡み合ったイメージを持っていたので、greedyな解は無理では？と思って除外してしまっていた)

面倒そうというのは、辞書が{aaa,ccc,bacb}の場合、

-a--
-a--
bacb
--c-
--c-

と置いて、bacbを消した場合、acを残してもacが辞書にないのでinvalid、acも消してもaa,ccがinvalidになるので、invalidを許すか、invalidを許さない場合は連鎖的に単語を削除していくイメージ。
invalidは最後まで残すと解消が無理そうだし、invalidを許さない場合、単語の連鎖が多くなりそう、と思ってあきらめた。
(終了後、onigiri(utmath)さんとの感想戦で「消せないなら消さない」というのもあるよね、というアイデアは考慮できていなかった)

テスター、ビジュアライザ

今回、testerがエラー出力を握りつぶしていたり、visualizerが付いていなかったので、デバッグが非常につらく、途中からc++で書き直したりしてた。

visualizerはなかったので、テキスト出力で見てたけど、縦長になってしまったり、クロスしている文字がどこなのか見にくく、ちゃんと整形して表示するものだけでも作るべきだった。

(結局、終わってからビジュアライザを作ったらそんなに時間かからずできたので、作るべきだったかも・・・)

ビームサーチの調整

ビームサーチをやろうと思ったら、結構生成される近傍が大きくなってしまって探索空間が大きそうというのにハマる。

妥協案として、真ん中付近に一番長い単語を置いて、そこからできるだけ長い単語をクロスするように設置していく(クロスできないならできるだけ長い単語を適当に置く)方法を試す。
結局、これ以外の方法などは時間がなくて試せなかった。

感想戦で、「いうほどクロスが多くない」という話が出ていて、ビジュアライザを作っていれば気づけたかもしれないと思う・・・

パラメータの調整

単純に上記の探索だと無駄な探索も多くて時間がかなりかかっていたので、ある程度時間内に終わるよう調整を考えた。

一つ目は、長さが小さい単語は使う必要があまりないor後で設置すればよさそうかもと思い、辞書を長さごとにグループ分けして、計算量を減らすことを考えた。

二つ目は、サイズが大きすぎるときのパラメータ(ビーム幅や辞書の分割数など)を調整してた。けど、あんまりやりたくなかったので、適当に時間に間に合いそうな値にして提出して、結局最後までそのままだった。。。

その他

盤面や辞書の生成ルール的に、「大きいケース」と「小さいケース」に偏りがあると思って、見ていた。
計算してみると、だいたい、マスのサイズが1000以下になるのが63%ぐらい、1000より多くなるのが37%ぐらいで、半分以上がマスのサイズが1000以下の小さいケースのようだった。

辞書サイズも小さいので、できるだけ小さいケースは十分な探索をできるように調整したかったけど、最終提出には入れられなかった。

反省

  • アプローチ
    • 今回は様々な手法が有効だったようで、
      • greedyに単語(またはフレーム)を置いて、それをランダムに繰り返す感じ
      • より多くの交差、より長い単語が最初になるような多くのrandom searchを試す
      • 焼きなましで配置や追加削除を試す(＋様々な工夫)
      • 市松模様っぽく単語を配置しつつ、できるだけ単語を串刺しにする感じを焼きなましする
      • など
  • visualizer

ビジュアライザ

終わった後で、ビジュアライザを作った。
GitHub - jetbead/TopCoderMM108_Visualizer: Topcoder MarathonMatch 108 Visualizer

課題意識としては、

  • 最終状態の出力ではなく、焼きなましやビームサーチなどの途中状態も見れるようにしたい
  • ファイルに書き出す方法だと膨大な量になってしまったり、読み込み面倒なので、できるだけC++で完結させたい
  • macで手頃で使えるのにしたい

というのがあった。

QtやGTKなどはやや大がかりすぎるような気がして、OpenSiv3Dは新しめのコンパイラを必要とすることから、一番手頃そうなSDL2を試してみた。(「ゲームプログラミングC++」という本でも使われていたのを見たので)
悪くなさそうなので、他の手段も調べつつ、いろいろ使ってみたい。(できれば、visualizerで必要な要素をまとめたい)