Skip to content

Instantly share code, notes, and snippets.

@kohyama
Last active December 10, 2015 18:09
Show Gist options
  • Save kohyama/4472647 to your computer and use it in GitHub Desktop.
Save kohyama/4472647 to your computer and use it in GitHub Desktop.
Project Euler Problem 18
(require '[clojure.test :refer (is)])
(require '[clojure.string :as s])
(def input "
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 largers-of-each-two [coll]
(map (partial apply max) (partition 2 1 coll)))
(defn pep018
([] (pep018 input))
([triangle]
(->> (s/trim triangle)
(#(s/split % #"\n"))
(map #(s/split (s/trim %) #"\s+"))
(map (partial map #(Integer/parseInt %)))
reverse
(reduce #(map + (largers-of-each-two %) %2))
first)))
(is (= (largers-of-each-two '(8 5 9 3)) '(8 9 9)))
(is (= (pep018 "
3
7 4
2 4 6
8 5 9 3
") 23))
(pep018)
@kohyama
Copy link
Author

kohyama commented Jan 7, 2013

Project Euler Problem 18
「三角形状並べた数値群を与えられた場合, 上の頂点から底辺に向かってそれぞれ二又に分かれていき, 通過する数を足していった場合の総和で最大はいくらか」
という問題です.

文字列をパーズし, 底辺から順に見たいので reverse します.
reduce でやっていることは,

  • 底辺をアキュムレータの初期状態とします. (初期化引数を省略したので自動的にそうなります)
  • アキュムレータの要素を二個ずつのペアとして見て, 大きい方からなるリスト (largers-of-each-two %) を作ります. 要素数は一つ少なく, 次のリストと同じ要素数となります. この二つのリストの各要素を足し合わせ, 新しいアキュムレータとします.

です.
reduce が終わると要素が一つのリストになっているはずですので first で取り出して終わりです.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment