Problem44 - Haskellで無理矢理

30分プログラム、その317。Problem44 - Project EulerをHaskellで無理矢理解こうとして失敗した。まあ、無理だとは思ってたけどね。

使った方針は、次のようなもの。

• 適当なP_xを決める
• P_x = P_i + P_jとなるiとjを全て求める。ただしi > j
• P_i - P_jが五角数のものだけを取り出す

あと、unsafePerformIOとかを使ってログを出そうとしたけれど、うまくいかなかった。たぶん、http://haskell.g.hatena.ne.jp/jmk/20070706/1183688102にあるようなことが原因だろう。

使い方

*Main> solve
  C-c C-cInterrupted.

ソースコード

import Control.Monad.List
import Debug.Trace

ps :: [Int]
ps = map (\n->n*(3*n-1) `div` 2) [1..]

expressed :: Int -> [(Int,Int)]
expressed x = do i <- takeWhile (<x) ps
                 j <- takeWhile (<i) ps
                 guard $ x == i + j
                 return (i,j)
solve :: [Int]
solve = do y <- ps
           (i,j) <- expressed y
           guard $ (i-j) `elem` takeWhile (<i-j) ps
           return (i-j)

参考

• 過去の30分プログラム
• Problem 44 - PukiWiki