The Move That Completes the Line
An r by c board starts empty. A list of q moves is played in the order
given, numbered 1 to q. Each move names the player, 1 or 2, and a row and a
column.
Three rules settle everything a casual description of such a game leaves open:
1. a move onto a square that already holds a mark is ILLEGAL. The board does
not change, and the move still uses up its number.
2. turns are NOT enforced. The player named on each move is the player who
moves, even if the same player moves twice running.
3. the game ends the instant a player has w of their own marks in a row
horizontally, vertically, or along either diagonal. Later moves in the list
are not played.
Print the winning player and the number of the move that ended the game,
separated by a space. If no player ever completes a line, print DRAW.
``` r = 3, c = 3, w = 3, moves: 1 1 0 0 2 2 1 1 3 1 0 1 4 2 2 2 5 1 0 2 -> 1 5
player 1 holds (0,0), (0,1) and (0,2) after move 5, which is the top row ```
``` r = 3, c = 3, w = 3, moves: 1 1 1 1 2 1 1 1 3 1 0 0 4 1 2 2 -> 1 4
move 2 is illegal, since (1,1) is taken, and it still consumes move number 2, so the diagonal is completed on move 4 and not on move 3 ```
## What most people try first
Rescanning the entire board after every move, looking for any line of w. It
is correct, and it is the second implementation used to verify this problem,
but it costs O(r c w) per move, and only one square has changed.
The sharper version counts outward from the square just played, which is the only square that can be part of a newly completed line:
for each of the four directions (0,1), (1,0), (1,1), (1,-1):
run = 1
walk forward from the played square while the mark matches, counting
walk backward from the played square while the mark matches, counting
if run >= w: the mover has won
Four directions, not eight: walking both ways along each of them already covers all eight compass headings, and doing eight directions separately double-counts the played square and reports lines that are half the length.
## Why counting from the played square is enough
Before the move, no line of w existed, or the game would already have ended.
After the move, suppose the mover has a line of w. Every square of that line
holds the mover's mark, and the board before the move differed from the board
after it in exactly one square, the one just played. If that square were not on
the line, the line would have been complete before the move as well, which
contradicts the game not having ended. So the played square lies on the line,
and the line runs in one of the four directions through it. Walking both ways
from the played square along that direction counts a maximal run of the mover's
marks containing the line, so the count is at least w and the win is found.
The run >= w rather than run == w matters: the run through the played
square may be longer than w, for instance when the move joins two existing
runs. An equality test misses exactly that case.
## The boundary that breaks a careless implementation
An illegal move must not be skipped silently in the numbering. It consumes its move number, so the answer is a different number from the one a solution that only counts legal moves would print. The second worked example above is precisely that case and is a declared test.
w may be 1, which means the first legal move wins. w may also be larger
than both r and c, which means no line can ever be completed and the answer
is always DRAW.
## Cost
O(w) per move for the four directions, so O(q w) overall, plus O(r c)
memory for the board.