The Same Rule, Updated Left to Right
This is #2140 with the update order deliberately reversed. The rule table is
the same, the non-wrapping boundary is the same, and the answer is different.
A generation is carried out by visiting cells from index 0 up to index
n - 1, one at a time, and writing each new value immediately. So when cell i
is computed:
its LEFT neighbour, cell i - 1, already holds its NEW value for this generation
the cell itself, cell i, still holds its OLD value
its RIGHT neighbour, cell i + 1, still holds its OLD value
A missing neighbour off either end counts as 0. The three values, read as
left centre right, give a position from 0 to 7, and the bit of rule at that
position is written into cell i at once, before cell i + 1 is visited.
Print the row after exactly g such passes.
``` n = 5, g = 1, rule = 90, row = 00100 -> 01111
i = 0: left 0, centre 0, right 0 -> 0 row 00100 i = 1: left 0, centre 0, right 1 (old) -> 1 row 01100 i = 2: left 1 (NEW), centre 1, right 0 -> 1 row 01100 i = 3: left 1 (NEW), centre 0, right 0 -> 1 row 01110 i = 4: left 1 (NEW), centre 0, right none -> 1 row 01111 ```
Compare #2140, which runs the same rule simultaneously and answers 01010.
The two are different questions, not two spellings of one, and this problem
exists so that difference is seen once deliberately rather than discovered as a
bug.
## What most people try first
Writing the careful two-buffer version out of habit, because that is the rule
everywhere else. Here it gives the WRONG answer, because the specification
explicitly says the left neighbour is already updated. The two-buffer solution
answers #2140.
## One array, mutated in place
for each pass:
for i from 0 to n - 1:
l = (i > 0) ? a[i - 1] : 0 # already new
c = a[i] # still old
r = (i < n - 1) ? a[i + 1] : 0 # still old
a[i] = table[4 * l + 2 * c + r]
In-place is not a shortcut here, it is the specification. Note the order of the
three reads: a[i + 1] must be read before a[i] is written, which the line
above does naturally because the write is the last thing to happen. Splitting
it into "write a[i], then compute the neighbours" would corrupt the right
neighbour of the previous cell.
## Why it is correct
The specification is a sequence of single-cell assignments in a fixed order, so the only thing to prove is that the code performs exactly those assignments in exactly that order and reads exactly the values the specification names.
Visiting i in increasing order gives that directly. At the moment cell i is
written, the cells with index below i have each been written once during this
pass, so a[i - 1] holds its new value, which is what the specification asks
for. The cells with index i or above have not been touched during this pass,
so a[i] and a[i + 1] hold their values from the previous generation, which
is also what the specification asks for. No value is read after being
overwritten and no value is read before being written, so the state the code
sees at each step is the state the specification describes.
Note that the second implementation used to verify this problem keeps prev
and cur as two separate arrays, reading cur[i - 1], prev[i] and
prev[i + 1]. It agrees with the in-place version on every case, which is the
evidence that in-place really does mean what is written above.
## The boundary that breaks a careless implementation
Cell 0 has no left neighbour, so it reads 0 rather than the value just
written at the end of the previous pass. Each pass starts clean at the left
edge. For n = 1 the single cell reads 0 on both sides, so this problem and
#2140 agree there, which is why that case is declared in both.
## Cost
O(n g) updates and O(n) memory, one array rather than two. At the stated
limits, at most 40000 updates.