We are given this triangle: 3 7 4 2 4 6 8 5 9 3

If we begin at the top, and move to adjacent numbers in the row below, that is from 3 in the top, we can move to 7 or 4. If we chose 4, we can move to 4 or 6 in the third row.

Continuing to the bottom, and adding the numbers on the path, what is the maximum sum we can get?

The trick is to look at the second to last row. If we are at the number 4, we can either chose 5 or 9, to get to the bottom. No matter what the sum of the path that led us to the number 4 in the third row, we should chose 9 to maximise the sum.

Therefore, the effective value of reaching 4 in the third row, is to reach a value of 13. We calculate new values in the third row as the effective values based on the binary choice bringing us to row 4. We now have a new second to last row, and repeat.

3 7 4 2 4 6 8 5 9 3

-> 3 7 4 10 13 15

-> 3 20 19

->

23

Having figured this out, two steps remain. Store the triangle in some datastructure. Write a function that returns the last row

Tricket er at i stedet for at finde den største sum der starter i toppen. Så fjerner vi den øverste linie. Og behandler resten som to trekanter, en med 95 og en med 64 i toppen. Vi finder den størst mulige sum for hver af de trekanter. Den største af de to, lagt til 75 er den største sum. Det kan vi gentage.

Men vi kan også tage det nede fra. Fjern den nederste række, og find den største sum i den resterende trekant. Hvis den involverer tallet 66, vil vi skulle lægge enten 62 eller 98 til for at få den største samlede sum.

Det kan vi gøre iterativt. Kig på næstnederste linie. Hvis vi følger en sti der ender med tallet 63 i næstnederste linie - så kan vi kun tilføje 04 til den. Det er ækvivalent til at der i stedet for 63 skal stå 67. Følger vi en sti der ender med tallet 66, skal vi enten lægge 62 eller 98 til. Vi vælger 98, for det vil maksimere den samlede sum. Så vi kan kollapse de to nederste linier til en ny nederste linie.

Lad os prøve det.

næst <- c(63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31)
nederst <- c(04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23)

position 1 i næst, kan kun pege på position i nederst. Position 2 i næst, kan kun pege på position 2 og 3 i nederst

Så vi kan skrive en funktion, der kollapser de to nederste til en ny nederst:

# b er den nederste. a er den næstnederste.
# funktionen kollapser de to til en ny nederste række.
kollaps <- function(a, b ){
output <- numeric()
for(i in 1:length(a)){
  output[i] <- max(a[i]+b[i], a[i]+b[i+1])
}
output}

Og det betyder at den nye nederste er:

kollaps(næst, nederst)
##  [1] 125 164 102  95 112 123 165 128 166 109 122 147 100  54

Lad os få data ind i noget vi kan arbejde med:

trekant <- "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"
trekant <- str_split(trekant, "\\n") %>% unlist() %>% 
  str_split(" ") %>% 
  lapply(as.numeric)

Og så kaster vi det hele sammen:

nederst <- 1000
while(nederst > 2){
  nederst <- length(trekant)
  trekant[[nederst - 1]] <- kollaps(trekant[[nederst-1]], trekant[[nederst]])
  trekant[[nederst]] <- NULL  
}
answer <- unlist(trekant)