Project Euler Problem 67 Solution

Question

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.

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^{12}) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Haskell

parse :: String -> [[Integer]]
parse = map (map read . words) . lines

best :: [Integer] -> [Integer]
best row = map maximum choices where
    choices = zipWith (\a b -> a : [b]) row (tail row)

maxStep :: [Integer] -> [Integer] -> [Integer]
maxStep current next = zipWith (+) next (best current)

maxPath :: [[Integer]] -> Integer
maxPath [[x]] = x
maxPath (current:next:rest) = maxPath $ (maxStep current next) : rest

main :: IO ()
main = do
        str <- readFile "/home/zach/code/euler/067/triangle.txt"
        print $ maxPath $ reverse $ parse str

$ ghc -O2 -o maximum-path-sum maximum-path-sum.hs
$ time ./maximum-path-sum
real   0m0.012s
user   0m0.006s
sys    0m0.006s

Python

#!/usr/bin/env python
import os

def find_sum(triangle):
    def get_options(row, index):
        return triangle[row+1][index], triangle[row+1][index+1]
    row = len(triangle) - 2
    while True:
        try:
            for index, node in enumerate(triangle[row]):
                best = max([node + option for option in get_options(row, index)])
                triangle[row][index] = best
            row -= 1
        except:
            return triangle[0][0]

def main():
    triangle = [[int(digit) for digit in line.split()] for line in open(os.path.join(os.path.dirname(__file__), 'triangle.txt')).readlines()]
    print(find_sum(triangle))

if __name__ == "__main__":
    main()

$ time python3 triangle-max.py
real   0m0.023s
user   0m0.023s
sys    0m0.000s