Project Euler Problem 18 in F#

2011 brings us yet another Project Euler problem to tackle: this time is Problem 18, one of the most interesting that I've solved so far:

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

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

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)

Analysis

This problem is easily solved resorting to dynamic programming, which we can loosely describe as decomposing the overall problem into easier sub-problems and combining their solutions to find the final answer.

In our case, if we consider the number associated with each node of the triangle as a cost, the overall problem can be expressed as finding the path with maximum cost from the upper vertex to the bottom row. A generic sub-problem would be the cost to reach the bottom row from a generic node at position i,j.

Given the cost c_{i,j} of passing through a given node and the cost C_{i,j} of reaching the bottom row from that particular node, we can define the following truth:

    \[C_{i,j} = c_{i,j} + max(C_{i+1,j}, C_{i+1,j+1})\]

or, in other words, from each node i,j the cost of reaching the bottom is equal to the cost of the node itself plus the maximum path between one of the two adjacent nodes from the row below.

Let's confirm why this is the case with the help of the following figure: consider for example the first node from the left in the fourteenth (last-but-one) row (having cost 63): from there you can move to the bottom either going to node 04 or node 62. Clearly, if we want to pick the highest cost, we need to pick 62 (and we mark this choice with a grey line). The overall cost to reach the bottom from that node is thus 63 + max (04, 62) = 125.

Let’s consider now the second node from that row (66). From there, we have to choose between node 62 and 98: the highest cost path from there is thus 66 + max(62, 98) = 164. We can continue for all the nodes in the row to find the highest cost path from each node; the solution to such sub-problems is indicated in gray close to each node.

ProjectEuler18_2rows

Having solved all sub-problems for row 14, we can now consider the row immediately above. In the following figure, I have replaced row 14 with the solutions of the sub-problems that we had just solved; the row above is row 13. Please note how we don’t care about row 15 anymore: its contribution to the overall problem is already captured in each sub-problems’ solution for row 14! Hence, we proceed in a similar way to solve the sub-problems for the row 13 just as we did for row 14:

ProjectEuler18_2rows

We continue to follow a similar pattern moving upwards row after row, until we reach the tip of the triangle, always considering two rows at a time.

Solution

#light

let a = Array2D.zeroCreate<int> 15 15

a.[0,0] <- 75
a.[1,0] <- 95
a.[1,1] <- 64
a.[2,0] <- 17
a.[2,1] <- 47
a.[2,2] <- 82
a.[3,0] <- 18
// other initializations omitted for clarity
// full listing available on Github
// (https://github.com/stefanoric/YAPEFSHARP)
a.[14,10] <- 38
a.[14,11] <- 53
a.[14,12] <- 60
a.[14,13] <- 04
a.[14,14] <- 23 

let costs = Array2D.zeroCreate<int> 15 15

// costs for bottom row is the same as bottom row values
Array2D.blit a 14 0 costs 14 0 1 15 |> ignore

let max a b = if a > b then a else b

for i in 13 .. -1 .. 0 do
    for j in 0 .. i do
        costs.[i,j] <- a.[i,j] + max costs.[i+1,j] costs.[i+1, j+1]
        
let result () =
    costs.[0,0]

Most of the code for this solution is needed just to initialize the two dimensional array containing the triangle. For reading convenience, I have skipped most of the uninteresting rows, but you can find the complete solution on Github.

So, we have a matrix (2D array) for the cost of each nodes and another matrix for the solutions of the sub-problems associated to each node. Trivially, the costs and the solutions coincide for the bottom row (note the handy Array2D.blit function to copy a whole row from one matrix to the other).

Then, with a loop we move backward from the last-but-one row up to the tip of the triangle calculating the sub-problems solutions as explained above.

kick it on DotNetKicks.com

Shout it

This entry was posted in F# and tagged , , . Bookmark the permalink.
  • Pingback: Project Euler Problem 18 in F#

  • Pingback: Tweets that mention Project Euler Problem 18 in F# | Stefano Ricciardi -- Topsy.com

  • HUZ

    Yours is a very un-idiomatic, imperative solution. More functional is this:

    let maxTriPath () =
        let rec sumRows ra rb acc =
            match ra with
                | []          -> []   // should never happen
                | [a]         -> List.rev acc
                | a :: b :: r ->
                    let rec c = List.head rb
                    and d = List.tail ra
                    and e = List.tail rb
                    and f = (if a > b then a else b) + c in
                        sumRows d e (f :: acc)
        and iter l =
            match l with
                | []            -> []   // should never happen
                | [la]          -> la
                | la :: lb :: r -> iter ((sumRows la lb []) :: r)
        in
            [[04; 62; 98; 27; 23; 09; 70; 98; 73; 93; 38; 53; 60; 04; 23];
             [63; 66; 04; 68; 89; 53; 67; 30; 73; 16; 69; 87; 40; 31];
             [91; 71; 52; 38; 17; 14; 91; 43; 58; 50; 27; 29; 48];
             [70; 11; 33; 28; 77; 73; 17; 78; 39; 68; 17; 57];
             [53; 71; 44; 65; 25; 43; 91; 52; 97; 51; 14];
             [41; 48; 72; 33; 47; 32; 37; 16; 94; 29];
             [41; 41; 26; 56; 83; 40; 80; 70; 33];
             [99; 65; 04; 28; 06; 16; 70; 92];
             [88; 02; 77; 73; 07; 63; 67];
             [19; 01; 23; 75; 03; 34];
             [20; 04; 82; 47; 65];
             [18; 35; 87; 10];
             [17; 47; 82];
             [95; 64];
             [75]]
            |> iter
    
    let _ =
        let sw = System.Diagnostics.Stopwatch () in
        sw.Start ();
        let r = maxTriPath () in
        sw.Stop ();
        System.Console.WriteLine ("Result: {0}", r);
        System.Console.WriteLine ("Time elapsed: {0}", sw.Elapsed);
        System.Console.WriteLine ("Ticks elapsed: {0}", sw.ElapsedTicks)
    
  • Anonymous

    @HUZ:disqus, yes, it can be that it’s not idiomatic, I am just learning the language and I have no prior experience with functional languages.

  • HUZ

    Hello Stéfano,

    I have not programmed much since dropping out of University (I work in tech support these days, and am trying myself at programming in a few free minutes to exercise my brain in something different) but my introductory programming class was using Scheme and largely based on the book ‘Structure and Interpretation of Computer Programs.’ It teaches you how to attack a number of problem types in a functional way, and can be easily transported to F#. Perhaps you should read it when you have some time.

    One of the most basic things I remember from it is that any imperative loop can be modeled using a recursive function, which is what I did, since the F# library functions for list processing did not quite seem to fit the bill here.

    By the way, my solution returns the final value in a list; add ‘|> List.head’ after ‘|> iter’ to extract the value only.

  • Anonymous

    @9e07fb6f52ee2b392c3ed188964cc564:disqus I have a pdf version of that book somewhere in my Kindle. However since changing my job earlier this year I’ve had less time to play around with F# and functional programming in general (as you can see, this was the last blog post on the topic….) :(. I hope catch up in the near future (possibly by next fall).

  • Anonymous

    @9e07fb6f52ee2b392c3ed188964cc564:disqus I have a pdf version of that book somewhere in my Kindle. However since changing my job earlier this year I’ve had less time to play around with F# and functional programming in general (as you can see, this was the last blog post on the topic….) :(. I hope catch up in the near future (possibly by next fall).

  • http://www.asia-gazette.com/ Dani

    There are two mistakes in the image ‘ProjectEuler18_2rows_thumb.png’

    The max between 68 and 27 or 68 and 23 is 95.
    The max between 87 and 53 or 87 and 60 is 147.

    But great explanation! This helps a lot!

  • http://www.asia-gazette.com/ Dani

     And the last image should read:
    [255, 235, 154, 150, 140, 179, 256, 209, 224, 172, 174, 176, 148]