Re: Brute force vs algorithm (PWC # 100)

From an algorithm point of view (no code), start from the bottom and work your way up. You know that on the penultimate row, the biggest value you can get on the "6" is 6+5, the biggest value you can get on the "4" is 4+7, and the biggest value you can get on the "9" is 9+7. Move up a row; the biggest value you can get on the "2" is the same whether you chose 2+6+5 or 2+4+7. The biggest on the "4" is 4+9+7. From the peak "1", the biggest you can get is from the 1+4+9+7.

So you have to visit each node once, but you never need to recurse or try every path.

edit: whoops, I described finding the maximum; thanks LanX. The idea is the same, just pick the smallest each time /edit

Comment on Re: Brute force vs algorithm (PWC # 100)

Replies are listed 'Best First'.
Re^2: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 15, 2021 at 18:38 UTC
You are describing the dual problem of maximizing a path instead minimizing it. ... but yeah starting with penultimate row will take advantage of the triangle structure. But you still need to visit all cells, branch-and-bound might help avoiding this. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^2: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 15, 2021 at 19:26 UTC
That's what you meant? :) ("abusing" List::Util::reduce() to window two neighboring cells) <Reveal this spoiler or all in this thread> `ok 1 ok 2 1..2` [download] edit That's `O(m) = O(n*2)` with `m:= #cells` , `n:= #rows` and `m = n(n+1)/2` Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} update added comments to code	[reply] [d/l] [select]
Re^3: Brute force vs algorithm (PWC # 100) by pryrt (Abbot) on Feb 15, 2021 at 19:56 UTC
Hmm, I didn't think it my method was as bad as the brute force, but it apparently is. So much for that idea. (it's how I would've solved it. Also, your implementation was better than mine would have been, even for my naive algorithm.)	[reply]
Re^4: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 15, 2021 at 20:17 UTC
> I didn't think it my method was as bad as the brute force It's not, brute (well the brutest) force will explore all possible path. The number of possible path grows much faster than m (I'd say exponentially)°. (... but with such a small triangle that's only of theoretical interest ) Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} °) sure it's `p = 2**(n-1)`	[reply] [d/l]

edit

update