Project Euler #018 – 和が最大となる経路

12 1月 2010

Project EulerをClojureでおさらいシリーズ。
Problem 18

日本語訳：

下の三角形の頂点から隣接する数字を下まで辿っていくと、その数値の和の最大数は23となる。
3
7 4
2 4 6
8 5 9 3
この例の場合、3 + 7 + 4 + 9 = 23 である。

以下の三角形において、同様に和の最大数を求めよ。
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
注意：この例では16384通りのルートしかないのですべての経路を調べることもできる。しかし Problem 67 では同様の問題でも三角形が100行からなるので総当たりで解くのは不可能である。もっと賢い方法が求められる。

選択肢の枝をどのように切り落としていくかが問題。

以前Rubyで解いたもの：

#!/usr/bin/env ruby
 
Rows = 15
tri = []
tri << %w(75)
tri << %w(95 64)
tri << %w(17 47 82)
tri << %w(18 35 87 10)
tri << %w(20 04 82 47 65)
tri << %w(19 01 23 75 03 34)
tri << %w(88 02 77 73 07 63 67)
tri << %w(99 65 04 28 06 16 70 92)
tri << %w(41 41 26 56 83 40 80 70 33)
tri << %w(41 48 72 33 47 32 37 16 94 29)
tri << %w(53 71 44 65 25 43 91 52 97 51 14)
tri << %w(70 11 33 28 77 73 17 78 39 68 17 57)
tri << %w(91 71 52 38 17 14 91 43 58 50 27 29 48)
tri << %w(63 66 04 68 89 53 67 30 73 16 69 87 40 31)
tri << %w(04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)
Tri = tri.map{|line| line.map{|num| num.to_i}}
$cache = tri.map{|line| line.map{|num| nil}}
 
def pick_grater(depth, pos)
  current = Tri[depth][pos]
  return current if depth == Rows - 1
  $cache[depth+1][pos] ||= pick_grater(depth + 1, pos)
  $cache[depth+1][pos+1] ||= pick_grater(depth + 1, pos + 1)
  left  = $cache[depth+1][pos]
  right = $cache[depth+1][pos+1]
  (left > right ) ? (left + current) : (right + current)
end
 
p pick_grater(0, 0)

再帰＆キャッシュです。

頂点からスタートして
最大数＝（左右の選択肢が持つ和の大きいほう）＋（自分の数字）
で、あとは再帰。

さて、次はClojureで書いてみます。

書籍 “Programming Clojure” より “Six Rules of Clojure FP” の5つめ：

Know the sequence library. You can often write code without using recur or the lazy APIs at all.

最近はこれを心がけています。

Ruby版のは再帰ですが実際の処理としては枝の最下部から切り落とされていきます。

だったら最下層から折りたたんでいけば再帰を使わなくてもいけそうです。

(ns euler.p018)
 
(def triangle-text
  "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")
 
(def triangle
     (for [row (map #(re-seq #"[0-9]+" %)
		     (.split triangle-text "\n"))]
       (map #(Integer. %) row)))
 
(defn merge-rows
  "Return maximum values for upper row."
  [last-row current-row]
  (map +
       current-row
       (map #(apply max %) (partition 2 1 last-row))))
 
(println "Answer : "
	 (first (reduce merge-rows (reverse triangle))))