Problem 275

Problem 275 – Project Euler

問題の概要.

ある条件を満たす,polyominoを探す.

その条件の1つは,横方向にバランスがとれていること(重心のx座標が0).

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

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

下図はproject eulerからの引用.

f:id:jeneshicc:20100123174249g:image

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

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

見事に1分以上かかった(3分ぐらい).

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

ひさびさに,難問か?

追記

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

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

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

(STArray使うくらいなら,C++で書く).

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

More Reading
Newer// 今日の失敗
Older// firefox 3.6