Fog Creek Software
Discussion Board




Crash Engines

There are two engines designed to be parachuted at the random points of the infinite straight railway. After landing, they both face one direction.

The engines operate automatically by the on-board computer with a single absolutely identical program inside each computer.

The engines both bury their parachutes at the point of landing, and then their control programs start.

The computer can recognize the following 4 commands:

- FORWARD - move one step (say, 1 meter) forward;

- BACKWARD - move one step backward;

- GOTO <label> - switch control to the command marked by
<label> (each command may have a unique label)

- IF (CHUTE) THEN <command> - if there is a parachute at that point, execute <command> (any command described above). The engines cannot recognize if the parachute is their own.

You are the programmer of the engine on-board computer. Your goal is to make two engines crash.

Can you do that?

Dmitri Papichev
Tuesday, June 14, 2005

crash algorithm:

facing = forward;
num = 1;

while (true)
{
    go num steps in facing direction;
    num = num * 2;
    reverse(facing);
}

reverse(facing)
{
    if facing = forward
        facing = backward
    else
        facing = forward
}

j
Tuesday, June 14, 2005

No, it will not work, because:

- No variables allowed;
- WHILE, IF-ELSE, assignment operators, as well as multiplication, are not supported.

Your program can contain only 4 commands listed above.

Dmitri Papichev
Tuesday, June 14, 2005

J's solution would not work even if all constructions in his code were legal. The engines would stay at the same distance from each other as after the landing.

P.S. I forgot to emphasize that they both land simultaneously.

Dmitri Papichev
Tuesday, June 14, 2005

Should program have a finite number of instructions?

DK
Tuesday, June 14, 2005

Yes.

Dmitri Papichev
Tuesday, June 14, 2005

It was not that scary as I expected after all :) The idea is to program engines to move slowly in one direction, and if one finds another's parachute - accelerate.

----------------------------------
go:
    FORWARD
    IF(CHUTE) THEN GOTO run
    FORWARD
    BACKWARD
    GOTO go
run:
    FORWARD
    GOTO run

DK
Tuesday, June 14, 2005

You got it, DK!

There is an assumption in that solution, that only moving takes time, and all other commands are performed effectively instantaneously.

But what if ALL the commands take the same time to complete, no matter if the engine movement is involved?

Of course, the algorithm above would still work, but could it be simplified then?

Dmitri Papichev
Tuesday, June 14, 2005

You are right - there was an assumption in my solution, which was not stated in the problem, but I just noticed, that even with this my solution is not optimal.

So, there can be another follow-up to the problem:

If only execution of FORWARD and BACKWARD takes some substential and equal time, write a program, that would require minimum time for engines to crash.

DK
Tuesday, June 14, 2005

DK's solution is ALMOST optimal:

go:
    FORWARD
    IF(CHUTE) THEN GOTO run
    BACKWARD *
    FORWARD *
    GOTO go
run:
    FORWARD
    GOTO run

The only optimization we can do is to make it go backward before it goes forward. That way if the other engine is immediately behind, it hits one turn earlier.

If each statement takes equal time to execute, however, we don't need the extra Reverse, Forward:
go:
    FORWARD
    IF(CHUTE) THEN GOTO run
    GOTO go
run:
    FORWARD
    GOTO run

Go takes 3 turns to execute, Run takes 2.

Depending on our program space, we can actually improve the run routine by adding an arbitrary number of FORWARDS before the GOTO:

run:
    FORWARD
    FORWARD
    ...
    FORWARD
    FORWARD
    GOTO run

that way we don't lose as much time calling GOTO every other turn.

BradC
Wednesday, June 15, 2005

I believe, there is nothing left to optimize in BradC's solution for "each command takes constant time" case.

We can speed up "go" loop as well as "run", and if there is some fixed limit on number of commands in program - there can be another tuning question - e.g. to write fastest program in under 100 commands.

Tuning the other case - "only FORWARD and BACKWARD take some substantial and equal time" - is different. Brad had a good catch, but it works only in one special case. Time to crash is defined by two speeds here, ang the idea is to find the best ratio. Plus - demonstrate, that no other program can do better.

Anyway, thanks for the good puzzle, Dmitri :)

DK
Thursday, June 16, 2005

*  Recent Topics

*  Fog Creek Home