The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » 2 robots (0 Likes) Printer Friendly Version

 Go to page 1~2 [Next]
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Here is a nice puzzle I was given not long ago.
2 robots land on an endless east-west track.
one has a red parachute the other blue.
the bots can travel at a constant speed to either west or east (or stop in place naturally).
they have FINITE amount of memory and their software can recognize parachutes and colors.
while landing on the track there were strong winds and each bot landed somewhere on the track.
the bots cant communicate in anyway but have to find eachother.
find an algorithm so they can meet.
---
for the math experts, the bots have no memory at all. find a way to make them meet.
--
enjoy,

Nir
Antz
View Profile
Regular user
120 Posts

Profile of Antz
Robot1: I'll go west
Robot2: I'll go east

Since the world is round, wouldn't they naturally meet?

Antz
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Robot 1 does not move at all

Robot 2 needs to remember Direction, Distance and Increment. After he has moved Distance in Direction, Distance is increased with Increment and Direction is reversed.

No idea how to make them meet if there is no type of memory (mechanical or otherwise) in any robot.

/Tomas
dr chutney
View Profile
Special user
United Kingdom
518 Posts

Profile of dr chutney
On landing both robots place parachutes on the ground and secure. Both instructed to head West a finite time and distance. This is calculated by the height from which they were dropped and the potential distance apart they could be based on wind speed etc. An extra 10% or 20% is calculated in.

If they come across the parachute of the other they are to stop and wait. If they don't find a parachute in the time programmed, they are to return to the parachute they left behind. If this excercise fails ( they do not meet up ) they are to repeat but extend the time allotted for travelling by a certain percentage.

This is all assuming they have an unlimited power supply to keep travelling as long as it takes.
We're having a laugh!
Grab yourself a FREE Joke Ebook at http://thejester.biz
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
27017 Posts

Profile of Jonathan Townsend
Hmmm

the track being a good thousand miles across, and the robots only moving east-west... oh well, NASA loses another probe.

Let's saw the track were small. And the robots could put a becon on their chute that would go off is the other robot ran over it. The other robot could halt then. This leads to a problem if both robots have the same strategy. I guess one would need to find a chute and halt while the other one ran around and also listened for the beep.
...to all the coins I've dropped here
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Quote:
On 2005-06-08 01:29, TomasB wrote:
Robot 1 does not move at all

Robot 2 needs to remember Direction, Distance and Increment. After he has moved Distance in Direction, Distance is increased with Increment and Direction is reversed.

No idea how to make them meet if there is no type of memory (mechanical or otherwise) in any robot.

/Tomas


Tomas,

this leads to infinite memory. think that they are very far apart. each time one of the bots has to remember previous DIst+Inc. or Dist+ (iteration * Inc)
this term diverges... so you would need an infinite amount of memory

or maybe I didn't get you right...

Nir
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Quote:
On 2005-06-08 00:45, Antz wrote:
Robot1: I'll go west
Robot2: I'll go east

Since the world is round, wouldn't they naturally meet?

Antz


assume we are on flatland...
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Quote:
If this excercise fails ( they do not meet up ) they are to repeat but extend the time allotted for travelling by a certain percentage.


exactly this sentence implies that they would need an infinite amount of memory.
if a procedure is incremental in nature (meaning it is based on the previous stage decisions) it is usually (like that case) not bounded in memory.
try to look for extremes regarding your initial values and the size of the track, this helps in getting better feeling of the problem.

N.
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Quote:
If this excercise fails ( they do not meet up ) they are to repeat but extend the time allotted for travelling by a certain percentage.


exactly this sentence implies that they would need an infinite amount of memory.
if a procedure is incremental in nature (meaning it is based on the previous stage decisions) it is usually (like that case) not bounded in memory.
try to look for extremes regarding your initial values and the size of the track, this helps in getting better feeling of the problem.

N.
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Nir, I understand what you mean. My solution uses only a finite memory but you can't tell in advance how much that is. I wonder if this is a possible solution:

One bot stays. The other tears his parachute in two parts, leaves one and travels a random distance in one direction. He leaves the half parachute there and changes direction until he reaches the other half parachute which he picks up and continues a random distance in the same directions. He leaves the parachute, reverses direction, etc. When he sees a parachute of the opposite color he stops.

Thinking about it, the first bot may not have to stand still. If he gets the same program they _might_ reach eachother quicker.

/Tomas
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Tomas,
unfortunately the bots do not have arms to drag the parachutes.
they stay in place beside the track.
it is true that your first solution uses a finite amount of memory but you have to set the limits on the problem BEFORE everything starts, and this cant be done...

the solution is so simple you will eat yourself for not finding it quicker.

the 0 memory solution might also be regarded as a 1bit solution - depends on how strict you are with the definition...

Nir
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
Does this work?

Both travel east for one hour, then rest in place for one hour.
As long as neither has come across the other's parachute, this cycle
is repeated over and over again.
Once a bot comes across the other's parachute, it eliminates its rests.
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
You got it stan.
now try the 0 memory solution
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
Both travel east at the same constant speed.
Bot A travels for 1 hour, rests in place for 2 hrs, travels for 3, rests for 4,
travels for 5, etc.
Bot B rests in place for 1 hr, travels for 2 hrs, rests for 3, travels for 4,
etc.
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
Oooops. Scratch that. Nir's objection to Tomas's algorithm would also apply
here. Where'd I put that thinking cap?
dr chutney
View Profile
Special user
United Kingdom
518 Posts

Profile of dr chutney
X = 1

Do

East x mins

x = x + 1

West x mins

x = x + 1

Loop Until Parachute Or Robot Found
We're having a laugh!
Grab yourself a FREE Joke Ebook at http://thejester.biz
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
X=x+1 is not bounded.
give me a value of memory you design the bots for the largest X they can hold.
and I can find you a case where that solution wont work.

N
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Stan, you da man! Excellent solution.

But didn't Stan's solution count as using no memory except for the memory the program lies in? Do you count constants in the zero memory solution or just memory that changes with time? Is it the clock measuring the hour in Stan's solution that counts as used memory?

/Tomas
dr chutney
View Profile
Special user
United Kingdom
518 Posts

Profile of dr chutney
There is a two speed solution which probably doesn't apply here. However, I'll state my case.

If the robots always face East and start travelling at half speed as soon as they land. If they pass the other's parachute they go to top speed. No memory as such; parachute recognition triggers the increase in speed.
We're having a laugh!
Grab yourself a FREE Joke Ebook at http://thejester.biz
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Chutney, they can only travel at a constant speed. So Stan had the solution to diminish their average speed. Correct Nir?

/Tomas
The Magic Cafe Forum Index » » Puzzle me this... » » 2 robots (0 Likes)
 Go to page 1~2 [Next]
[ Top of Page ]
All content & postings Copyright © 2001-2020 Steve Brooks. All Rights Reserved.
This page was created in 0.19 seconds requiring 5 database queries.
The views and comments expressed on The Magic Café
are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic.
> Privacy Statement <

ROTFL Billions and billions served! ROTFL