; maximum sum path

(define sample
  '((3)
    (7 4)
    (2 4 6)
    (8 5 9 3)))

(define input18
  '((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)))

(define (max-sum tri)
  (define (but-last xs) (reverse (cdr (reverse xs))))
  (define (step xs ys)
    (map + ys (map max (cdr xs) (but-last xs))))
  (let loop ((tri (reverse tri)))
    (if (null? (cdr tri)) (caar tri)
      (loop (cons (step (car tri) (cadr tri)) (cddr tri))))))

(display (max-sum sample)) (newline)
(display (max-sum input18)) (newline)

(define (max-sum-path tri)
  (define (sum xs) (apply + xs))
  (define (step last next-to-last)
    (let loop ((last last) (next-to-last next-to-last) (out (list)))
      (if (null? next-to-last) (reverse out)
        (loop (cdr last) (cdr next-to-last)
              (if (< (sum (cadr last)) (sum (car last)))
                  (cons (cons (car next-to-last) (car last)) out)
                  (cons (cons (car next-to-last) (cadr last)) out))))))
  (define (fix-last-row tri)
    (cons (map list (car tri)) (cdr tri)))
  (let loop ((tri (fix-last-row (reverse tri))))
    (if (null? (cdr tri)) (caar tri)
      (loop (cons (step (car tri) (cadr tri)) (cddr tri))))))

(display (max-sum-path sample)) (newline)
(display (max-sum-path input18)) (newline)

23
1074
(3 7 4 9)
(75 64 82 87 82 75 73 28 83 32 91 78 58 73 93)