Project Euler in F#: Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, find the maximum total from top to bottom of the triangle below:

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

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Like problem 14, this problem, while brute forcable, just screams DP / memoization. Since I played around with memoization for 14, I decided to try a classic ‘C’ style dynamic program this time around.

module Problem18 =
    open System
    let fileName = @"C:\Users\d\Documents\Visual Studio 2010\Projects\Euler\Euler\euler 18.txt"

    let aData = System.IO.File.ReadAllLines(fileName) |> Array.rev |>  Array.map (fun l ->  l.Split([|' '|], System.StringSplitOptions.RemoveEmptyEntries) |> Array.map System.Int32.Parse)
    let size = aData.Length
    let maxTable = Array2D.init size size (fun i j -> if j < size - i then aData.[i].[j] else 0)

    for i in 1 .. size - 1 do
        for j in 0 .. size - i - 1 do
            maxTable.[i,j] <- maxTable.[i,j] + (max maxTable.[i-1,j] maxTable.[i-1,j+1])
    printfn "Answer: %i" maxTable.[size-1, 0]

There’s no reason to use a 2D array here, but since I already learned how to use 1D arrays, I figured I might as well try a 2D array, to learn something new.

Advertisements
Project Euler in F#: Problem 18

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