2140. 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.

Constraints - `1 ≤ n ≤ 200` - `0 ≤ g ≤ 200` - `0 ≤ rule ≤ 255` - every character of the starting row is `0` or `1` - the row does not wrap: a missing neighbour counts as `0` - all cells change simultaneously, from the previous generation only