Re^2: Brute force vs algorithm (PWC # 100)

That's what you meant? :)

("abusing" List::Util::reduce() to window two neighboring cells)

ok 1
ok 2
1..2
[download]

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}

added comments to code

Comment on Re^2: Brute force vs algorithm (PWC # 100) Select or Download Code

Replies are listed 'Best First'.
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]