Euler Solution 67
From ProgSoc Wiki
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.