Langton's Ant |
The ant world's is an n x n plane where the squares (or cells) on the plane are colored variously either blue or red. The number n is called the size of the world. A cell is denoted with a pair (i, j), ( 1i, jn). The ant lives and moves in single steps following the rules below:
For example, let us assume the ant is in a red cell while facing east. If there is not a cell immediately to its south, then the ant dies. On the contrary, if there is a cell immediately to its south, then the ant takes a single step by moving to this cell to which it arrives facing south and the color of its source cell flips to blue. Then, the ant will try to take another single step, and so on.
Your task is to determine if the ant can go to the (n, n) cell of a world, given (i) the configuration of the world, and (ii) the initial position of the ant. You are to assume the ant's initial direction is north.
The configuration of an n x n world can be codified as a natural number in binary notation by using n2 bits. We adopt the following conventions: 0 = blue, 1 = red, and the binary representation of the configuration identifies the cells of the world from left to right and from bottom to top (considering the bits from the most significant bit to the least significant bit). For example, the binary number 0100 (4 in decimal notation) represents a 2 x 2 world with the following configuration:
blue | blue |
blue | red |
Coherently, the binary number 011010100 (212 in decimal notation) represents a 3 x 3 world with the following configuration:
red | blue | blue |
blue | red | blue |
blue | red | red |
The problem input has several test cases. Each case consists of a single line containing a list of four natural numbers, n, c, x, y, separated by blanks, that should be interpreted as:
The end of the input is indicated by a line where n = c = x = y = 0.
For each test case your solution should output:
For each test case, it's guaranteed that after a finite number of steps, the ant reaches the cell (n, n) or dies without reaching the cell (n, n).
2 8 1 1 2 4 1 1 2 15 1 1 0 0 0 0
Yes Kaputt! Kaputt!