# max-sum-triangle-path

Assume an equilateral triangle T of numbers. A move from any non-base number n in T ends at the number immediately below and to the left or right of n. A path in T is a sequence of moves starting at the apex and ending at a number in the base. The path sum is the sum of the numbers along a path. Given a triangle, find a path with maximum sum among all paths through the triangle.

A brute-force solution is straightforward:

``` (define (max-sum-path triangle)

; Return a pair, the car of which is the path sum of the cdr, which
; is a max path through the given triange.  A path is a list of 0s
; and 1s indicating left (0) or right (1) moves.

(let

((rows (1- (triangle 'row-count)))
(max-path '())
(max-sum -1))

(let loop

((row 0) (i 0) (path '()) (sum (triangle 'get-value 0 0)))

(if (< row rows)

; Above the base.

(let ((r (1+ row)))

; Let's go down and to the left.

(loop r i (cons 0 path) (+ (triangle 'get-value r i) sum))

; Now let's go down and to the right.

(let ((i2 (1+ i))
(sum' (+ (triangle 'get-value r i2) sum)))
(loop r i2 (cons 1 path) sum'))

; At the base; this path is done.

(if (or (null? max-path) (> sum max-sum))
(begin
(set! max-path path)
(set! max-sum sum)))))

(cons max-sum (reverse max-path)))))
```

A numeric triangle is a simple-object representing an equilateral triangle of numbers. For reasons explained below (and which you may have already anticipated), a numeric triangle is a wrapper around a general triangular matrix.

``` (define (numeric-triangle rows)

(let

((triangle (triangle-matrix rows)))

; Fill the triangle with random numbers.

(do ((r 0 (1+ r))) ((>= r rows))
(do ((i 0 (1+ i))) ((> i r))
(triangle 'set-value! r i (- (random 100) 50))))

(lambda (cmd . args)
(case cmd
((row-count) (triangle 'row-count))
((get-value) (apply triangle 'get-value args))
((set-value!) (apply triangle 'set-value! args))
(else (error "unrecognized command"))))))
```

A triangular matrix is represented as a vector of minimum necessary size. Perhaps the easiest way to understand the indexing is to imagine a triangle stored in a 2d matrix with all rows pushed to the left; that is, stored in a lower triangular matrix.

``` (define (triangle-matrix rows)

(define (gauss n) (/ (* n (1+ n)) 2))
(define (index r i) (+ (gauss r) i))

(let*

((row-count rows)
(N (gauss rows))
(values (make-vector N '()))
(get-value (lambda (r i) (vector-ref values (index r i))))
(set-value! (lambda (r i v) (vector-set! values (index r i) v))))

(lambda (cmd . args)
(case cmd
((row-count) rows)
((get-value) (apply get-value args))
((set-value!) (apply set-value! args))
(else (error "unrecognized command"))))))
```

This solution works, but isn't good because it's exponential in the number of rows in the triangle. Increasing the triangle size by five rows increases the solution run-time in usec by at least an order of magnitude; the solution run in Guile 1.8.1 on a fairly modern laptop takes over four minutes to find a path through a 25-row triangle.

The solution is slow because it repeatedly recomputes max-sum paths for sub-triangles. The fix for such problems is to use dynamic programming: once a max-sum path is found for a sub-triangle, remember it so the next time the max-sum path for that sub-triangle is needed, it can be found by indexing rather than more onerous computing.

Another trick to exploit is to find sub-triangle max-sum paths from the base up rather than from the apex down. This allows a third trick, which is to replace a full table with a pair of rows (as was done for edit-distance); for simplicity, however, this last trick will be skipped.

``` (define (max-sum-path-dp triangle)

; Return a pair, the car of which is the path sum of the cdr, which
; is a max path through the given triange.  A path is a list of 0s
; and 1s indicating left (0) or right (1) moves.

(let* ((rows (triangle 'row-count))
(table (triangle-matrix rows)))

; Fill in the base

(let ((r (1- rows)))
(do ((i 0 (1+ i))) ((> i r))
(table 'set-value! r i
(cons (triangle 'get-value r i) '()))))

; Work up from the base to the apex, row by row.  When done,
; return the max-sum path found at the apex.

(do ((row (- rows 2) (1- row))) ((< row 0) (table 'get-value 0 0))

; Within each row, work left to right (or right to left; it
; doesn't matter).

(do ((i 0 (1+ i))) ((> i row))

(let*

((row-below (1+ row))

(left (table 'get-value row-below i)) (l-max (car left))

(right (table 'get-value row-below (1+ i)))
(r-max (car right)))

(let ((v (triangle 'get-value row i)))

(table 'set-value! row i
(if (< r-max l-max)
(cons (+ l-max v) (cons 0 (cdr left)))
(cons (+ r-max v) (cons 1 (cdr right)))))))))))
```

The dynamic-programming version of max-sum-path solves a 25-row triangle in 9 msec and a 300-row triangle in 36 sec.