2143. Where the Automaton Starts Repeating

A ring of n cells runs the rule-table automaton of #2141: three values read as left centre right give a position from 0 to 7, the bit of rule at that position is the cell's next value, the ring wraps, and all cells change simultaneously.

Call the starting row generation 0. Print two integers:

s the smallest index such that generation s occurs again later p the smallest positive number with generation s + p equal to generation s

So s is where the repeating part begins and p is how long it is. The generations before s happen once and never come back.

``` n = 4, rule = 90, row = 0100 -> 2 1

gen 0 0100 gen 1 1010 gen 2 0000 gen 3 0000 equal to generation 2, so s = 2 and p = 1 ```

``` n = 5, rule = 150, row = 00100 -> 0 3

the starting row itself comes back after three generations, so nothing happens only once and s is 0 ```

## Why it always terminates

A generation is a row of n cells, each 0 or 1, so there are exactly 2^n possible generations and no more. Generations 0 through 2^n are 2^n + 1 rows drawn from a set of size 2^n, so by the pigeonhole principle two of them are equal. The automaton is also DETERMINISTIC: the next generation is a function of the current one alone, with no memory of how it was reached. So once a row repeats, everything after it repeats too, forever, and the answer exists for every input. With n at its limit of 16 that bound is 65537 generations, which is why simulating to the repeat is affordable at all.

## What most people try first

Running a fixed number of generations, say a few thousand, and looking for two equal rows among them. That is both unsound and slower than it needs to be: the tail before the cycle can be long, and comparing every new row against every stored row costs O(n) per comparison and O(k^2) comparisons after k generations, which at 65537 generations is far too much work.

## Each row is one integer

With n at most 16, a row fits in 16 bits, so a whole generation is a number below 65536. That turns "have I seen this row before" into one array lookup:

first = array of 2^n entries, all -1 m = the starting row packed into bits gen = 0 while first[m] == -1: first[m] = gen m = step(m) gen = gen + 1 print first[m], gen - first[m]

When the loop stops, m is the first row that has been met twice. first[m] is the generation it appeared in originally and gen is the generation it has just reappeared in, so the difference is the period.

## Why that is the SMALLEST s, and the smallest p

Two claims, and both need the argument rather than the assertion.

For s: the loop stops at the first repeat it ever meets, so no generation with index below first[m] recurs. Suppose one did, say generation j with j < first[m] equals some generation k with k > j. Then the loop would have stopped at step k, and k < gen because gen is where it actually stopped, so first[m] would have been at most j, a contradiction. So first[m] is the smallest index that recurs.

For p: because the step is a function, generation s + i is determined by generation s for every i, so the sequence from s onwards is purely periodic with period gen - s. Any smaller positive q with generation s + q equal to generation s would mean row m reappears at index s + q, and s + q < gen would have stopped the loop earlier. So gen - s is minimal.

## The boundary that breaks a careless implementation

p is at least 1, never 0, because s + p must come strictly after s. A row that is already stable, such as anything under rule 0 after it empties, gives p = 1 rather than p = 0. Rings of one and two cells are legal, and the wrap makes a cell its own neighbour there, exactly as in #2141.

## Cost

At most 2^n + 1 generations, each O(n), so O(n 2^n) time and O(2^n) memory for the seen array. At n = 16 that is about a million cell updates and 65536 array entries.

Constraints - `1 ≤ n ≤ 16` - `0 ≤ rule ≤ 255` - every character of generation 0 is `0` or `1` - the row is a ring and all cells change simultaneously, from the previous generation only - the answer always exists because there are only `2^n` possible generations - `p` is at least 1