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, .
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 299 altogether! If you could check one trillion () routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
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.019s user 0m0.012s sys 0m0.004s
#!/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 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.026s user 0m0.024s sys 0m0.000s