以下の三角形の一番上から隣接した数字を移動して一番下まで移動したときの 合計の最大値は23である。（データ省略）
以下の三角形を一番上から下まで移動したときの合計の最大値を求めよ。（デー タ省略）
（注）この問題は16384通りしかないので、すべての経路を計算することも可能 である。しかし、この問題の発展問題である問題67では100列のデータがあるの で、総当りでは答えを求めることが出来ない。
問題のデータはProject Eulerのサイトを参照してほしい。ここではそのデータ がeuler018.datというテキストファイルに入っているとして扱うことにする。 まずはファイルからデータを読み込み三角形のに並んだ数字をリストのリスト として表現する。HaskellではreadFile関数でファイルの中身を文字列として読 み込むことができる。ここでdo表記を使うと以下のコードのようにファイルの 中身全体が変数xに入る。Haskellの入出力の関数はIOモナドというもので表現 されており、型の整合性を考えるとdo表記の最後に値を返すにはreturn関数を 使うことになる。ここではIOモナドについては詳しくは立ち入らない。
全体のプログラムの構造が上のように決まったところで中身の処理を考えると、 まず文字列を解析してリストにする必要がある。linesは文字列を一行ごとの文 字列のリストに分解する関数。wordsは文字列を単語ごとの文字列のリストに分 解する関数。linesの結果にmapで一行ごとにwordsを適用することで単語ごとの リストのリストに分解できる。ここでmapでreadを適用することで文字列を数値 に変換する。上から下までたどったときのすべてのルートの和のリストを求め る関数travelを定義し、最後にmaximumで最大値を求める。
三角形を上から下にたどるときにとりえるルートはそれぞれの地点で、右下に いくか左下にいくかの二通りなので、現時点までの和をもとめつつ再帰的にリ ストを連結していくようにtravelを定義する。これは全てのルートについて計 算することになるので非常に低速であるが、ここでは特に問題にならない。問 題67では同じ問題でデータが100行に増えたバージョンがあり、そこでもっと効 率的なプログラムを考えることにする。
euler018 = do x <- readFile "euler018.dat"
return $ maximum $ travel 0 0 15 0
$ map ((map read) . words) $ lines x
where travel i j n x a
| i == (n - 1) = [x + y]
| otherwise = travel (i + 1) j n (x + y) a
++ travel (i + 1) (j + 1) n (x + y) a
where y = a !! i !! j