Moving Chips (Large Input)

Let the rows be numbered 1 to 100 from top to bottom, and the columns be numbered 1 to 100 from left to right.

First, how can we figure out who wins?

If you're familiar with the game Nim , this is actually very similar to it. Suppose a chip is in row $r+1$ and in column $c+1$ . Interpret this as two Nim piles, one of size $r$ and one of size $c$ . If we move the chip to row $r'+1$ (with $r' < r$ ), this is equivalent to reducing the pile of size $r$ to size $r'$ . Likewise, if we move the chip to column $c'+1$ , this is equivalent to reducing the pile of size $c$ to size $c'$ .

This interpretation is correct:

• A pile corresponds to a chip and a direction (left or up).
• Moving a chip left/up means reducing the corresponding pile.
• We can only move one chip in one direction as a single move; we can only reduce one pile as a single move.
• When all chips are at the top-left corner, the piles are empty.
• The winner is the player that moved last, or in other words the loser is the player that cannot move; this is the same as Nim.

Thus, we can interpret this as a game of Nim. And conveniently, we know how to solve Nim; we take the XOR of the sizes of the piles, and if it's 0, then the second player wins, otherwise the first player wins.

Now that we've shown that, we can code it: convert it to a game of Nim, and find the winner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

data = "<contents of the file>".split()
# now data[r][c] refers to cell in row r+1, column c+1
nim_piles = []
for r in range(100):
    for c in range(100):
        if data[r][c] == ".": continue
        for k in range(int(data[r][c])):
            nim_piles.append(r)
            nim_piles.append(c)
result = 0
for pile in nim_piles: result = result ^ pile
print("Alice" if result != 0 else "Bob")
# prints Bob