Langton's Ant starting from pure white grid (from Wikipedia)
The problem is provided by Clive Fraser aka CSFPython - our warmest thanks for it!
Langton's Ant is a well-known cellular automaton with a simple set of rules leading to quite complex emergent behaviour. The ant moves on a square grid of black and white squares. The rules for moving the ant are as follows:
- If the ant is on a
Whitesquare, it changes the colour of the square to black, then turns clockwise (i.e. "right") through 90 degrees and then moves forwards into the next square. - If the ant is on a
Blacksquare, it changes the colour of the square to white, then turns anti-clockwise (i.e. "left") through 90 degrees and then moves forwards into the next square.
The ant can face in any of four directions: Up (U), Down (D), Left (L) or Right (R). All squares on the grid have x,y co-ordinates. Up is in the direction of increasing y. Right is in the direction of increasing x. At the start, all squares in the grid are coloured white. The ant is placed on the square 50,50 and is facing Down. The first 5 moves of the ant are described in the table below:
move 0 W 50 50 D
move 1 W 49 50 L
move 2 W 49 51 U
move 3 W 50 51 R
move 4 B 50 50 D
move 5 W 51 50 R
The table describes the position of the ant at the end of each move. Each description starts with the colour of the square which the ant is on (W or B). We then have the co-ordinates of the square (x followed by y) and then the direction in which the ant is facing. Move 0 represents the starting position. For move 1, the ant begins by changing the colour of the current square; so the square at 50,50 is changed from white to black. The ant then turns clockwise through 90 degrees to face left (L). Note that the square was white at the start of the move; this is the colour that determines the direction of the turn. Finally the ant moves forward one square; so moves left into square 49,50 which is currently white. In move 2 the ant begins by turning the colour of square 49,50 from white to black. It then turns clockwise through 90 degrees to face up (U). The ant then moves forwards into square 49,51 which is currently white. At the end of move 4, the ant has returned to square 50,50. Note that this is now black because its colour was changed during move 1. For move 5 the ant turns square 50,50 from black to white. It then turns anti-clockwise for the first time, to face right (R), before moving into square 51,50 which is currently white.
Input/Output description: The first line of the input data will contain a single integer N. N lines will follow. Each line contains a single move number. For each move number you must describe the position of the ant, using the format given in the question (not including the move number itself). In the example below, after move 47 the ant is on a black square with coordinates 50,53 and is facing left (B 50 53 L). Give all answers on a single line, separated by single spaces.
Example:
input:
9
47
137
447109
59678217
9798659910
747887439942
4080904939000
7319969768184828
819361551456997263
answer:
B 50 53 L B 51 50 L W 8471 8446 L B 1147531 1147508 L W 188435639 188435619 U W 14382450643 14382450617 U W 78478941010 78478940984 D B 140768649388040 140768649388018 D W 15756952912634438 15756952912634415 R