Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

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

by LanX (Saint)
on Feb 17, 2021 at 01:41 UTC ( [id://11128485]=note: print w/replies, xml ) Need Help??


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

> 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

In Section Meditations

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://11128485]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others wandering the Monastery: (1)
As of 2024-04-25 04:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found