The Population After Each Generation, On a Ring
The same rule-table automaton as #2140, with one change: the row of n cells
is a RING. Cell 0's left neighbour is cell n - 1, and cell n - 1's right
neighbour is cell 0. Nothing is ever treated as 0 for being off the end,
because there is no end.
Three values, read as left centre right, give a position from 0 to 7, and the
bit of rule at that position is the cell's next value. All cells change
simultaneously, from the previous generation only.
Print how many cells are alive after each of the g generations, in order.
``` n = 5, g = 3, rule = 90, row = 00100 -> 2 2 4
generation 1 01010 two alive generation 2 10001 two alive generation 3 11011 four alive ```
The starting generation is NOT reported. The first number printed is the
population after generation 1, and there are exactly g numbers.
## What most people try first
Reusing a non-wrapping solution and "fixing the ends afterwards". There is nothing to fix afterwards: the end cells have genuinely different neighbourhoods, and patching them after the generation has been computed means patching them from values that are already the new generation. The wrap belongs inside the index calculation, before anything is written.
## Reading the neighbour on a ring
l = cur[(i - 1 + n) mod n]
r = cur[(i + 1) mod n]
The + n matters. In C, C++, Java and JavaScript, -1 mod n is -1, not
n - 1, so without it cell 0 indexes one before the start of the array.
Python's modulo is the exception and returns n - 1. This single difference is
the most common bug in ring problems, and it is a silent out-of-bounds read in
three of the five languages rather than an error.
## Two small rings, settled
When n is 1 the single cell is its own left neighbour AND its own right
neighbour, so its neighbourhood is c c c, which is position 0 or position 7.
When n is 2 each cell has the other cell on both sides, so the neighbourhood
is o c o where o is the other cell. Both are legal inputs and both are
declared tests. They are not special cases in the code: the modulo formula above
already produces exactly this.
## Why the output is a log and not a single number
The populations after each generation are the answer, in order, because an automaton is interesting for its history rather than its final state. That makes the ORDER part of the answer: printing the same multiset of counts in a different order is wrong. It also makes the problem self-checking for a student, since a wrong generation shows up as a wrong count at that position rather than as one wrong final row.
## Cost
O(n g) cell updates and O(n) memory. The counting adds O(n) per
generation, which does not change the order. At the stated limits that is at
most 40000 updates.