;; Problem 18
;; 31 May 2002

;; 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 5
;;  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

;; NOTE: As there are only 16384 routes, it is possible to solve this
;; problem 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)

(defvar *small-triangle*
  '((    3    )
    (   7 5   )
    (  2 4 6  )
    ( 8 5 9 3 )))


;; lower[0] upper[0]
;; lower[1] upper[0,1]
;; lower[2] upper[1,2]
;; lower[3] upper[2]

(defun get-upper-idxs (lower-idx upper-len)
  (cond ((= 0 lower-idx)
	 (list lower-idx))
	((= lower-idx upper-len)
	 (list (- lower-idx 1)))
	(t
	 (list (- lower-idx 1)
	       lower-idx))))

(defun zip-rows (upper-row lower-row)
  (apply
   #'append
   (loop for item in lower-row
	 for lower-idx = 0 then (+ lower-idx 1)
	 collect
	 (loop for upper-idx in (get-upper-idxs lower-idx (length upper-row))
	       collect (list (nth upper-idx upper-row)
			     (nth lower-idx lower-row))))))

; (zip-rows  '(7 5) '(2 4 6)) ; ((7 2) (7 4) (5 4) (5 6))

;; merge upper into lower, taking the max of the sums from the pairs
(defun combine-rows (upper-row lower-row)
  (loop for litem in lower-row
	for lidx = 0 then (+ lidx 1)
	collect
	(apply #'max
	       (loop for uidx in (get-upper-idxs lidx (length upper-row))
		     collect (+ (nth lidx lower-row)
				(nth uidx upper-row))))))

;; (combine-rows '(3) '(7 5)) ; (10 8) 
;; (combine-rows  '(10 8) '(2 4 6))
;; (combine-rows '(12 14 14) '(8 5 9 3))
;; (apply #'max '(20 19 23 17)); 23

(defun collapse-triangle (triangle)
  (let* ((current-row (first triangle)))
    (loop for next-row in (rest triangle)
	  do
;; 	  (format t "curr-row:~a~&next-row:~a~&"
;; 		  current-row
;; 		  next-row)
	  (setf current-row (combine-rows current-row next-row)))
    current-row))

(apply #'max (collapse-triangle *small-triangle*))

(defvar *large-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)))


(apply #'max (collapse-triangle *large-triangle*)); 1074