Three Rules, and the First One Wins
A row of n cells holds one of three values:
0 empty
1 young
2 mature
Each generation, every cell is recomputed at the same time from the previous generation. Three rules are tried IN THIS ORDER, and the first one whose condition holds decides the new value. If none holds, the cell keeps its value.
rule 1 a cell with a neighbour equal to 2 becomes 0
rule 2 a cell equal to 1 becomes 2
rule 3 a cell equal to 0 whose BOTH neighbours equal 1 becomes 1
A neighbour off either end of the row counts as 0.
Print the row after exactly g generations.
``` n = 5, g = 1, row = 01000 -> 02000
cell 0: no neighbour is 2, cell is 0, and its only present neighbour is 1 while the missing one counts as 0, so no rule fires: stays 0 cell 1: no neighbour is 2, cell is 1, so rule 2 fires: becomes 2 cell 2: no neighbour is 2, cell is 0, its neighbours are 1 and 0, so rule 3 does not fire: stays 0 ```
## The order is load bearing
Rules 1 and 2 OVERLAP. A cell equal to 1 that has a neighbour equal to 2
satisfies both conditions, and rule 1 is listed first, so the cell becomes 0
and not 2. Reversing the two rules gives a different automaton.
n = 2, g = 1, row = 12 -> 02
Work that one through slowly. At cell 0 the right neighbour is 2, so rule 1
fires and cell 0 becomes 0, even though rule 2 also applied to it and would
have made it 2. At cell 1 the only present neighbour is cell 0, which holds
1, so rule 1 does not fire; cell 1 is not 1, so rule 2 does not fire; cell
1 is not 0, so rule 3 does not fire; it keeps 2. The row becomes 02. Had
rule 2 been listed first, cell 0 would have become 2 and the row would be
22 instead.
## What most people try first
Writing the three conditions as independent if statements with no else, so
a cell that matches two rules is written twice and the LAST match wins instead
of the first. That is a one-character bug with a completely different answer,
and it only shows up on inputs where two rules fire at once, which random
testing hits rarely.
## The method
for each generation:
for each cell i:
l = (i > 0) ? old[i - 1] : 0
r = (i < n - 1) ? old[i + 1] : 0
if l == 2 or r == 2: new[i] = 0
else if old[i] == 1: new[i] = 2
else if old[i] == 0 and l == 1 and r == 1: new[i] = 1
else: new[i] = old[i]
old = new
The else if chain is the whole implementation of "first match wins". The
alternative, which is what verifies this problem, is to evaluate all three
conditions into a list and then take the first that is true. That version is
longer and makes the precedence explicit rather than implied by the control
flow, which is why it was used as the independent second opinion: a mistake in
one is unlikely to appear in the other in the same shape.
## Why it is correct
Two things to establish.
First, simultaneity. All three rules test values of the PREVIOUS generation,
including the neighbours, so writing into a second array and swapping is
required for the same reason as in #2140. Here it is easier to get wrong
because rule 1 looks at neighbours while rule 2 looks only at the cell, so a
careless reading treats rule 2 as safe to apply in place. It is not: cell
i + 1 would then read an updated cell i when evaluating rule 1.
Second, precedence. The else if chain evaluates the conditions in the listed
order and assigns from the first true one, which is the definition given. The
only pair of rules that can both hold is 1 and 2, since rule 3 requires the
cell to be 0 with both neighbours 1, which leaves no neighbour equal to 2
and so excludes rule 1, and requires the cell not to be 1 and so excludes
rule 2. So exactly one ordering decision matters, it is between rules 1 and 2,
and the statement settles it.
## Cost
O(n g) cell updates with O(1) work each and O(n) memory, at most a
million updates at the stated limits.