Project Euler — problem 18

The 18th Euler problem is sorta a route finding problem. It has occupied my mind for two days. Finally I came up to a clever solution.

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

Firstly, allow me to introduce the brute force algorithm for this particular problem. Let’s calculate from the top to the bottom. In the toppest level, we get only one number 75. In the 2nd, we have two possible numbers, 95 and 64, to add on 75; if we stop here, we could easily find 75+95 is bigger than 75+64 but we must go on. In the third level, we have another two possible numbers for each previous sum number, so we got four results, i.e. 75+95+17, 75+95+47, 75+64+47, 75+64+82. To this end, we can’t tell which is the biggest by directly comparing the 3rd-layer numbers. And for each level, there are always two choices to add to each previous sum result… So there will be 2^14, which is 16384, possible route. Big O is 2^n. Obviously, there must be some better ways to solve this!

Here comes the better idea which took me two days. Still, let’s start from the top. At the 1st level, one number 75. At the 2nd level, two possibilities, 75+95=170 and 75+64=139 and let’s keep them for a while. At the 3rd level (this is the KEY step), there are four possibilities: for the leftmost 17 we get 170+17 and for the rightmost 82 we get 139+82, but for the middle 47 we can simply keep 170+47 while discard 139+47 due to 170>139. Therefore, we rule out one route at the 3rd level. Let’s move on to the 4th level. Still, for the leftmost we get 187+18, for the rightmost we get 221+10, and for the middle left 35 we keep 217+35 (because 217>187) and for the middle right 87 we keep 221+87 (221>217). In the 4th level, we keep only four results and in the next level, we will keep five results by simply comparing two adjacent sum results. By this means, we improve the original O(2^n) algorithm to a new O(n^2) algorithm. If you find it’s a little hard to understand, you could try another way — bottom up.

1
2
3
4
5
6
7
8
9
10
11
12
13

n <- 15
chart <- read.table("chart", sep = " ", fill = NA, col.names = 1:n)
chart <- as.matrix(chart)
chart[2, 1:2] <- chart[2, 1:2] + chart[1, 1]
for (i in 3:n) {
  chart[i, 1] <- chart[i, 1] + chart[(i - 1), 1]
  chart[i, i] <- chart[i, i] + chart[(i - 1), (i - 1)]
  for (j in 2:(i - 1)) {
    chart[i, j] <- chart[i, j] + max(chart[(i - 1), (j - 1):j])
  }
}
result <- max(chart[n, ])
cat("The result is:", result, "\n")