# Project Euler Problems 18 and 67

Project Euler Problem 18 and Project Euler Problem 67 can be solved with the same code just operating on different data.

When looking at a random row of the triangle it can be noticed that each constituing number, most left and most right being excluded, participate in exactly two routes. If we already know max sums for each of these two routes it is easy to find the max sum for the value under consideration. Most left and most right values are even easier: max sum for them is sum of value and max sum of previous most left (or most right).

To simplify pick of max sum let’s do the following: let’s convert each next row that we’re going to fold into row of tuples representing both collected so far sums. For the most left and most right values let’s add zeros from left and from right effectively making # of tuple pairs equal to # of values of the next row. Algorithm ends when only one row left, the answer is max element in this row.

open System.IO open System let getData (path: string) = [ use sr = new StreamReader(path) while not sr.EndOfStream do yield (sr.ReadLine().Split(' ') |> Array.map (fun x -> int x) |> Array.toList) ] let pair l = List.zip (0::l) (l @ [0]) let maxpath curr next = List.map2 (fun (x,y) z -> max (x+z) (y+z)) curr next let rec findMaxPath l = match l with | first::second::t -> findMaxPath ((maxpath (pair first) second) :: t) | _ -> List.max (List.head l) let problem018 () = findMaxPath (getData @"..\..\..\Datafiles\Problem018.data") let problem067 () = findMaxPath (getData @"..\..\..\Datafiles\Problem067.data")