# Internet Problem Solving Contest

## Problem F – Fish Fillets

Fish Fillets is little known but extremely cool and challenging logic game made by the Czech company Altar, and later released as open source. In this task you will have to solve two new levels – by any means you can use.

You are controlling two fish trapped in a room. The big blue fish is Agent Max Flounder, and the small orange one is Agent Tina Guppy. The entire game is played on a discrete grid. In each step, you may move one of the fish by one square in one of the four basic directions. The fish can push and carry other objects according to specific rules described later. The player’s goal is to get both fish out of the room. Sounds simple – but make one bad move and falling objects will kill your fish.

To get yourselves acquainted with the game, you can watch a video with instructions at http://www.youtube.com/watch?v=qs1JedhK0fI or download this video from our server. Alternately, the same rules as in the video are summarized below.

Pushing objects

The fish are only in danger when they move some object. The simplest situation is lifting objects – there is no danger in it. If the fish on the left picture moves up, it lifts the object. If it moves left or right, the object stays in place. If the fish goes on moving left or right long enough, it will eventually come out from under the object, and the object will fall harmlessly down. The only dangerous direction is down. If the fish moves down, the object it was supporting will fall on it and kill it.

If the fish want to push an object left or right, the object must be supported by some structure or other object. The fish cannot support the object it is pushing. The fish on the middle picture cannot move left because it would get killed.

The fish can push an unsupported object only if it becomes supported in the new position. An example of such a situation is on the right picture.

Steel objects

In some levels you will encounter steel objects. They look like the cylinder on the picture above. Steel objects can only be lifted and pushed by the big fish. The small fish cannot move them. Moreover, if she gets to a situation where she has to support a group of objects that includes some steel objects, she will perish.

Transferring objects

The fish can transfer objects between themselves. If one fish supports the object and the other one gets into position where the object rests also upon her, the first fish can move away. Any fish can move away in the left picture and the object will stay upon the other.

Be careful with transfer of steel objects. In the situation on the right picture only the smaller fish can move away.

Pushing objects along other objects

It is allowed to push objects that are not directly supported by the fish. One such case is presented on the left picture.

However, a fish is not allowed to push an object that is directly supported by her partner; in such case the partner would perish. More precisely, this is disallowed in the case where the object would rest directly on the partner after the push. For example, the small fish on the middle picture cannot push right because it would kill the big fish.

For the same reason it is impossible to place an object upon a fish. This is shown on the right picture.

Note that on the middle picture the small fish could swim around and push the L shaped object left.

Falling objects

Falling objects are always deadly. It doesn’t matter how long the object falls, if it hits a fish or something that rests upon a fish, the fish is dead.

The object supported directly by a fish can only be pushed if it falls down or rests upon some structure immediately afterwards. This is shown on the left and middle pictures.

Be on the lookout for the situation where the object seemingly hits the fish but at the same time it hits some structure. In such a situation the fish is safe. An example of such a situation is on the right picture.

Problem specification

Your task is to solve two levels of this game. A level is solved if both fish leave the room alive. A fish will leave the room the moment it touches the boundary of the level After a fish leaves, the player can not return it back into the room.

We provide you both with a textual description of the levels and with a Flash applications which you can use to familiarize yourselves with the rules and even to solve the entire levels, if you prefer to do it by hand. If you solve a level, the application will congratulate you and show you the sequence of moves you made. (You can then copy this sequence and submit it.)

Instructions for the Flash application

• R: restarts the level
• S or F2: saves the current position
• L or F3: loads the most recently saved position
• space: switches which fish is active
• arrow keys: moves the active fish one step in the given direction
• some objects are animated – this is eye candy only, ignore it when solving

Input specification

All coordinates in the input are 0-based, with (0,0) in the upper left corner. For each object the initial coordinates of its upper left corner are given. The rest should be obvious.

Output specification

Send us a text file with a sequence of moves that wins the given level. Any such sequence of 5000 or less moves will be accepted. Each move is a character from the set UDLRudlr. Lowercase letters are movements of the small fish, uppercase ones are movements of the big fish. The letters represent the directions: Up, Down, Left and Right. Whitespace does not matter.

Flash applications:

Example

 input room:  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 0 0 0 0 0 0 0 1 0 0 0 0 0 1  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1    small fish:  row 4 col 1  1 1 1    large fish:  row 1 col 10  1 1 1 1  1 1 1 1    item 1:  row 2 col 9 steel  1 0  1 1  1 1
 output L R D L L L L  R R R R D R  u u u r r r r d r r r r r r d r The first row of the output is the big fish pushing the steel object to the left. In the second row it exits the room. Finally, the small fish can now swim around the steel object and exit the room as well. The entire initial position in ASCII art looks as follows:              111111111111111              1.......1.BBBB1              1........oBBBB1              1........oo....              1SSS.....oo....              111111111111111 Here, B is the big fish, S the small one, and o is the steel object.