The Run Your Own Piece Closes
A row of n cells holds . for empty, A for one player's piece and B for
the other's. k placements are made, in the order given. Each names a player
and a cell index counting from 0.
A placement is carried out like this:
1. if the cell is not empty, the placement is ILLEGAL: nothing changes at all
2. otherwise the player's piece is written into that cell
3. then, looking LEFT from it and looking RIGHT from it, independently:
read outward while the cells hold the OPPONENT's piece
if that run is non-empty AND the cell immediately beyond it holds the
player's OWN piece, every piece in the run changes to the player's
if the run is empty, or it runs off the end of the row, or the cell
beyond it is empty, nothing changes in that direction
Both directions are decided from the row as it stands immediately after step 2 and BEFORE either flip is applied, so a capture on one side can never create or destroy a capture on the other.
Print the row after all k placements.
``` A.BBA place A at 1 -> AAAAA
looking left from cell 1: cell 0 holds A, which is the player's own piece, so the run of opponent pieces is empty and nothing is captured looking right: cells 2 and 3 hold B, cell 4 holds A, so both flip
..BB. place A at 1 -> .ABB.
looking right: cells 2 and 3 hold B and then the row ends with an empty cell, so the run is not closed and nothing flips ```
## What most people try first
Flipping as the scan walks, rather than collecting the run and flipping once
the closing piece has been confirmed. On ..BB. that converts cells 2 and 3 to
A and only then discovers there is no closing A, leaving the row wrong and
with no easy way back.
The second common slip is deciding the second direction from the already
flipped row. Consider placing A at index 2 of AB.BA: left sees B at 1
closed by A at 0, right sees B at 3 closed by A at 4. Both flip, and the
answer is AAAAA. If the left flip is applied first and the right scan then
reads the new row, the answer happens to be the same here, but the rule has
become order dependent, and on other inputs it is not the same. Pinning both
directions to the pre-flip row removes the question.
## The method
if row[at] is not '.': skip this placement
row[at] = me
before = a copy of row
flips = empty list
for step in (-1, +1):
j = at + step
run = empty list
while j is inside the row and before[j] == opponent:
add j to run
j = j + step
if run is non-empty and j is inside the row and before[j] == me:
add run to flips
for j in flips: row[j] = me
## Why it is correct
The rule as written is a function of the row immediately after the placement, so the only thing to establish is that the code evaluates it on exactly that row and writes nothing until both directions have been decided.
Taking the copy before after step 2 gives precisely the row the rule names.
Both scans read only before, so neither can see the other's result, and the
collected flips therefore describes the same set of cells whichever order the
two directions are examined in. The writes happen after both scans, so they
cannot affect either. That is what makes the answer independent of the
direction order, which is the property the statement promises.
The closure test is also exactly the rule: the loop stops at the first cell
that is not the opponent's, so j is either off the end of the row or holds
. or holds the player's own piece. Only the last of those three closes the
run, and only a non-empty run is a capture, so both conditions are needed and
neither is redundant.
## The boundary that breaks a careless implementation
A run that reaches the end of the row is not closed. A run closed by an empty
cell is not closed either. And a placement next to its own piece captures
nothing in that direction, because the run of opponent pieces is empty: AA
is not a capture of zero pieces that still counts.
An illegal placement is skipped entirely, including its captures. It does not flip anything and it does not consume anything.
## Cost
Each placement scans outward at most the width of the row, so O(n) per
placement and O(n k) overall, with O(n) memory.