Clojure入門 - Project Eulerを解いてみる 問１8

第十八問

ツリー状の数字の連なりを上から下へと下がっていって、たどった道筋の和の最大のものを求める。

道筋自体を求めなくていいのは楽。

上から行こうとすると遅くなるか複雑になるか、なので下から見ていく。

下二段を評価する場合、下から二段目の行から、次に行くべき道筋というのは一義的に決まっている。一番下の段の、隣り合っている二つの数字のよりでかい方に行けばいい。そうすることで、下から二番目の段の最善の道筋とその大きさがわかる。

それを踏まえて、その一段上を見ると、これもまた次に行くべき道筋というのが（先ほどの計算から）一義的に決まる。というふうに、下から連鎖的に調べていくと計算量O(N)で最大の和が算出される。

まずはデータの処理：

(def src 
"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23")

(defn to-int [s] (Integer/parseInt s))
(def data
  (->> src
     (clojure.string/split-lines)
     (map #(clojure.string/split % #" "))
     (map #(map to-int %))
     (into [])))

nthを使いたいので最後にベクター化しておく。

あとは上記の戦略の通りにコードに落とし込むだけ。

(defn traverse [data]
  (loop [i   (dec (count (last data))) 
         row (last data)]
    (if (zero? i) (first row)
      (let [next-row-base (nth data (dec i))
            best-path (map max row (rest row))
            new-row (map + next-row-base best-path)]
        (recur (dec i) new-row)))))

(traverse data)