Logo engraving

Semilab is working on its own robot to engrave our logo. The robot is ready, but it needs instructions how to draw. You have to give the correct command sequence to the robot.

The robot understands 4 commands, each command has a power cost:

  • LASER_ON: Turn on laser. In this state the robot is engraving. It costs 100 power.
  • LASER_OFF: Turn off laser. It costs 1 power.
  • MOVE_X K: Move to K position on the X axis. It costs 1 power.
  • MOVE_Y K: Move to K position on the Y axis. It costs 1 power.

In LASER_ON state move command engraves too.
Your task is to make a command sequence that engraves the given logo.

Solutions will be sorted based on power cost.
The input file contains an NxM matrix, where each element is 0 or 1. Value 1 means that the position has to be engraved. Top left corner is (0,0). (The input picture is noisy on purpose, it is not a mistake. The output has to contain the noise too.). You can download input from here.

Only the topmost material is engraveable, it is allowed to engrave the same coordinate multiple times, it will be ignored. Your robots starts at (0,0) position and it is in LASER_OFF state.

algorithm

Criteria

    Race awards:

    • 10-1 points: 1-10. place
      In case of power cost equality, each team gets the points.
      For ea: First 2 teams are equal, they get 10-10 points, and the third team gets 8 points.

    Guaranteed awards:

    • 1 point: Valid solution
    • 2 points: Under 1 500 000 power cost.
    • 3 points: Under 1 200 000 power cost.
    • 4 points: Under 800 000 power cost.
    • 5 points: Under 150 000 power cost.

    Your points will be calculated: Max(race award, guaranteed award)

Submission

Your output must be a team_name.txt file that contains one instruction in each line.
File size limit is 30MB.

For example:
LASER_ON
MOVE_X 50
MOVE_Y 100

Your command sequence has to engrave the given input.

To submit your solution, send your file to zoltan.bartal@semilab.hu, and come to us to run your solution together.