Run the Rule Table for g Generations
A row of n cells, each 0 or 1, changes in steps called generations. The
next value of a cell depends only on three cells of the CURRENT generation: the
one to its left, itself, and the one to its right.
Those three values, read in that order as a binary number, give a position from 0 to 7:
left centre right position
0 0 0 0
0 0 1 1
0 1 0 2
0 1 1 3
1 0 0 4
1 0 1 5
1 1 0 6
1 1 1 7
The rule is a single number rule between 0 and 255. Its bit at that position
is the cell's next value. So with rule = 90, whose bits from position 0 upwards
are 0 1 0 1 1 0 1 0, the neighbourhood 0 1 0 is at position 2 and the bit
there is 0, while 0 0 1 is at position 1 and the bit there is 1.
The row does NOT wrap. A cell at either end treats the missing neighbour as 0.
Print the row after exactly g generations. If g is 0, print the starting row
unchanged.
n = 5, g = 1, rule = 90, row = 00100 -> 01010
n = 5, g = 4, rule = 90, row = 00100 -> 10001
## What most people try first
Walk the row from left to right and write each new value straight back into the
row you are reading. That is wrong, and it is wrong quietly: by the time the
loop reaches cell i, cell i - 1 already holds its NEW value, so the
neighbourhood being read is half of this generation and half of the next one.
With rule = 90 and 00100, the correct first generation is 01010. Writing
in place gives 01111, because cell 2 sees the freshly written 1 at cell 1
instead of the original 0. Nothing crashes and no index goes out of range.
The answer is simply a different automaton, which is the subject of a separate
problem in this topic, #2142.
## Two buffers, swapped
for each generation:
for i from 0 to n - 1:
l = (i > 0) ? cur[i - 1] : 0
r = (i < n - 1) ? cur[i + 1] : 0
nxt[i] = table[4 * l + 2 * cur[i] + r]
swap cur and nxt
nxt is written and never read inside the inner loop, so every value the loop
reads comes from cur, which is untouched for the whole generation. Swapping
the two buffer references at the end costs nothing and avoids allocating a
fresh array per generation.
## Why it is correct
The specification defines generation k + 1 as a function of generation k
alone, applied to every cell at once. "At once" has a precise consequence: for
any two cells i and j, the value used for j when computing i must be
j's value in generation k, whatever order the cells happen to be visited
in. Writing into a second buffer makes that true by construction, because no
cell of generation k is ever overwritten before the generation is finished,
so the visiting order becomes irrelevant and the result is well defined.
Building the table once as table[i] = (rule >> i) & 1 is correct because the
position formula 4 * left + 2 * centre + right is exactly the binary value of
the three bits in the stated order, and the rule number's bit at that position
is by definition the new value.
## The boundary that breaks a careless implementation
The missing neighbour is 0, not a copy of the cell and not a wrap to the far
end. For n = 1 the single cell has BOTH neighbours missing, so its
neighbourhood is always 0 c 0, which is position 0 or position 2 and nothing
else. A declared test covers that.
## Cost
O(n g) cell updates, each O(1), and O(n) memory for the two buffers. At
the stated limits that is at most 40000 updates.