Stefano Ricciardi

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 of passing through a given node and the cost of reaching the bottom row from that particular node, we can define the following truth:

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.

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:

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.

Project Euler problem 17 turned out to be quite an easy one.

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Solution

The solution this time is almost trivial:

• "Zero" is considered to have 0 length (it will be obvious later on why this is the case)
• Numbers from 1 to 19 have their own unique names (i.e. they are not composed by putting together more words)
• Numbers from 20 to 99 are combined putting together a word like "thirty" and a number from 0 to 9. If the number is zero, we don't add anything (we don't say "twenty and zero")
• Numbers from 100 to 999 are combined putting together a words like "two hundred and" plus a number from 0 to 99 composed as explained above. Exact multiples of 100 are exception in that they don't have another trailing number (again, we don't say "two hundred and zero").

#light

let thousand    = "oneThousand"
let hundred     = "hundred"
let hundred_and = "hundredAnd"

let zero_to_nine = new System.Collections.Generic.Dictionary<int, string="">()
zero_to_nine.[0] <- ""
zero_to_nine.[1] <- "one"
zero_to_nine.[2] <- "two"
zero_to_nine.[3] <- "three"
zero_to_nine.[4] <- "four"
zero_to_nine.[5] <- "five"
zero_to_nine.[6] <- "six"
zero_to_nine.[7] <- "seven"
zero_to_nine.[8] <- "eight"
zero_to_nine.[9] <- "nine"

let ten_to_nineteen =  new System.Collections.Generic.Dictionary<int, string="">()
ten_to_nineteen.[10] <- "ten"
ten_to_nineteen.[11] <- "eleven"
ten_to_nineteen.[12] <- "twelve"
ten_to_nineteen.[13] <- "thirteen"
ten_to_nineteen.[14] <- "fourteen"
ten_to_nineteen.[15] <- "fifteen"
ten_to_nineteen.[16] <- "sixteen"
ten_to_nineteen.[17] <- "seventeen"
ten_to_nineteen.[18] <- "eighteen"
ten_to_nineteen.[19] <- "nineteen"

let twenty_to_ninety = new System.Collections.Generic.Dictionary<int, string="">()
twenty_to_ninety.[20] <- "twenty"
twenty_to_ninety.[30] <- "thirty"
twenty_to_ninety.[40] <- "forty"
twenty_to_ninety.[50] <- "fifty"
twenty_to_ninety.[60] <- "sixty"
twenty_to_ninety.[70] <- "seventy"
twenty_to_ninety.[80] <- "eighty"
twenty_to_ninety.[90] <- "ninety"

let len s = String.length s

let calculate_letters_under_one_hundred n =
    match n with
        | x when x < 10 -> len zero_to_nine.[x]
        | x when x < 20 -> len ten_to_nineteen.[x]
        | x when x < 100 -> len twenty_to_ninety.[((x / 10) * 10)] + len zero_to_nine.[(x % 10)]
        | _ -> failwith "Number is too big!"

let calculate_letters n =
    match n with
        | x when x < 100 -> calculate_letters_under_one_hundred x
        | x when ((x < 1000) && (x % 100 = 0)) -> len zero_to_nine.[(x / 100)] + len hundred
        | x when x < 1000 -> len zero_to_nine.[(x / 100)] + len hundred_and +  calculate_letters_under_one_hundred (x % 100)
        | 1000 -> len thousand
        | _ -> failwith "Numer is too big!"

let all_letters_up_to n =
    List.sumBy (fun i -> calculate_letters i) [1..n]