wu :: forums - Print Page


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

        riddles >> medium >> 2 Robots
        
(Message started by: mad on Mar 7^th, 2008, 8:11pm)

Title: 2 Robots
Post by mad on Mar 7^th, 2008, 8:11pm

Two robots are standing on an infinitely long line at infinte unknown positions. We need to make them meet. To do so, we need to write same program for both of them using statements
MOVL (move 1 step left)
MOVR (move 1 step right)
MOV2L (move 2 steps left)
MOVR (move 2 steps right)
MARK (make a mark at current position)
if( Mark ) //True if mark is already there.

Title: Re: 2 Robots
Post by Icarus on Mar 8^th, 2008, 7:26am

No negation or Else operators? No branching instructions? That will require infinitely long programs.

Title: Re: 2 Robots
Post by Hippo on Mar 8^th, 2008, 7:54am

It is very simillar to hole in the wall ... one of the robots will stand still mimicking the hole...

Yes, some variables will be helpful ... what about unmarking, conditioanl loops, branching ...

Title: Re: 2 Robots
Post by rmsgrey on Mar 8^th, 2008, 8:00am

on 03/08/08 at 07:54:44, Hippo wrote:

It is very simillar to hole in the wall ... one of the robots will stand still mimicking the hole...

Yes, some variables will be helpful ... what about unmarking, conditioanl loops, branching ...

You can't have just one robot stand still throughout - each robot has the same program...

I'd go for:

MOVL
if ( Mark ) MOV2L
MARK

repeated infinitely many times...

Title: Re: 2 Robots
Post by Hippo on Mar 8^th, 2008, 10:37am

Oops: one letter difference sAme not sOme ;)

And yes, your solution works well if the conditions are interpreted the way you use.
(Suppose originaly there is sufficient number of places with no marks ;) )

Title: Re: 2 Robots
Post by Grimbal on Mar 9^th, 2008, 6:16am

What is missing in the question is: how are the robots synchronized. Do they repeat the whole program with each time tick? Do they repeat one instruction per time tick? If yes, is if ( ... ) ... executed in one or two ticks when the condition is true?

Title: Re: 2 Robots
Post by temporary on Mar 23^rd, 2008, 1:24pm

Write this program for only one(or possibly both) robot(s):
MOVL
MOV2R
MOV3L
MOV4R
MOV5L
MOV6R...

Title: Re: 2 Robots
Post by rmsgrey on Mar 24^th, 2008, 2:19pm

on 03/23/08 at 13:24:50, temporary wrote:

Write this program for only one(or possibly both) robot(s):
MOVL
MOV2R
MOV3L
MOV4R
MOV5L
MOV6R...

There are two problems with that program. Firstly, it uses instructions that aren't included in the initial set, which only allows for moves of up to 2 steps. Secondly, if both robots execute it at the same speed, there will always be a constant distance between them.

Title: Re: 2 Robots
Post by temporary on Mar 25^th, 2008, 6:09pm

Then I suppose programming both of them wouldn't work, but programming only one of them still works. And I can still use that answer by simply rewriting it with only two steps at a time.
MOVL
MOV2R
MOV2L
MOVL
MOV2R
MOV2R
MOV2L
MOV2L
MOVL
MOV2R
MOV2R
MOV2R
MOV2L...

Title: Re: 2 Robots
Post by rmsgrey on Mar 26^th, 2008, 12:45pm

on 03/25/08 at 18:09:30, temporary wrote:

It's possible for the two robots to be guaranteed to meet, despite both running the same program. The key is the if command that lets the robots behave differently depending on whether they are at marked positions or not.

Title: Re: 2 Robots
Post by Hippo on Mar 26^th, 2008, 3:11pm

rmsgrey: Nice to see someone who is able to comment the posts in such a polite way. ;)
I myself should ignore them not having enough mental powers to be able to ...

Title: Re: 2 Robots
Post by marsh8472 on Sep 14^th, 2012, 1:39am

on 03/07/08 at 20:11:13, mad wrote:

do until MARK
MOVL
LOOP
do until MARK == false
MOV2L
loop

They both move left until they pick up the other's trail then once the rightmost bot picks up the leftmost bot's trail, the rightmost bot moves twice the speed until it catches up with the leftmost bot.