Euler Solution 18

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 18

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): 43.68 ms

; Define the triangle as a list of lists.
(define triangle '(
(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)
))

; 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 67.

Python by Althalus

Runtime < 1 ms

pyramid = 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

pyramid = pyramid.split('\n')
split_pyramid = [line.split(' ') for line in pyramid]

list = split_pyramid.pop()
while len(split_pyramid) > 0:
    new_list = []
    for i in range(0,len(list)-1):
        if i+1 < len(list):
            if int(list[i]) > int(list[i+1]):
                new_list.append(int(list[i]))
            else:
                new_list.append(int(list[i+1]))
    list = split_pyramid.pop()
    for i in range(0,len(list)):
        list[i] = int(list[i])+int(new_list[i])

print(list)
run_time = time.time() - start_time
print(run_time)
Personal tools