# Problem 18

In order to solve the 18th Euler problem, I used a lookahead function that tries to find out which position to choose in the current level of the triangle based on the next level. It also uses the last position used in order to pick the right values in the next levels of the triangle.

First, I defined both triangles using a list of lists, as one can see below.

import List type Triag = [[Int]] triangle :: Triag 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] ] triangleExample :: Triag triangleExample = [ [3], [7,4], [2,4,6], [8,5,9,3] ]

Then, I created a few utility functions that I thought I could use, such as *maxValue*, which returns the position of the best number among 2; the *indexOf*, which btw I am not very proud of, that returns the position of a given number in a list (note: although one should never define such a function like that, I am sure I will find an element in that list, so the result will always be correct); and finally *maxOf*, which *tells* the *lookahead* function which position it should return based on the next level of the triangle.

Here are the definitions:

maxValue :: Int -> --position [Int] -> --list Int maxValue p l = let a = (!!) l p b = (!!) l (p+1) in case a >= b of True -> p False -> p+1 indexOf :: Int -> --element [Int] -> --list Int--position in the listindexOf n l = case (elemIndex n l) of Nothing -> 0 Just x -> x maxOf l = let k = unzip l m = (maximum . fst) k n = indexOf m (fst k) in (!!) (snd k) n

The lookahead calculates the sum of the relevant values in the current and next level of the triangle, and returns the best position to choose:

lookahead :: [Int] ->-- Line 1[Int] ->-- Line 2Int ->-- Column valueInt-- Column position where to go nextlookahead l1 l2 c = let x1_l1 = (!!) l1 c x2_l1 = (!!) l1 (c+1) v1 = (x1_l1 + (!!) l2 c,c) v2 = (x1_l1 + (!!) l2 (c+1),c) v3 = (x2_l1 + (!!) l2 (c+1),c+1) v4 = (x2_l1 + (!!) l2 (c+2),c+1) l = [v1,v2,v3,v4] in maxOf l

Finally, it was a matter of assembling everything:

total_max :: Triag ->-- TriangleInt ->-- Next columnInt-- maximum totaltotal_max (l1:l2:l3:ls) n = let next = lookahead l2 l3 n val = (!!) l1 n in val + total_max (l2:l3:ls) next total_max (l1:l2:[]) n = let val = (!!) l1 n nextval = maxValue n l2 in val + (!!) l2 nextval total = total_max triangle 0

The interpreter returned the following output, when I executed the *total* function:

(0.03 secs, 4125124 bytes)

Although it is not a pretty solution, it solved the problem relatively fast. Now I will try it in problem 67, where there are 2^{99} possible routes!