1998 Canadian Computing Competition, Stage 1

Problem C: Mars Rover

A planetary "rover" is travelling on a perfectly level surface (no obstacles) on Mars. The rover is in radio communication with the "lander" it arrived in. The lander accumulates and relays commands, which it receives from Earth, to the rover. The rover makes several excursions. Each excursion begins with the rover at the lander facing in a known direction. At the end of each excursion the lander must compute and transmit a sequence of instructions to return the rover to the lander.

The rover responds to a sequence of commands sent from the lander. Each command tells the rover to move ahead some multiple of an exact unit of distance, or to turn left or right exactly 90 degrees.

The "move ahead" command is encoded using two consecutive lines in the input file. The first line contains the integer 1, and the second line contains a non-negative integer n, the distance to move forward.
The "turn right" command is encoded using a single input line containing the integer 2.
The "turn left" command is encoded using a single input line containing the integer 3.
For example, the following sequence of commands instructs the rover to turn left, then move ahead 10 units, then turn right, and then move ahead 5 units.

3
1
10
2
1
5

Your task is, given such a sequence of commands, to determine how far the rover must travel to return to the lander, and to determine the shortest sequence of commands that will return the rover to the lander. In the example above, the rover must travel 15 units to return, and the shortest sequence of commands is

2
1
10
2
1
5

Input

The input begins with a line containing a positive integer, n, the number of excursions for the rover. The commands for excursions occupy subsequent lines of the input file. Each excursion consists of a number of commands followed by a line containing 0. There are no errors or blank lines in the input. The rover travels less than 10 000 units of distance on each excursion.

Output

For each excursion, the output should contain a line:

Distance is k

where k is the distance in units that the rover must travel to return to the lander. The following lines should contain the shortest sequence of commands to return the rover to the lander. A blank line should separate the lines of output for different excursions.

Sample Input

3
2
3
3
0
3
1
10
2
1
5
0
1
5
2
1
5
3
3
1
1
0

Sample Output

Distance is 0
 
Distance is 15
2
1
10
2
1
5
 
Distance is 9
1
4
3
1
5

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hi, I have finally managed to get an OK, which involved changing all double-rights to double-lefts.
i.e.
2
2
1
600

turns into
3
3
1
600

Is there any reason why the first version is not considered just as optimal? Feel free to quote any part of the question that answers this. .-.

It could be the case that the verifier isn't working, contrary to Hanson's post from 6 years ago, and your output ends up needing to match the judge output exactly.

Noticed the same effect - extremely weird, considering that my "right biased" code matches the data from http://mmhs.ca/ccc/index.htm perfectly.

The alternate output file was mysteriously missing. I remade it, so Hanson's comment is now valid again and WA submissions have been rejudged.

Note to Brian: Consider displaying an error when alternate output files are missing.

My program turns only left and does the right turn with equivalent number of left moves . Does it matter ?

Yes; your program should optimise the number of actions, and turning left three times is less optimal than turning right once.

Suppose that after all moves in the input are done, the lander is at (0,0), and the rover is at (0,10), facing up (facing the opposite direction of the lander). Should the rover turn left twice then move 10 spaces forward, or turn right twice and move 10 forward? Or does the judge let you do either?

The judge will accept any shortest route.