Cat and Mouse

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

There is a cat (initially just one) and a mouse on a 100 by 100 grid . There is a square basin having corners (50,50) and (65, 65) as well as up to three other non-overlapping basins, also 15 by 15 (as determined on the night of the competition but randomly placed by the architect). Neither the cat nor the mouse is allowed to go into the basin. In a single turn, the mouse can choose to stay still or to move one square either vertically, horizontally, or diagonally; the cat can move up to four squares either vertically or horizontally, (but not diagonally) and can mix these directions in two parts of the move (i.e. it can change directions at most once in a move). The mouse and cat must state their movement plans before the move begins. If the cat and mouse ever intersect on a square (i.e. if the cat ever steps in the destination square of the mouse), then the cat catches the mouse and the game is over.

Your Task

You will take the role of the cat in one game and the mouse in another. I will give you beginning positions of each (outside the basins of course). When you are the cat, your job is to catch the mouse in as few turns as possible. When you are the mouse, your job is to avoid being caught for as many turns as possible.

In the multiple-cat version, there can be k cats and any one can catch the mouse.

Architecture Team

Your job is to draw the grid, the basins, the cat(s) and the mouse. Then you are to receive the moves for each turn and track the movement of the cat and the mouse visually. At the end of each turn you are to give those positions to the cat(s) and mouse if they can see one another (i.e. if a straight line from one to the other is not obscured by one or more basins).