# Problem 67 – Using an efficient algorithm find the maximal sum in a triangle

In order to solve this problem, I tried to use the solution of problem 18, however that didn’t work… Therefore, I started by looking into some Haskell libraries and I came across the *zipWith* function. I used it before, however I didn’t remember it when I solved problem 18. The truth is that by using it together with the *foldr1* function, it simplified the solution drastically. Here is my solution:

import Examples total67 = head . foldr1 f where f x1 x2 = let l = zipWith max (init x2) (tail x2) in zipWith (+) x1 l

The triangles were saved inside another module (Examples). In order to save the triangle used in this problem, I used a small python script to insert a list syntax into the text file:

o = open("triangle.hs","a") i = open("triangle.txt") for line in open("triangle.txt"): line = line.replace(" ",",") line = line.strip() line = " [" + line + "],\n" o.write(line) o.close()

GHCi executes this function in (0.08 secs, 34504884 bytes).

Advertisements

Leave a Comment