Leonardo invented the original odometer: a cart which could measure distances by dropping pebbles as the cart's wheels turned. Counting the pebbles gave the number of turns of the wheel, which allowed the user to compute the distance travelled by the odometer. As computer scientists, we have added software control to the odometer, extending its functionalities. Your task is to program the odometer under the rules specified below.
Operation Grid
The odometer moves on an imaginary square grid of
Basic Commands
The odometer can be programmed using the following commands.
left
- turn degrees to the left (counter clockwise) and remain in the current cell (e.g. if it was facing south before, then it will face east after the command).right
- turn degrees to the right (clockwise) and remain in the current cell (e.g. if it was facing west before, then it will face north after the command).move
- move one unit forwards (in the direction the odometer is facing) into an adjacent cell. If no such cell exists (i.e. the border in that direction has already been reached), then this command has no effect.get
- remove one pebble from the current cell. If the current cell has no pebbles, then the command has no effect.put
- add one pebble to the current cell. If the current cell already contains pebbles, then the command has no effect. The odometer never runs out of pebbles.halt
- terminate the execution.
The odometer executes the commands in the order they are given in the program.
The program must contain at most one command per line.
Empty lines are ignored.
The symbol #
indicates a comment; any text that follows, up to the end of the line, is ignored.
If the odometer reaches the end of the program, execution is terminated.
Example 1
Consider the following program for the odometer.
It takes the odometer to the cell
move # no effect
right
# now the odometer is facing east
move
move
Labels, Borders, and Pebbles
To alter the flow of the program depending on the current status, you can use labels, which are case-sensitive strings of at most 128 symbols chosen from
L:
- (i.e. followed by a colon:
) - declares the location within a program of a label . All declared labels must be unique. Declaring a label has no effect on the odometer.jump L
- continue the execution by unconditionally jumping to the line with label .border L
- continue the execution by jumping to the line with label if the odometer is on a border facing the edge of the grid (i.e. amove
instruction would have no effect); otherwise, the execution continues normally and this command has no effect.pebble L
- continue the execution by jumping to the line with label if the current cell contains at least one pebble; otherwise, the execution continues normally and this command has no effect.
Example 2
The following program locates the first (westmost) pebble in row leonardo
and davinci
.
right
leonardo:
pebble davinci # pebble found
border davinci # end of the row
move
jump leonardo
davinci:
halt
The odometer starts by turning to its right.
The loop begins with the label declaration leonardo:
and ends with the jump leonardo
command.
In the loop, the odometer checks for the presence of a pebble or the border at the end of the row; if not so, the odometer makes a move from the current cell halt
command is not strictly necessary here as the program terminates anyway.)
Statement
You should submit a program in the odometer's own language, as described above, that makes the odometer behave as expected. Each subtask (see below) specifies a behaviour the odometer is required to fulfill and the constraints the submitted solution must satisfy. The constraints concern the two following matters.
- Program size — the program must be short enough. The size of a program is the number of commands in it. Label declarations, comments and blank lines are not counted in the size.
- Execution length — the program must terminate fast enough. The execution length is the number of performed steps: every single command execution counts as a step, regardless of whether the command had an effect or not; label declarations, comments and blank lines do not count as a step.
In Example 1, the program size is right
, pebble davinci
; border davinci
; move
; jump leonardo
), and finally, pebble davinci
and halt
.
Subtask 1 [9 points]
At the beginning there are
Limits: program size
Subtask 2 [12 points]
Same task as above but when the program ends, the cell
Limits: program size
Subtask 3 [19 points]
There are exactly two pebbles somewhere in row
Limits: program size
Subtask 4 [up to 32 points]
There are at most
points if ; points if ; points if .
Limits: program size
Subtask 5 [up to 28 points]
There may be any number of pebbles in each cell of the grid (of course, between
points if ; points if ; points if .
Limits: execution length
Implementation Details
You will have to submit a single file containing programs to all subtasks.
You will need to include headings (lines of code) of the form [Subtask X]
to indicate the start of your program for subtask [Subtask X]
and will parse your program beginning on the next line and ending at the next subtask heading or at the end of the file.
For each test case, you will receive feedback on the resources used by your code. If the code is not syntactically correct and thus impossible to test, you will receive information on the specific syntax error. If you do not include a program for any given subtask, the subtask will score zero for that submission.
Example 3
[Subtask 1] # heading for the first subtask
right
move
move
[Subtask 4]
put
Above is an example of a submission that has valid headings and programs for subtasks 1 and 4.
Note that code size is measured separately for each subtask.
The above program would have code size
Simulator
For testing purposes, you are provided with an odometer simulator, which you can feed with your programs and input grids. Odometer programs will be written in the same format used for submission (i.e. the one described above), but without subtask headings.
Grid descriptions will be given using the following format: each line of the file must contain three numbers,
0 10 3
4 5 12
The grid described by this file would contain
You can invoke the test simulator by calling the program simulator.py
, passing the program file name as an argument.
The simulator program will accept the following command line options:
-h
will give a brief overview of the available options;-g GRID_FILE
loads the grid description from fileGRID_FILE
(default: empty grid);-s GRID_SIDE
sets the size of the grid toGRID_SIDE
GRID_SIDE
(default: , as used in the problem specification); usage of smaller grids can be useful for program debugging;-m STEPS
limits the number of execution steps in the simulation to at mostSTEPS
;-c
enters compilation mode; in compilation mode, the simulator returns exactly the same output, but instead of doing the simulation with Python, it generates and compiles a small C program. This causes a larger overhead when starting, but then gives significantly faster results; you are advised to use it when your program is expected to run for more than about steps.
Note that the simulator is written in Python 2, not Python 3.
Attachment Package
The simulator along with the examples is available here.
Comments