Project Euler Problem 67

Maximum path sum II

Problem 67

Published on Saturday, 10th April 2004, 02:00 am; Solved by 46063

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

 

Answer: 7273

 

Racket

 

#lang racket
(require net/url)
(define nums
  (let* ([text (port->string (get-pure-port (string->url "http://projecteuler.net/project/triangle.txt")))])
    (list->vector (map string->number (string-split text)))))

(define (triangle-yx->x y x)
  (+ (/ (* y (+ 1 y)) 2) x))

(define (problem67)
  (for* ([i (in-range (- 100 2) -1 -1)]
         [j (in-range 0 (+ 1 i))])
    (vector-set! nums
                 (triangle-yx->x i j)
                 (+ (vector-ref nums (triangle-yx->x i j)) (max (vector-ref nums (triangle-yx->x (+ 1 i) j))
                                                                (vector-ref nums (triangle-yx->x (+ 1 i) (+ 1 j)))))))
  (display (vector-ref nums 0)))

(problem67)