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

i.e. summing up the parents bottom-up with the min of two lower children?

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

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

Replies are listed 'Best First'.
Re^3: Brute force vs algorithm (PWC # 100) by choroba (Cardinal) on Feb 16, 2021 at 23:17 UTC
Yes, it is. I wasn't able to come up with a top down algorithm. `map{substr$_->[0],$_->[1]\|\|0,1}[\\|\|{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^ARGV,3]`	[reply] [d/l]
Re^4: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 16, 2021 at 23:45 UTC
Top-down is much harder. And when one doesn't do it right, one will just end-up visiting each cell anyway. That would have no benefit over this bottom-up approach. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^5: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 17, 2021 at 01:41 UTC
> And when one doesn't do it right, one will just end-up visiting each cell anyway. And I think there is no algorithm which can guaranty otherwise. consider this input `2 2 2 2 2 2 2 2 2 2 . . . . . 2s in between 2 2 . . 2 1 last row` [download] no matter which top-down search you apply, you can move the 1 in a way that it's only found at last try. Which means all cells needed to be visited.° update °) NB: complexity big O() calculations are about worst case (if not stated otherwise ) Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l]