Project Euler Problem 18

problem_18.clj

;;; By starting at the top of the triangle below and moving to adjacent numbers
;;; on the row below, the maximum total from top to bottom is 23.
;;;
;;;    3
;;;   7 4
;;;  2 4 6
;;; 8 5 9 3
;;;
;;; That is, 3 + 7 + 4 + 9 = 23.
;;;
;;; Find the maximum total from top to bottom of the triangle below:
;;;
;;;               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

(ns projecteuler.problem-18
  (:require [clojure.string :as str])
  (:use clojure.test))

(def triangle
  "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-vec
  "複数の数字を含む1行の文字列をパースし vector に変換する。"
  [s]
  (->> (str/split s #"\s+")
       (map #(Integer/parseInt %))
       (into [])))

(defn make-triangle-vec
  "問題の文字列データを、改行ごとに区切り二重配列に格納する。"
  [s]
  (->> (str/split-lines s)
       (map #(to-int-vec %))))

(defn calc-two-lines
  "問題の配列データ(n行)の下２行分(n行、n-1行)を受け取り、n-1行に相当する結果を返す。"
  [lower upper]
  (loop [lower lower upper upper result []]
    (if (= (count upper) 0)
      result
      (recur (next lower)
             (next upper)
             (conj result (+ (first upper) (max (first lower) (second lower))))))))

(defn problem-18
  "Project Euler Problem-18"
  ([] (problem-18 triangle))
  ([s] (->> (make-triangle-vec s)
            (reverse)
            (reduce calc-two-lines)
            first)))

;; test
(is (= (to-int-vec "1") [1]))
(is (= (to-int-vec "01 10 20") [1 10 20]))
(is (= (make-triangle-vec "1") [[1]]))
(is (= (make-triangle-vec "1\n2 3") [[1] [2 3]]))
(is (= (make-triangle-vec "1\n2 3\n4 5 6") [[1] [2 3] [4 5 6]]))
(is (= (calc-two-lines [1 2] [3]) [5]))
(is (= (calc-two-lines [1 2 3] [4 5]) [6 8]))
;; 例題
(is (= (problem-18 "3\n7 4\n2 4 6\n8 5 9 3") 23))

(time (problem-18))
;;"Elapsed time: 1.954 msecs"

;;; problem-67
;; (def s (slurp "http://projecteuler.net/project/triangle.txt"))
;; (time (problem-18 s))
;; "Elapsed time: 135.868 msecs"

考え方とか感想とか

• 問題のデータを文字列として定義しておき、二次元の vector に変換して処理します。
• n行の二次元配列の n行目、n-1行目のデータをとり、最大値のパスとなりうる値を返す関数(calc-two-lines)を定義しました(名前が悪いですが...)。
• あとは、その関数を reduce を使って元のデータを適用していきます(reduce を適用させるために、元のデータを reverse しています)。
• 要するに、ボトムアップ・アプローチです。
• Problem-67 もついでにやってみました。Elapsed が 135.868 msec なので、全く問題無さそうです(Clojure 速い)。

底辺からスタートし, 二股の大きい方だけ足して行くのは順当な解法と思います.
パーズから reverse までまったく一緒ですが, その後の loop のところを partition と map でまとめて, reduce した解答例を作成しましたので貼っておきます.
https://gist.github.com/4472647
計算時間は遅くなってますのであくまで参考ということで.

解答例のgist、拝見させていただきました。largers-of-each-two 、シンプルで分かりやすくていいですね(こういう発想がなかったので勉強になりました)。

ぱっと見たときは同じかなと思ってましたが、計算の方向が逆だったりしたので、僕のも貼ります。
解説付きなので、ブログの方です。

http://ypsilonbox.blogspot.jp/2011/11/euler-problem-67.html

• 方向は上から下向きです。下からの方がいいと思います。
• 計算にはreduceを使っています。 reduceのこういう使いかたが好きだったりします。
• 問題文のパーズは line-seqを使ったせいか、すっきりしていると思います。
• 計算するときにmapが使えるように、リストを加工しています。

Blog 読ませていただきました。解説を読んで「ああなるほど」となりました。やっていることはややこしくないので、コードがすっきりしていていいですね。こちらも勉強になりました。ありがとうございます。

(defn to-int-vec
  [s]
  (->> (str/split s #"\s+")
    (map #(Integer/parseInt %))
    (into [])))

ですが、

• 最初に (str/trim) を実行すると、triangle の行頭の空白を気にしなくて済む
• (into []) よりは vec の方が分かりやすいのでは?

と指摘してみます。(解法が殆ど同じだったので、メインのアルゴリズム以外の部分に突っ込みをいれます)