Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

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

by choroba (Archbishop)
on Feb 16, 2021 at 23:17 UTC ( #11128480=note: print w/replies, xml ) Need Help??


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

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]

Replies are listed 'Best First'.
Re^4: Brute force vs algorithm (PWC # 100)
by LanX (Cardinal) 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

      > 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

      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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11128480]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2021-04-18 16:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?