Internet Problem Solving Contest

IPSC 2015

Solution to Problem E – Enclosure

This is intentionally a very open-ended task, with a whole spectrum of possible approaches.

It is possible to view this as an implementation problem. Clearly, all your last moves will be in the proximity of the cat, which makes it reasonably easy to solve the endgame optimally, but what to do with the first part of the game? Maybe making the first few moves randomly, or in some fixed pattern will do the trick.

It is also possible to view this as a code analysis problem. Read the cat’s implementation, try to understand its strategy and use that to build a trap. It is our opinion that it never hurts to take at least a cursory glance into the source code. A high-level scan through the library should have told you that the cat follows one strategy for the first 7 turns, and then a different one for the rest of the game. The first strategy is something about free parts of the board, the second strategy is something with shortest paths. Since turn 8, the cat essentially follows some shortest path to the boundary. This knowledge can be quite useful when playing the game.

Which brings us to option 3: treat this task as an actual game. Play it, learn the cat’s behavior, adapt, and eventually solve the task completely by hand.

Each of these options has its benefits. You should have chosen the one that plays to your strengths. And which one of these do we prefer? Actually, neither. Our favorite solution involves both writing code and playing the game – but it does not involve writing any code that solves the game. We did a very different thing. In a few additional lines of code we significantly improved the Pygame implementation. In particular, the two features we added were Save/Load and Undo. (Both can easily be implemented without messing with the library. For example, to undo, just take the log of the current game, start a new game, and replay the old log except for its last item.) Having these, playing the game becomes much more pleasant. You will learn the cat’s movement patterns faster, you will be able to try different possibilities for the next move, and take back a bad move without restarting the entire game.

The best solution we were able to find by playing the game in this improved visualizer takes 12 moves: 11 8, 9 10, 6 7, 7 3, 6 2, 6 1, 9 3, 8 2, 8 4, 9 4, 7 1, 7 2. The final configuration is shown below.

Cat Challenge results

Two teams managed to match our 12-move solution. The faster of those two teams and the amazing winner of the Cat Challenge is… wait for it… Stjupit Dox: Peter Trebatický, Peter Lacko, and Matúš Horváth. Congratulations!

The second place goes to NIN Team who also submitted a 12-move solution, approximately two and a half hours later than our winners.

Six other teams found a 14-move solution. The fastest of those was the team Open Ports.