wu :: forums - Print Page


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

        riddles >> cs >> Robot Collision, an idea.
        
(Message started by: -D- on Jul 28^th, 2002, 1:08am)

Title: Robot Collision, an idea.
Post by -D- on Jul 28^th, 2002, 1:08am

I saw this problem and was hooked. The problem is that when a robot lands, it doesn't know if the other robot is to the right or left of it. So you can't just send a robot to the right or left, you'd have a 25% chance of them hitting.

I've sort of figured out a recursive approach, basically you start say on the left. You recursively go right until the parachute, and then for every level of unrolling the recursion you take 2 steps to the right. Then you dp the same to the left. So they will essentially keep going from right to left increasing their distance, kind of a rubber band thing.

function to_the_right
go right
skip unless parachute
goto ttr_end
call to_the_right
LABEL: ttr_end
go right
go right
return

function to_the_left
go left
skip unless parachute
goto ttl_end
call to_the_left
LABEL: ttl_end
go left
go left
return

Then assuming these functions are programmed into memory, each bot starts like this:

LABEL: BOT_A
go left
call to_the_right
call to_the_left
goto BOT_A

LABEL: BOT_B
go right
call to_the_left
call to_the_right
goto BOT_B

I like it that one starts on the right and one on the left because they will "oscillate" at the same frequency. This garentees that they collide in the center. If they aren't out of phase like this, eventually one will hit the other parachute and probably start oscillating around it which would actually still work but this is cooler.

I've found a white paper on stack free recursion but I can't figure out how to implement my algorithm with it. The problem is that I'm currently using the only condition/conditional to define the limit of my recursion. I would need another form of conditional to control the unrolling.

You can implement functions with gotos but you don't have a return stack so you have to virtualize it some how. I think you can some how encode it in the bots location not being at the parachute but I haven't figured out how.

Anyone have a different idea?
-D-

Title: Re: Robot Collision, an idea.
Post by klbarrus on Jul 29^th, 2002, 10:53am

A simpler way to have the robots collide is to do this:

1) move them both the same direction, left, right, doesn't matter
2) one will find a parachute, and one won't
3) the one that finds a parachute knows it is "behind" the other robot, so it starts to move 2 spaces at a time. It will eventually catch the other robot.

So that works out to something like this:

move1space:
move right
skip unless parachute
goto move2spaces
goto move1space
move2spaces:
move right
move right
goto move2spaces

Title: Re: Robot Collision, an idea.
Post by -D- on Jul 29^th, 2002, 11:01am

AUGH!!! You're right. That's much easier.

Damn. I probably burned out a few hundred brain cells stretching for an answer.

If the stupid robots had return stacks, I would have loved to see them oscillate though!

Thanks though.
-D-

Title: Re: Robot Collision, an idea.
Post by Alex Harris on Jul 29^th, 2002, 11:52am

You're assuming that they execute each labelled sequence in a unit time. It's probably better to enforce slow motion as left, left, right, repeat then let the fast motion be left, left, repeat. This way we just need to assume that the robots travel at the same speed. We could account for any bounded speed differential between the two robots by streching this method, while if we don't have any bound on the relative speeds of the two robots then I think the problem is impossible.

Title: Re: Robot Collision, an idea.
Post by -D- on Jul 29^th, 2002, 12:00pm

I was thinking about that too when I saw his answer. But I assumed that we're talking about a mechanism that resembles a CPU so a conditional would take one cycle to evaluate. That being the case, looking for the parachute would take a cycle, even if the goto did not. Technically jumping/moving the program counter takes a cycle to complete also but with some hardware optimizations you could get around that. Especially in a simple CPU.

Also, they mentioned that there are 4 instructions in the set and each one takes a unit of time to execute. Goto and check for parachute are considered instructions so the algorithm would probably work. Otherwise, enforcing slow motion would be a minor addition to clean up the algorithm.
-D-

Title: Re: Robot Collision, an idea.
Post by Alex Harris on Jul 29^th, 2002, 2:34pm

Hrm. Somehow I missed that "each instruction takes 1 cycle" thing so actually its just fine as is. My mistake.

Title: Re: Robot Collision, an idea.
Post by Atticus on Aug 6^th, 2003, 2:16pm

Since every instruction takes one cycle, there's no need to worry about programming in two steps when in pursuit mode- the lack of parachute checks means that pursuit mode is inherently faster.

Hence:

<normal>
go left
skip next unless parachute
goto <pursuit>
goto <normal>
<pursuit>
go left
goto <pursuit>

which is probably the shortest program possible...?

Title: Re: Robot Collision, an idea.
Post by ChineseStunna on Feb 12^th, 2004, 2:24pm

Quote:

Well, since every insturction does take 1 cycle, this program, while shorter, would make the run-time efficiencies much worse than the original version, since you are spending a cycle "goto" per every go left command vs the other one going right twice before using "goto".

The optimal runtime solution would be to find out the memory size of the robot and make the "pursuit" function filled with "go right" or "go left" functions until the last line, which then would be the "goto" command :)

Title: Re: Robot Collision, an idea.
Post by grimbal on May 22^nd, 2004, 2:38pm

What if there are 3 robots?

Title: Re: Robot Collision, an idea.
Post by ChipBizGuy on Jul 16^th, 2004, 1:30pm

The riddle should be clarified to state that the robots are both initially facing the same direction (e.g. North). Otherwise, if they both move right, they may end up going in opposite directions. LOL. (I didn't realize this until after solving it, though.)

This is an interesting problem, but pretty easy once you realize the system only has one bit of data to work with.

BTW, the 'optimal' solution depends on whether you are measuring time or distance (or some other factor). Shortest distance to intercept would require slowing down the 'jog', not speeding up the 'ramming speed' section of the code.

Also interesting that there seems not to be any algorithm that guarantees to make the robots face each other when they collide.

Mark

Title: Re: Robot Collision, an idea.
Post by ChipBizGuy on Jul 16^th, 2004, 1:36pm

The same code works for N robots and N parachutes.

However, it is an interesting question whether there is a minimum number K of robots on an 'infinitely' long line that permit a different algorithm to always succeed. I think the answer is there is no such K. Even though you are adding memory to the system by adding additional parachutes, there is always one robot that doesn't get to use any of it. And the whole system is dictated by that 'least common denominator' robot. What do you think?

Title: Re: Robot Collision, an idea.
Post by Norman Furlong on Sep 20^th, 2004, 6:37pm

Interesting side note. I was asked a variation on this last year during a Microsoft interview, in which the two robots landed on the equator of an arbitrarily large moon. My thinking was along the line of the original poster (-D-) since you didn't know what direction the robot was facing and the "rubber band" approach was the first to come to mind. The interviewer failed me, giving the "correct" solution of doubling the speed upon finding a parachute. Can you find the flaw in the interviewer's solution?

Title: Re: Robot Collision, an idea.
Post by Grimbal on Sep 21^st, 2004, 4:42am

If the robots land at opposite points of the equator, and run along the equator, they will both find the other's parachute and both double speed.

If the starting position is symetrical and the robots are identical and deterministic, there is no way to break the symetry. The only place where they can join is at a pole.

Title: Re: Robot Collision, an idea.
Post by Norman on Sep 22^nd, 2004, 3:22pm

Right. It's probably beneath you good folk to figure out how much of the total solution space is missed by the interviewer's false answer, but I'm a newbie so I'll ask anyway. If you're insulted, please let me know. ::)

Title: Re: Robot Collision, an idea.
Post by Grimbal on Sep 22^nd, 2004, 9:24pm

There should be a probability of about 1/3 of robots chasing themselves endlessly. The exact value would depend on the distribution of moon sizes.

Title: Re: Robot Collision, an idea.
Post by Brad711 on Dec 17^th, 2004, 8:33pm

I don't get it.

Title: Re: Robot Collision, an idea.
Post by Norman Furlong on Dec 18^th, 2004, 9:19pm

Look down at this moon from a pole and draw a peace sign on it. The circumference of the sign is the equator. If the robots fall on the equator within the same portion of the sign (1/3 of world) AND are facing the same direction, they will chase each other continually with the Microsoft-blessed "correct" answer. So it fails in 1/6 of all cases.

Title: Re: Robot Collision, an idea.
Post by william wu on Dec 19^th, 2004, 3:23pm

I computed only 1/5 chance of failure for the Microsoft solution; but I guess you guys were just doing rough approximations. (Unless I miscomputed something.)

Let L be the shortest initial distance between the two robots along the equator, and let the equator have unit circumference. Note that L [le] 1/2.

Initially, both robots move in the same direction (clockwise or counterclockwise). Let A denote the robot that finds B's parachute. The moment B's parachute is found, robot B still has 1-2L distance to travel before finding A's parachute. Robot A increases his movement speed by a factor of N, and thus has an equivalent distance of L/N units to travel before colliding with robot B. To avoid infinite chasing, we want the robots to collide before both parachutes are found, and thus the necessary condition is

L/N < 1-2L [to] L < N/(2N + 1)

As N[to][infty], we approach L < 1/2, which is a premise from the start. When N is 2, we have L < 2/5, which is satisfied with probability 4/5.

Title: Re: Robot Collision, an idea.
Post by Grimbal on Dec 20^th, 2004, 6:12am

on 12/19/04 at 15:23:06, william wu wrote:

Robot A increases his movement speed by a factor of N, and thus has an equivalent distance of L/N units to travel before colliding with robot B.

That would be if B stopped there.

Title: Re: Robot Collision, an idea.
Post by Jayant Chauhan on Nov 13^th, 2005, 8:41pm

Hey,
For the globe thing, cant we just move them in the opposite directions ;D. Or are you guys just suggesting a generic solution ?!

Title: Re: Robot Collision, an idea.
Post by BenVitale on Jun 30^th, 2008, 7:09pm

on 07/29/02 at 10:53:27, klbarrus wrote:

I realize it's an old thread and all, i have a script and i would like to read your opinions

var x = 1;
do
{
// Head x spaces. alternate between going left and right.
for(var y = x; y > 0; y--)
{
if(x is ODD)
GO LEFT
else
GO RIGHT

// If we find a parachute, let's continue in whatever direction we were headed.
if( found parachute)
{
while(TRUE)
{
if(x is ODD)
GO LEFT
else
GO RIGHT
}
}
}

INCREMENT X
}while(TRUE)

the idea is go left 1, right 2, left 3, right 4, etc. until either a collision occurs (won't happen if both robots are facing the same direction when they start, since they'll move in sync) or a parachute is found, at which point in time the robot continues moving in that direction. The other robot will eventually double back and collide.

One obvious issue with this algorithm is it would assume you have an infinite amount of memory (presumably x needs to be able to represent infinitely large numbers, which is sort of an issue). But I think that's OK, given that the problem also assumes the line is infinite in length, which is equally implausible.

Something tells me the first is more efficient.