project euler 18 67

最後の二行を　左を合わせてzipWith (+)したものと　右を合わせてzipWithしたものを比較し残りのものと置換して最後までやる

上からたどる方法は配列でも使わないと無理、速度的にも無理だけど・・・

main = print $ g a67

g x | length x==1 = x
    | otherwise   = g ((init (init x)) ++ [zipWith max (zipWith (+) (last x) (last (init x))) (zipWith (+) (tail (last x)) (last (init x)))]\
)

a0=[[3],
    [7,4],
    [2,4,6],
    [8,5,9,3]]

a18=[[75],
   [95,64],
   [17,47,82],
   [18,35,87,10],
（略）

リストを最後から参照するのだからfoldr の出番だな。

main = print $ g a67
f x = foldr1 f2 x
f2 x y = zipWith max (zipWith (+) x y) (zipWith (+) x (tail y))

だいぶすっきりした。
GHCiでも1秒未満で計算する

そうか、再下行のでかい方と足せば大丈夫なんだ

f' x = foldr1 f3 x
f3 x y = zipWith (+) x (zipWith max y (tail y))

ということはこれワンライナーになるな。

main = print $ foldr1 f4 a67 where f4 x y= zipWith (+) x (zipWith max y (tail y))

すげぇ。