wu :: forums - Print Page


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

        riddles >> medium >> Searching for a friend
        
(Message started by: nothing_ on Mar 20^th, 2008, 7:12pm)

Title: Searching for a friend
Post by nothing_ on Mar 20^th, 2008, 7:12pm

You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.

Title: Re: Searching for a friend
Post by towr on Mar 21^st, 2008, 1:44am

[hide]Walk 2ⁱ miles up road i mod 4, until you meet your friend.
Or buy a pair of binoculars and look for him first.[/hide]

Title: Re: Searching for a friend
Post by pscoe2 on Mar 22^nd, 2008, 10:53pm

u just have to walk 1 mile in 1 direction come back goto another and like this check in all directions...
if you dont find him go double next time and keep doing this all the time till you find your friend
max distance travelled=4d+4*2*d/2+4*2*d/4.....+4*2*1=12d
so it is always O(d)

Title: Re: Searching for a friend
Post by johny_cage on Mar 25^th, 2008, 1:58am

@nothing_

this is not a CS problem, please post this type of puzzles into the Puzzles category...

Thank,..
Johny

Title: Re: Searching for a friend
Post by Hippo on Mar 25^th, 2008, 9:20am

on 03/25/08 at 01:58:34, johny_cage wrote:

@nothing_

this is not a CS problem, please post this type of puzzles into the Puzzles category...

Thank,..
Johny

Isn't it common problem in robotics? Just kidding :)

But the complexity issue is interesting here ... minimize the worst ratio of frends actual distance and your traveled path.
(Actually it's very simillar to walking around wall except there are 4 ways instead of just 2).

Title: Re: Searching for a friend
Post by Grimbal on Mar 25^th, 2008, 2:27pm

Regarding the "best worst case" question:
[hide]Assuming the searched distance increases by a factor r each time. You will start by infinitely small and infinitely many short trips until you almost reach your friend. The worst case is when you just arrive to an epsilon of your friend and turn back. The distance travelled is almost
... + 2d/r³ + 2d/r² + 2d/r + d
You then do a last round and travel
d + 2dr + 2dr² + 2dr³ + d
where you meet the friend.
Summing all that gives
D = 2d·r³·r/(r-1) + d
A minimum can be found at r = 4/3.
From there you can compute D/d = 539/27 or almost 20

If I haven't made a mistake somewhere.[/hide]

Title: Re: Searching for a friend
Post by Hippo on Mar 25^th, 2008, 3:45pm

Grimbal: good job, easily generalised result is for k-ways from the origin [hide](the wall has k=2 and optimal r was 2 minimising r²/(r-1)) .... minimise r^k/(r-1) ... 0=(kr^k-1(r-1)-r^k)/(r-1)^2 ... (k-1)r^k=kr^k-1 ... (k-1)r=k ... r=k/(k-1)[/hide]