Problem 275 – Project Euler

問題の概要．

ある条件を満たす，polyominoを探す．

その条件の１つは，横方向にバランスがとれていること（重心のx座標が0）．

詳細な条件は上のリンクで．

絵でみると分かりやすい．

下図はproject eulerからの引用．

f🆔jeneshicc:20100123174249g:image

求めるのはサイズ18．しかし，形が想像できないので，ナイーブな検証用のコードをC++で書いた．

実行したら，サイズ15で4 秒ぐらいだった．これなら，サイズ18でも大丈夫か，と思い，サイズ18で実行したら，

見事に1分以上かかった（3分ぐらい）．

ナイーブな方法でもうまく，枝刈りをすれば，1分切れるかもしれないが，もっと賢い方法がありそう．

ひさびさに，難問か？

追記

どうにかして，Haskellで速いコードを書こうと思っていた．

しかし，こういうのはどうも，書きづらい．問題が難しいからでもある．

この手の問題は可変配列を使うのが単純で効率的だろう．しかし，STArray使うのは，なんというか負けな気がする

（STArray使うくらいなら，C++で書く）．

どうにかして，純粋関数型言語的に書けないのかなー．