読者です 読者をやめる 読者になる 読者になる

Google Code Jam 2016 Qualification Round レビュー in Haskell

今年もスケジュールが合わず参戦できなかったので後日レビュー実施。Pythonで解いた後にHaskellでやってみた。ただしHaskellで解いてみるだけでは今までと変わらない気がするので、do構文とArrayは使用しない、という制約を付けた。ただ、HaskellらしくList(無限リスト)を多用するように心がけてはいるものの、値を持ち回さないで状態系モナドを活用するという姿勢で解けるまでには至っていない。

  • Problem A. Counting Sheep

与えられた数字をNとすると、[N, N*2, N*3, ...] の無限リストを作成し、そのリストの要素を一つずつ集めたリストを準備する。つまり、[ [N], [N, N*2], [N, N*2, N*3], ...] というリストを作って、Unique . Sort で結果が"0123456789"になれば、そのリストの最後の要素を表示して終了。結果がそうならない場合に備えて実はその無限リストを1000に絞っている。

gist.github.com

  • Problem B. Revenge of the Pancakes

先頭のパンケーキと別の面のPancakeが現れたところで、同じ面のPancakeをひっくり返す。takeWhileとdropWhileを組み合わせて、Pancakeをひっくり返すリストと、そのままのリストを作り出し、それを全てのPancakeが同じ面になるまで繰り返す。全てが+ならそれで終了、-なら最後に1回加えて終了。

gist.github.com

  • Problem C. Coin Jam (Only for small)

1で始まり1で終わるnbitのcoinの無限リストを作って、Jamcoinの条件でfilterし、先頭からj個取り出す。出力に必要なNontrivial Divisorはfilterの条件式中に現れるが、出力として取り出せないので、Jamcoinを取り出した後、それを元に改めて作り出している。サンクのキャッシュが効けばそれほど非効率でも無いかなという淡い期待はあるが自信はない。これは、Python版でもLargeが解けないでいるが、Haskell版ではtakeの引数の型がIntのため、桁数制限無しのIntegerを一括して諦めているので、その時点でおそらくLargeは無理だろう。

gist.github.com