Author |
Topic: find the exit (Read 2895 times) |
|
almost dead
Newbie
Posts: 17
|
 |
find the exit
« on: Jun 30th, 2007, 7:40am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
alien2
Uberpuzzler
Gender: 
Posts: 6991
|
|
Re: find the exit
« Reply #1 on: Jun 30th, 2007, 10:30am » |
Quote Modify
|
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.  
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6991
|
|
Re: find the exit
« Reply #2 on: Jun 30th, 2007, 10:31am » |
Quote Modify
|
Oh and my suggestion is even better if you have binoculars or telescope. 
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6991
|
|
Re: find the exit
« Reply #3 on: Jun 30th, 2007, 2:06pm » |
Quote Modify
|
Or walk on your hands. 
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6991
|
|
Re: find the exit
« Reply #4 on: Jun 30th, 2007, 2:07pm » |
Quote Modify
|
Or drive in the car. 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: find the exit
« Reply #5 on: Jul 2nd, 2007, 12:44am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: find the exit
« Reply #6 on: Jul 4th, 2007, 1:19am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6991
|
|
Re: find the exit
« Reply #7 on: Jul 9th, 2007, 2:41pm » |
Quote Modify
|
If exit has a neon sign then the exit finds you. Shut me up.. 
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: find the exit
« Reply #8 on: Jul 11th, 2007, 7:54am » |
Quote Modify
|
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").
|
| « Last Edit: Jul 11th, 2007, 7:59am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: find the exit
« Reply #9 on: Jul 12th, 2007, 1:44am » |
Quote Modify
|
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)
|
| « Last Edit: Jul 12th, 2007, 7:54am by Hippo » |
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: find the exit
« Reply #10 on: Aug 28th, 2007, 12:05pm » |
Quote Modify
|
Algorithms cannot be infinite. The question is nonsensical.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the exit
« Reply #11 on: Aug 28th, 2007, 12:27pm » |
Quote Modify
|
on Aug 28th, 2007, 12:05pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: find the exit
« Reply #12 on: Aug 28th, 2007, 12:56pm » |
Quote Modify
|
Wikipedia mensions in the definition of algorithm that it is finite and terminates.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: find the exit
« Reply #13 on: Aug 28th, 2007, 1:00pm » |
Quote Modify
|
on Aug 28th, 2007, 12:56pm, srn347 wrote:| Wikipedia mensions in the definition of algorithm that it is finite and terminates. |
|
Quoting from Wikipedia:
Quote:| Some writers restrict the definition of algorithm to procedures that eventually finish. (...) Others, including Kleene, include procedures that could run forever without stopping |
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the exit
« Reply #14 on: Aug 28th, 2007, 1:12pm » |
Quote Modify
|
on Aug 28th, 2007, 12:56pm, 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();
}
|
| « Last Edit: Aug 28th, 2007, 1:14pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: find the exit
« Reply #15 on: Aug 28th, 2007, 8:36pm » |
Quote Modify
|
If it is infinite you don't have any use for it.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: find the exit
« Reply #16 on: Aug 29th, 2007, 1:02am » |
Quote Modify
|
on Aug 28th, 2007, 8:36pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: find the exit
« Reply #17 on: Aug 29th, 2007, 7:43pm » |
Quote Modify
|
on Aug 28th, 2007, 8:36pm, srn347 wrote:| If it is infinite you don't have any use for it. |
|
So is the algorithm for finding primes useless?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print