wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> find the exit
        
(Message started by: almost dead on Jun 30th, 2007, 7:40am)
Title: find the exit
Post by almost dead on Jun 30th, 2007, 7:40am
You have an infinitely long (both sides) wall in front of you. You have to find the door(only one door) in least number of steps.design an algorithm for this.i found this question in a forum.please help
Title: Re: find the exit
Post by Iceman on Jun 30th, 2007, 10:30am
Well, if the door is pretty close to you and it glows in the dark, just walk away from the wall, instead of walking so that your hand always touches the wall.   :-/  ;)
Title: Re: find the exit
Post by Iceman on Jun 30th, 2007, 10:31am
Oh and my suggestion is even better if you have binoculars or telescope.  :P
Title: Re: find the exit
Post by Iceman on Jun 30th, 2007, 2:06pm
Or walk on your hands.  ::)
Title: Re: find the exit
Post by Iceman on Jun 30th, 2007, 2:07pm
Or drive in the car.  :o
Title: Re: find the exit
Post by Grimbal on Jul 2nd, 2007, 12:44am
It helps if you are in fact at the dead end of an infinitely long corridor.

Anyway, I think you cannot determine an optimal algorithm unless you know the probability distribution of the position of the door.
Title: Re: find the exit
Post by Hippo on Jul 4th, 2007, 1:19am
This is an example of on-line algorithms ... you cannot optimize complexity of your algorithm, but you can optimize the worst possible ratio of your algorithm and the optimal algorithm.

In this example you can obtain algorithm with complexity small constant + K times optimal algorithm. What is the best K, what is the algorithm?

(complexity is length of your path in this case)
Title: Re: find the exit
Post by Iceman on Jul 9th, 2007, 2:41pm
If exit has a neon sign then the exit finds you. Shut me up..  :-[
Title: Re: find the exit
Post by Hippo on Jul 11th, 2007, 7:54am
OK, My algorithm would be to mark 0 on the wall and go to position (-q)i on i-th walk. Optimization of q gives the best result for q being the golden ratio (1+sqrt(5))/2. The ratio of the path len to the optimal len (absolute value of the exit coordinate) is less than (q+1)q2/(q-1)<11.1.

(The unit should be choosen such that it is small enough not to stop during first two iterations ... 1 corresponds to "exit visibility").
Title: Re: find the exit
Post by Hippo on Jul 12th, 2007, 1:44am
The previous algorithm was not optimised well.
the worst ratio is less than (2q2+q-1)/(q-1). In that case better q would be 1+sqrt(3/2) with ratio < 9.09.

Oops ... actualy the minimum is for q=2 ... ratio = 9. So again natural geometric series are 2^n and golden ratio ^n.

(the traveled len for the worst case is 2q+2q2+2q3+...+2qd+1+qd + eps where the best len is qd+eps, in the previous post I have considered full last term qd+2)
Title: Re: find the exit
Post by srn347 on Aug 28th, 2007, 12:05pm
Algorithms cannot be infinite. The question is nonsensical.
Title: Re: find the exit
Post by towr on Aug 28th, 2007, 12:27pm

on 08/28/07 at 12:05:20, srn347 wrote:
Algorithms cannot be infinite. The question is nonsensical.
An algorithm can, theoretically, be infinite, but the question doesn't ask for an infinite algorithm.

Also, considering how many people made sense of the puzzle, it is rather presumptuous to claim it is nonsensical. If you don't understand it, just say it.
Title: Re: find the exit
Post by srn347 on Aug 28th, 2007, 12:56pm
Wikipedia mensions in the definition of algorithm that it is finite and terminates.
Title: Re: find the exit
Post by pex on Aug 28th, 2007, 1:00pm

on 08/28/07 at 12:56:59, srn347 wrote:
Wikipedia mensions in the definition of algorithm that it is finite and terminates.

Quoting from Wikipedia (http://en.wikipedia.org/wiki/Algorithm):

Quote:
Some writers restrict the definition of algorithm to procedures that eventually finish. (...) Others, including Kleene, include procedures that could run forever without stopping
Title: Re: find the exit
Post by towr on Aug 28th, 2007, 1:12pm

on 08/28/07 at 12:56:59, srn347 wrote:
Wikipedia mensions in the definition of algorithm that it is finite and terminates.
Really? Then wikipedia would be wrong; there is no reason an algorithm needs to terminate; and it can extend itself to grow infinitely in size (and theoretically you can defy it infinitely from the start).

Here's an algorithm that doesn't terminate:
#include <unistd.h>
int main()
{
while (true)
  fork();
}
Title: Re: find the exit
Post by srn347 on Aug 28th, 2007, 8:36pm
If it is infinite you don't have any use for it.
Title: Re: find the exit
Post by towr on Aug 29th, 2007, 1:02am

on 08/28/07 at 20:36:10, srn347 wrote:
If it is infinite you don't have any use for it.
You OS should in principle be able to run without termination. Is it useless? If it is, you may have installed windows. *zing*

If you're going to question everything people say, you might consider also questioning what you say yourself.
Title: Re: find the exit
Post by Sameer on Aug 29th, 2007, 7:43pm

on 08/28/07 at 20:36:10, srn347 wrote:
If it is infinite you don't have any use for it.


So is the algorithm for finding primes useless?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board