Skip to content

Project Euler Problems 18 and 67

October 27, 2011

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")
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: