2
\$\begingroup\$

Your task is to program a robot so that it reaches the hole in the ground on each of the maps within reasonable time. If the robot reaches the hole, it falls down into it and thus victory is assured, even if the program never stops running.

Since the robot has to be programmed by manually punching in ones and zeroes, you want to solve the problems using as few commands as possible. Labels are translated to positions by the assembler and integrated into the gotoblocked and call commands, so the programmer never has to punch them into the robot. Therefore, they do not count towards the score. If the robot tries to move into a wall or off the map, nothing happens.

The language consists of these statements:

  • forward move the robot forward one step
  • right rotate 90 degrees clockwise
  • left rotate 90 degrees counter-clockwise
  • for X {A1 A2 .. An} repeat commands A1, A2, ..., An X times
  • call X call a subroutine, beginning at label X
  • return return from the subroutine
  • gotoblocked X jump to label X if there is a wall immediately in front of the robot
  • mylabel: a label used by call and/or gotoblocked. Loops may not contain any labels. Labels may only contain letters.

The input files consist of: testcase_name
N M
and then an N by M grid of:

  • . empty square
  • # blocked square
  • M the hole in the ground that we want to end up in
  • < > ^ v starting position of the robot, directed left, right, up or down, respectively.

The maps can be found at http://progolymp.se/uploads/robot.zip

Your task is to solve all the maps.

Validation: The code you submit will be executed against all the test cases, starting at the label testcasename for each map. Follow the formatting in the example program.

Scoring: The score is the number of statements (excluding labels) in the whole file, i.e. the code used to solve all testcases. Code reuse between testcases is ok.

Example program with starting points for testcases robot_cross and robot_maze (that solves neither):

walkandreturn:
  for 100 {
    forward
  }
robotmaze:
  gotoblocked done
  right
  right
  for 100 {
    for 3 {
      forward
    }
  }
done:
  return

robotcross:
  for 100 {
    call walkandreturn
    right
  }

Automated judge can be found at http://progolymp.se/uploads/robot.jar. To test a file against the testcase robot_ew_manuell, add this to the end of your program file:

main:
  call robotewmanuell

The judge starts execution at the label main, but we want it to start at robotmaze instead. This causes the judge to jump to where it should start, and saves me from having to write a new judge.

The actual judge can then be run like this: java -cp robot.jar parser.Runner robot_ew_manuell.in < my_solution.ans

Help wanted
If you have a good place to mirror the files, or a way to post them on the site, please do.

This problem is based on the final problem of the 2016 online qualifier of Programmeringsolympiaden. https://po.kattis.com/problems/robotoptimering The original problem was authored by Johan Sannemo and Anton Grensjö. CC BY-SA licensed, just like Stack Exchange.

\$\endgroup\$
12
  • 1
    \$\begingroup\$ Pretty sure this is just going to involve implementing A* (or similar) in your custom robolang. \$\endgroup\$ Dec 16, 2015 at 19:24
  • 1
    \$\begingroup\$ @Draco18s How would you implement A* in this language? By using the robot to simulate a turing machine? Keep in mind that the challenge is to use as few statements as possible. Writing the commands one-by-one to take the robot from start to finish would probably use less statements. \$\endgroup\$ Dec 16, 2015 at 19:30
  • \$\begingroup\$ Ah, there are specific test cases, no general case solution needed. Never mind then. \$\endgroup\$ Dec 16, 2015 at 19:32
  • \$\begingroup\$ You could write a single solution that handles all the test cases if you want to. \$\endgroup\$ Dec 16, 2015 at 19:33
  • 2
    \$\begingroup\$ Yes, but it would handle only those cases. It wouldn't handle every possible case. That was my misunderstanding \$\endgroup\$ Dec 16, 2015 at 19:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.