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.


category-code