# Solutions for Problem 67

Given a triangle of the form:

```   3
7 5
2 4 6
8 5 9 3
```

find the maximum sum of a path from the top to the bottom (without any cycles).

## Lisp by SanguineV

Runtime (Script mode): 66.74 ms

```; Define the triangle as a list of lists.
(define triangle '(
; Insert enormous triangle here!
))

; ALGORITHM
; There is a fairly simple algorithm for calculating the path that does not require
; complex tree searching.
; Start with the last row, transform it into a shorter list where each elements is
; the larger of the two adjacent elements in the original.
; For example: (8 5 9 3) transforms to (8 9 9)
; Then zip this with the row above using addition.
; For example zipWith + (8 9 9) (2 4 6) = (10 13 15)
; The triangle is now one row shorter (taken the last two rows and transformed them
; into a single row). Continue until only the top of the triangle remains and is
; the sum of the longest path.

; Process a single row
; Returns a list of numbers that represents the higher of each pair
(define (procrow r)
(cond
((= 1 (length r)) (cons r ()))
((= 2 (length r)) (cons (max (car r) (car (cdr r))) ()))
(else (cons (max (car r) (car (cdr r))) (procrow (cdr r))))))

; Zip two lists together
(define (zipWith f as bs)
(if (= 0 (length as))
()
(cons (f (car as) (car bs)) (zipWith f (cdr as) (cdr bs)))))

; Calculate the maximum sum of a path from the top to the bottom of a triangle, returns the
; result as a single element triangle
(define (maxSum tri)
(if (= 1 (length tri))
(procrow (car tri))
(procrow (zipWith (lambda (x y) (+ x y)) (car tri) (maxSum (cdr tri))))))

; Use these functions on the triangle defined above and print the value.
(begin (display (car (car (maxSum triangle)))) (newline))
(exit)
```

This solution also used to solve Problem 18.