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"

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

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

ですが、

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

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