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)
Impostiamo i numeri dentro alla matrice \(M\). Ci interessa trovare al somma massima ottenibile percorrendo \(M\) da cima a fondo e spostandoci con passi adiacenti. L'idea quindi è di partire dal numero in cima e scendere calcolando tutti i possibili valori che possiamo ottenere sommando quel numero ai numeri a lui adiacenti nella riga sotto, ovvero quello in basso a sinitra e quello in basso a destra (nella rappresentazione originale a triangolo). Di questi risultati, ci salviamo (in un'altra matrice \(M_\text{sum}\)) il massimo tra di loro, ovvero quando ad una cella possono contribuire diversi "percorsi" di somme selezioniamo quello che conduce alla somma più alta. Alla fine prendiamo il massimo valore che incontriamo sulla sua ultima riga: questo corrisponderà infatti al valore di somma massimo ottenibile. L'idea funziona perché è come se filtrassimo di volta in volta l'informazione contenuta in M: se siamo alla riga 5 non ci interessano precisamente tutti i numeri nelle righe dalla 1 alla 4, ma piuttosto solo il loro effetto, cioè le somme più alte che loro sono riusciti a generare.
Ad esempio, nel caso che segue partiamo con la matrice \(M\) che nella prima riga contiene il numero 75. La seconda riga di \(M_\text{sum}\) conterrà quindi 75+95 e 75+64, senza troppi pensieri. La terza riga diventa ora interessante perché si aprono diversi percorsi. Ad esempio, nella prima cella di \(M_\text{sum}\) mettiamo il massimo tra 75+95+17 (il percorso sempre dritto verso il basso) e 75+64+17 (il percorso che al secondo step devia verso destra). Allo stesso modo si procede nelle altre celle.
Possiamo anche provare a ricostruire il percorso della soluzione scorrendo \(M_\text{sum}\) dal basso verso l'alto e cofrontandola con \(M\).
cfr = maximum(Msum[end,:])
# se siamo in fondo il target è il massimo valore, la somma più alta
j_focus = argmax(Msum[end,:])
for i in R:-1:1
if i<R
global cfr = cfr - M[i+1,j_focus]
# altrimenti il target diventa la somma parziale meno il numero che c'era in M
global j_focus = findfirst(x -> x==cfr, Msum[i,:])
end
for j in 1:C
if j==j_focus
print(rpad("[$(M[i,j])]",7, " "))
else
print(rpad(M[i,j],7, " "))
end
end
println()
end
Dicevo "provare" perché questo metodo a volte può sbagliare, dato che opera su confronti aritmetici, che possono risultare ambigui in caso ci siano più numeri che soddisfano la condizione. Perciò occorre invece aggiornare la funzione sopra che assembla la soluzione per tenere anche traccia dei predecessori usati nel percorso ottimale.
parent = zeros(Int,R, C)
for i in 2:R
for j in 1:i
if j == 1
Msum[i,j] = Msum[i-1,j] + M[i,j]
parent[i,j] = j
else
# sciogliamo il max tra i due casi per aggiornare correttamente parent
if Msum[i-1,j] > Msum[i-1,j-1]
Msum[i,j] = Msum[i-1,j] + M[i,j]
parent[i,j] = j
else
Msum[i,j] = Msum[i-1,j-1] + M[i,j]
parent[i,j] = j-1
end
end
end
end
j_focus = argmax(Msum[end, :])
path = Int[]
path_indices = zeros(Int,R)
for i in R:-1:1
push!(path, M[i,j_focus])
global path_indices[i] = j_focus
global j_focus = parent[i,j_focus]
end
@show path sum(path)
