Euler Solution 67

From ProgSoc Wiki

Jump to: navigation, search

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.

Personal tools