“Enclosure” is a simple turn-based game. The game is played by two players. One of them is you, the other is an evil cat. The cat is located on a finite hexagonal grid. Whenever it’s the cat’s turn, the cat moves from its current hex to one of the neighboring hexes. (The cat cannot remain still, it always has to move.) Whenever it’s your turn, you get to click on one of the empty cells to block it off forever. You start the game by blocking the first cell.
The cat wins the game if it reaches the border of the hexagon. You win the game if you block the cat completely – i.e., you win if the cat doesn’t have any valid moves left.
A sample situation during the game is shown in the figure below. The blocked cells are filled. The image also shows the coordinate system used in the game. The cat starts in the middle: at (10, 10).
Catch the cat!
(Also see below for the special Cat Challenge!)
The cat’s moves are completely deterministic. You are given an implementation of the cat’s algorithm in the file catlib.py. You are also given several tools to help you interact with the cat:
The script cat-commandline.py is a simple command line interface to the library. It alternately reads your move from the standard input and prints the cat’s move to the standard output.
The script cat-pygame.py is a simple implementation of the game using the Pygame library.
Whenever you win or lose a game, the game library automatically appends a log of the game to the file log.txt. (So, for example, if you just won a game using the Pygame interface, you can find a log of that game at the end of the log file.)
The output for the easy subproblem E1 should contain any sequence of valid moves that catches the cat. The output for the hard subproblem E2 should contain any sequence of at most 17 valid moves that catches the cat. You may use any whitespace.
For a game in which you made m moves, the output should contain a sequence of 2m integers: the coordinates of blocked cells, in order. It should not contain any parentheses, commas, or the strings “NEW GAME” and “WINNER:” that are added to the game log by the library.
This problem comes with an additional special challenge! If you are bored with the rest of the problem set, you can keep looking for the shortest solution you can find.
Note that the contest system will only allow you to submit a correct solution to each subproblem once. Once you solve both subproblems, you will not be able to make additional submissions. If you later improve your solution, you may e-mail the new, shorter game log to ipscreg@ksp.sk with the subject “Cat Challenge”.
At the end of IPSC 2015 we will announce the three teams with the shortest solutions (breaking ties by submission time / e-mail reception time). The top three teams will also be enshrined for all eternity in the solution booklet.
