Internet Problem Solving Contest

IPSC 2015

Problem E – Enclosure

“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).

Problem specification

Catch the cat!

(Also see below for the special Cat Challenge!)

Input specification

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:

Output specification

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.

Cat Challenge!

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.