Swiss Olympiad in Informatics

Timon Gehr has won the Grand Theft Cake game.

After an unfortunate incident at the Aperture Science Enrichment Center, you decided to keep your Handheld Portal Device, knowing it might be handy at some later time (and GLaDOS would not mind, right?). However you are still craving for your share of the promised cake. Mmmh tasty! Since you could not find the cake on your last visit, it must be still inside the ruins of the Aperture Science Laboratories…

You are asked to navigate through the underground complex and look for the promised cake, retrieve it and return to your starting position. The game is played in two dimensions from a birds eye perspective. Your character can take the following actions:

• Look in a direction (tells you the distance to the next wall) [0.1 second]
• Walk in a direction (try to walk there on a direct line) [distance in seconds]
• Shoot portal A or B (creates the portal on the next wall) [5 seconds]
• Teleport (use closest portal) [no cost]

The Portal Gun shoots portals (type A or B) in an arbitrary direction. Portals are created where the line hits the next wall. To use a portal, you must stand within a maximum distance of 1 unit of its location and use the «Teleport» command. Your character will then be moved to the position of the second portal (assuming it has been created).

Note that you can look, shoot and walk in any arbitrary angle! Each of the above actions costs the specified amount of time. Your task is to retrieve the cake as fast as possible. To motivate faster programs, we will also multiply the actual runtime of your program by a factor¹⁾ and add it to your (ingame) time.

All interaction with the game server will be text mode based. This is a (highly) interactive task, it is therefore crucial that you remember to flush your output after each command you send to the server. You can interact with the server using these commands:

All numbers used in this task are floats. The server will return coordinates to a precision of three decimal digits. Whenever you have to reach a certain position (i.e. a Portal), it is sufficient to halt at most 1 unit from this location and the server will automatically assume you wanted to go there (and add the remaining walking distance).

All angles are interpreted in degrees in the range [0-360). As customary with mathematics, the 0 degree direction is the positive x direction (=right=east), the 90 degree direction corresponds to positive y (=up=north).

You can only shoot portals of type A or B. Whenever you place a portal of type A, the previous portal A will be removed. Thus there is always at most one portal of each type on the map. Using the Teleport command will beam you from the adjacent portal to the one with the other type. (You must stand closer than 1 unit to the first portal's location to use it)

If you hit a wall while walking, your move will stop and the resulting position will be where you hit the wall. You can then continue to move from there. Similarly, if you use the Teleport command with no adjacent portal (or the second portal is not placed), then the server will ignore your command and respond with your current position.

The cake is a circle with unit radius, you have to find it and step inside to retrieve it. (Then return to the start location). Note that the portal gun passes the cake unaffected and hits the wall behind it. You can only see the cake with the Look command.

To successfully retrieve the cake, you must stand closer than 1 unit to the cake at the end of one of your Walk or Teleport commands. You can check that you are actually standing inside the cake's circle (and therefore retrieving it) by issuing a Look command, which will return Cake 0.000 if standing inside.

The following shows a sample interaction with the server:

<< Position
>> 0.000 0.000
<< Look 0.0
>> Wall 1.500
<< Look 90.0
>> Wall 8.700
<< Shoot 0.0 A
>> 1.500 0.000
<< Shoot 90.0 B
>> 0.000 8.700
<< Walk 0.0 1.5
>> 1.500 0.000
<< Teleport
>> 0.000 8.700
<< Look 0.0
>> Cake 2.000
<< Walk 0.0 2.0
>> 2.000 8.700
<< Walk 180.0 2.0
>> 0.000 8.700
<< Teleport
>> 1.500 0.000
<< Walk 180.0 1.5
>> 0.000 0.000

In the above example, the player first looks east and north (positive x and y), then shoots portals in both directions, enters the east one, finds the cake on the other side and returns via the portal. If your browser supports animated gif's you can see the moves visualized on the right hand side. (Of course a real user would have to find the cake first, and could not go there directly).

• All coordinates are in the range [-500, 500].
• The Player Character has no width or height, he can move arbitrarily close to objects.
• You should always use the feedback from the server as your current position (otherwise rounding errors might accumulate).
• The levels will be designed such that there are no sharp corners and corridors generally have width of 3 units or more.
• It is in principle possible to play only with directions N,W,S,E and unit steps (though this is not very efficient).
• There might be more than one cake, in which case you need to retrieve only one (any cake is fine).
• The actual time costs of each action (as well as the runtime factor) are subject to change during the first round. Please write your programs such that you can easily adapt to other time constraints.
• You can use the testing server to evaluate your program locally!