2015-12-02 20:15 CET

Onlinekvalet 2016


2015-12-06 22:15 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -2667 days 3:49:03

Time elapsed


Time remaining


Problem F

There’s a robot in an $N \times M$ grid, where some unit squares are blocked so that the robot cannot walk on the square. Now she wants to move to another square, and have asked her owner to program her to do this. This owner happen to be you.

To transfer the programming to a robot from your computer requires a lot of energy, so you want to make the program as short as possible - this means using as few commands as possible. As everyone knows, the robot programming language looks as follows:


Move the robot forward a single step in its current direction.


Rotate $90\deg $ clockwise.


Rotate $90\deg $ counterclockwise.

for X { A1 A2 ... An }

Repeat the commands A1, A2, ..., An $X$ times.

call X

Jump to the instruction with label X, and add it to the current position in the call stack.


Jump to the last added position in the call stack, and remove it.

gotoblocked X

Jump to the instruction with label X, if the square in front of the robot is blocked.

A label has the syntax labelnamn:, and may only consist of small letters. A label cannot be inside a loop. The execution starts at the label called main.

Example program

  for 100 {
  gotoblocked done
  for 100 {

  for 100 {
    call walkandreturn

When the robot moves towards the edge of the grid, or a blocked square, it doesn’t move. When the robot reaches her target square, she wins, even if she doesn’t stop on the square.


Input consists of 10 different grids, which you can download here: Each grid is formatted as follows:

The first line contains the testcase name.

The next line contains two integers $1 \le R \le 1000$ och $1 \le C \le 1000$, the number of rows and columns in the grid.

Each square is one of:


free square


blocked square


goal square


start square, indicating the direction of the robot (in the order left, right, up, down).


There are some tools written in Java which you can download here: to solve the problem. You can use the command java -cp robot.jar parser.Runner < testfall.ans to run the program in the file testfall.ans on the grid in the file The program will tell you if the robot succeeded.

If you also want a graphical representation of the execution, you can run java -cp robot.jar gui.GuiMain.


To submit your solutions, you first run the command java -cp robot.jar gen.Submission, in the folder where your solutions are located. This will generate a Python-file named This can be submitted to Kattis (choose the language Python 3).


The output for testcase must be saved in the file robot_XYZ.ans. It should consist of a program on the form described above, that moves the robot from its starting position to the end position.


The scoring is based on the length of your program. The length is the number of times you use one of the listed commands in the your program. Our example program has length 11. In particular, labels does not contribute to length.

Assume your length on a test case is $L$, and that the shortest length on this case is $B$. Your score is then

\[ 10 (1 - (\frac{L - B}{L})^2) \]

OBS: Your score may change on this task during the contest, when people submit better solutions. In the beginning, we have put the best solution as 2000 commands, and will replace these when submissions are made, rejudging all the solutions. The score is not final until we have done this rejudge after the contest.