in reply to Re^3: Brute force vs algorithm (PWC # 100)
in thread Brute force vs algorithm (PWC # 100)

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

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

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

In Section Meditations