# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1519622649 0
# Node ID 76b628777c34c3ea82321c7ee1dbdecd0520130c
# Parent  18b41e49f53b62c261357a62ec61d8207ab46365
Problem 67

diff -r 18b41e49f53b -r 76b628777c34 src/problems.lisp
--- a/src/problems.lisp	Sat Feb 24 19:10:54 2018 -0500
+++ b/src/problems.lisp	Mon Feb 26 05:24:09 2018 +0000
@@ -386,21 +386,10 @@
   ;; by trying every route. However, Problem 67, is the same challenge with
   ;; a triangle containing one-hundred rows; it cannot be solved by brute force,
   ;; and requires a clever method! ;o)
-  (let ((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))))
+  (let ((triangle (iterate (for line :in-csv-file "data/018-triangle.txt"
+                                :delimiter #\space
+                                :key #'parse-integer)
+                           (collect line))))
     (car (reduce (lambda (prev last)
                    (mapcar #'+
                            prev
@@ -1597,6 +1586,35 @@
     (iterate (for n :from 1 :below (find-bound))
              (summing (score n)))))
 
+(defun problem-67 ()
+  ;; 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 in triangle.txt, a 15K text file
+  ;; containing a triangle with one-hundred rows.
+  ;;
+  ;; NOTE: This is a much more difficult version of Problem 18. It is not
+  ;; possible to try every route to solve this problem, as there are 299
+  ;; altogether! If you could check one trillion (1012) routes every second it
+  ;; would take over twenty billion years to check them all. There is an
+  ;; efficient algorithm to solve it.
+  (car (reduce (lambda (prev last)
+                 (mapcar #'+
+                         prev
+                         (mapcar #'max last (rest last))))
+               (iterate (for line :in-csv-file "data/067-triangle.txt"
+                             :delimiter #\space
+                             :key #'parse-integer)
+                        (collect line))
+               :from-end t)))
+
 (defun problem-69 ()
   ;; Euler's Totient function, φ(n) [sometimes called the phi function], is
   ;; used to determine the number of numbers less than n which are relatively
@@ -2426,6 +2444,7 @@
 (test p61 (is (= 28684 (problem-61))))
 (test p62 (is (= 127035954683 (problem-62))))
 (test p63 (is (= 49 (problem-63))))
+(test p67 (is (= 7273 (problem-67))))
 (test p69 (is (= 510510 (problem-69))))
 (test p74 (is (= 402 (problem-74))))
 (test p79 (is (= 73162890 (problem-79))))