Paterson's Worms is another game along the lines of Conway's Game of Life or Langton's Ant. However the ruleset allows for very unique and interesting behaviors:
- The game takes place on an infinite lattice graph of equilateral triangles. Initially, every edge of the graph contains a piece of food.
- There is a worm which can travel along the edges of the graph. Each time he reaches a node, he decides on a direction of travel then moves along an edge.
- While traveling along the edge the worm must eat food, or else he will starve and the simulation will end. Food is never replaced, so this means that the worm cannot travel the same path twice.
So how does the worm decide which edge to travel along?
The graph is always viewed from the worm's perspective, and edges around the worm's head are defined as follows:
- 0: Straight ahead, directly in front of the worm.
- 1: 60° right.
- 2: 120° right.
- 3: 180° behind the worm.
- 4: 60° left.
- 5: 120° left.
The worm is given a pre-defined ruleset consisting of a list of integers between 0 and 5 corresponding to these directions.
When reaching a node, the worm observes the pattern of the 5 edges around its head still contain food (the worm cannot see behind itself).
If only a single path has food, the worm automatically will follow that path.
Otherwise when the worm sees a pattern it has never seen before, it will apply the next move in its ruleset to that pattern, and then will make that move every time it encounters that pattern.
If the worm happens to encounter more unique patterns than the length of its ruleset, the worm begins reading from the beginning of the ruleset again.
That is, for a ruleset of length L, the nth unique pattern will use the n mod Lth rule of the ruleset.
Let's take a look at an example, a worm with a ruleset of [2, 0, 0]. On the worm's first turn, it sees food in the directions 01245 (recall the worm cannot see behind itself). This is the first time the worm is seeing this pattern, and it is the first pattern the worm has seen, and so the worm decides to move in the 2 direction (the first direction in its rulset). On the worm's second turn it again sees food in the directions 01245, and so again moves in the direction 2. The same thing occurs on the worm's third turn as well. However on the worm's fourth turn it has returned to the origin, so now it only sees food in the directions 0145. This is the first time is has seen this pattern, and it is the second pattern the worm has seen, and so the worm decides to move in the 0 direction (the second direction in its rulset). The worm continues until its tenth turn, on which it sees no food on any visible path, which is the fourth pattern it has seen, chooses to move in the direction 2 and then terminates because no food exists in that direction.
The path of the a worm with the ruleset [2, 0, 0].
Turn │ Pattern Seen │ Direction Chosen
──────│──────────────│──────────────────
0 │ 01245 │ 2
1 │ 01245 │ 2
2 │ 01245 │ 2
3 │ 01 │ 0
4 │ 01245 │ 2
5 │ 01245 │ 2
6 │ 014 │ 0
7 │ 01245 │ 2
8 │ 01245 │ 2
9 │ - │ 2 (terminates)
But this example just so happens to terminate rather quickly.
A worm with the ruleset [1, 0, 4, 2, 0, 1, 5] will go on for over 10 ^ 18 turns before terminating.
A worm with the rulset [1, 4, 2, 0, 2, 2, 1] will never terminate.
Problem Statement
For this problem, assume each edge has a length of 1.
Input Data
First line is Q, the quantity of testcases.
Q lines will then follow. The first value of each line will be N, the number of turns to run the simulation for.
The second value of each line will be the ruleset of the worm, with all digits compressed into a single string.
Answer
Should be Q space-separated integers, corresponding to the total absolute distance travelled from the origin at the end of the Nth turn.
If the worm terminates before reaching the Nth turn, report the distance to that termination point instead.
Error should be less than 1e-3.
Example
input data:
5
1 200
9 200
999 200
2376 51451
267515 254551
answer:
1 0 0 1 53502.5