Project Euler 18-20

Problem 18

http://projecteuler.net/index.php?section=problems&id=18


あえて全てのパスで和を求める。
三角形の数の並びは横のリストのリストにする。
まず、0〜16383の数を用意する。上から始めて、2で割って余りが0なら左下に進み、1なら右下に進んで2で割る。その際に、リストのリストのtailを取り、右下に進んだらリストのtailを取る。そうすると、常に一番上の数を取ればいいことになる。
インデックス参照するコードに比べて実行時間は少し短かった。


s = "75\n"
++ "95 64\n"
...
++ "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\n"

a :: Int
a = map (\line -> map read (words line)) (lines s)

sum_path [] _ = 0
sum_path (a:as) n = (head a) + (sum_path b (div n 2))
where b = if (mod n 2) == 0 then as
else map tail as

main = print(maximum (map (\n -> sum_path a n) [0..2^(length a)-1]))

Problem 19

http://projecteuler.net/index.php?section=problems&id=19


日付のライブラリを使わなくても、次の月の1日の曜日を求めるのは簡単だから、1900年からその曜日の無限リストを作るのも容易。


month_days y m | m == 2 = if (mod y 400) == 0 then 29
else if (mod y 100) == 0 then 28
else if (mod y 4) == 0 then 29
else 28
| m < 8 = if mod m 2 == 1 then 31 else 30
| otherwise = if mod m 2 == 1 then 30 else 31

next_month y 12 = (y + 1, 1)
next_month y m = (y, m + 1)

next_month_1st (y,m,w) = (y1, m1, mod (w + (month_days y m)) 7)
where (y1, m1) = next_month y m
a = (1900, 1, 1):[ next_month_1st m | m <- a ]
b = filter (\(y,_,w) -> w == 0 && y > 1900)
(takeWhile (\(y,_,_) -> y <= 2000) a)
main = print(length b)

Problem 20

http://projecteuler.net/index.php?section=problems&id=20


特になにもない。


digits 0 = []
digits n = (digits (div n 10)) ++ [ mod n 10 ]

factorial 0 = 1
factorial n = n * (factorial (n - 1))

n = 100
main = print(sum (digits (factorial n)))