Author |
Topic: Robot Collision, an idea. (Read 5671 times) |
|
-D-
Guest
|
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-
|
|
 IP Logged |
|
|
|
klbarrus
Newbie
Posts: 29
|
 |
Re: Robot Collision, an idea.
« Reply #1 on: Jul 29th, 2002, 10:53am » |
 Quote  Modify
|
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
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: Robot Collision, an idea.
« Reply #2 on: Jul 29th, 2002, 11:01am » |
Quote Modify
 Remove
|
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-
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
|
Re: Robot Collision, an idea.
« Reply #3 on: Jul 29th, 2002, 11:52am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: Robot Collision, an idea.
« Reply #4 on: Jul 29th, 2002, 12:00pm » |
Quote Modify
Remove
|
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-
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
|
Re: Robot Collision, an idea.
« Reply #5 on: Jul 29th, 2002, 2:34pm » |
Quote Modify
Remove
|
Hrm. Somehow I missed that "each instruction takes 1 cycle" thing so actually its just fine as is. My mistake.
|
|
IP Logged |
|
|
|
Atticus
Guest
|
|
Re: Robot Collision, an idea.
« Reply #6 on: Aug 6th, 2003, 2:16pm » |
Quote Modify
Remove
|
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...?
|
|
IP Logged |
|
|
|
ChineseStunna
Newbie
Posts: 4
|
|
Re: Robot Collision, an idea.
« Reply #7 on: Feb 12th, 2004, 2:24pm » |
Quote Modify
|
Quote: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...?
|
|
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 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Robot Collision, an idea.
« Reply #8 on: May 22nd, 2004, 2:38pm » |
Quote Modify
|
What if there are 3 robots?
|
|
IP Logged |
|
|
|
ChipBizGuy
Guest
|
|
Re: Robot Collision, an idea.
« Reply #9 on: Jul 16th, 2004, 1:30pm » |
Quote Modify
Remove
|
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
|
|
IP Logged |
|
|
|
ChipBizGuy
Guest
|
|
Re: Robot Collision, an idea.
« Reply #10 on: Jul 16th, 2004, 1:36pm » |
Quote Modify
Remove
|
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?
|
|
IP Logged |
|
|
|
Norman Furlong
Guest
|
 |
Re: Robot Collision, an idea.
« Reply #11 on: Sep 20th, 2004, 6:37pm » |
Quote Modify
Remove
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Robot Collision, an idea.
« Reply #12 on: Sep 21st, 2004, 4:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Norman
Newbie
Posts: 1
|
|
Re: Robot Collision, an idea.
« Reply #13 on: Sep 22nd, 2004, 3:22pm » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Robot Collision, an idea.
« Reply #14 on: Sep 22nd, 2004, 9:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Brad711
Newbie
Gender:
Posts: 10
|
|
Re: Robot Collision, an idea.
« Reply #15 on: Dec 17th, 2004, 8:33pm » |
Quote Modify
|
I don't get it.
|
|
IP Logged |
|
|
|
Norman Furlong
Guest
|
|
Re: Robot Collision, an idea.
« Reply #16 on: Dec 18th, 2004, 9:19pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Robot Collision, an idea.
« Reply #17 on: Dec 19th, 2004, 3:23pm » |
Quote Modify
|
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.
|
| « Last Edit: Dec 19th, 2004, 3:26pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Robot Collision, an idea.
« Reply #18 on: Dec 20th, 2004, 6:12am » |
Quote Modify
|
on Dec 19th, 2004, 3:23pm, 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.
|
|
IP Logged |
|
|
|
Jayant Chauhan
Guest
|
|
Re: Robot Collision, an idea.
« Reply #19 on: Nov 13th, 2005, 8:41pm » |
Quote Modify
Remove
|
Hey,
For the globe thing, cant we just move them in the opposite directions  . Or are you guys just suggesting a generic solution ?!
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Robot Collision, an idea.
« Reply #20 on: Jun 30th, 2008, 7:09pm » |
Quote Modify
|
on Jul 29th, 2002, 10:53am, klbarrus wrote: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
|
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print