Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Programming two trains to intersect without positional data or communication (logic puzzle) [closed]

A helicopter drops two trains, each on a parachute, onto a straight infinite railway line.

There is an undefined distance between the two trains.

Each faces the same direction, and upon landing, the parachute attached to each train falls to the ground next to the train and detaches.

Each train has a microchip that controls its motion. The chips are identical.

There is no way for the trains to know where they are.

You need to write the code in the chip to make the trains bump into each other.

Each line of code takes a single clock cycle to execute.

You can use the following commands (and only these):

  • MF - moves the train forward
  • MB - moves the train backward
  • IF (P) - conditional that is satisfied if the train is next to a parachute. There is no "then" to this IF statement.
  • GOTO
like image 250
siva Avatar asked Oct 25 '10 08:10

siva


2 Answers

Make each train move forwards slowly until it finds a parachute. When the back train finds the parachute of the front train, make it move forwards faster to catch up with the front train.

1.  MF
2.  IF(P)
3.    GOTO 5
4.  GOTO 1
5.  MF
6.  GOTO 5

If you want to make it take less time for the trains to reach each other, at the cost of some extra lines of code, you can unroll the second loop.

like image 58
jchl Avatar answered Sep 21 '22 09:09

jchl


label1: MF
If (P)
{
   // Do nothing (because of no then?)
}
ELSE
{
   MF;
   MB;
   GOTO label1;
}
label 2:MF
GOTO label2;

GO forward 2 times, backward 1 times until meet the other train's parachute go forward like crazy (to bump into the other - it's still Forward then backward - meaning it's go slower). I use MF one time in label 2, mean it take 2 clock cycle to go one step forward. In label1 it took 5 clock cycle to go forward one steps. So if we use more MF in label2 two of them will bump into eachother faster.
No variable used.

like image 38
Kiennx Avatar answered Sep 19 '22 09:09

Kiennx