in reply to Re: Brute force vs algorithm (PWC # 100) (updated: visualisation)
in thread Brute force vs algorithm (PWC # 100)

it's a variation of this idea Re^2: Brute force vs algorithm (PWC # 100), right?

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]
      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]
        > 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]

In Section Meditations