XOR Game

I picked up Renako Amaori and XOR Game as a problem I wanted to solve in an effort to get better at both algorithmic thinking as well as Zig. The explicitness of Zig was definitely new but it's good to see exactly what every function depends on when it comes to things like io and file descriptors, along with their buffers.

Algorithm

This required knowing how an XOR sum is affected by swaps, particularly in the case where all array inputs are either a 1 or a 0. One bit flip in the input array flips the XOR sum value. This property lets us conclude some important things:

1. When we make a significant swap, the results of both $XOR(a)$ and $XOR(b)$ will flip (0 to 1, 1 to 0). The XOR sums of both arrays are entangled when we make significant swaps.
2. The game is a Markov process. The only move that matters is the last one.

A significant move is one where $a_i \neq b_i$. In the case of an XOR sum, swapping the same bits will have no effect on the end result.

The game's outcome depends on the initial XOR sums of the arrays $a$ & $b$.

1. if $XOR(a) = XOR(b)$, the game is always a tie.
2. if $XOR(a) \neq XOR(b)$, the player that makes the last significant move wins. This player controls the final state of the game. They can choose whether to swap (changing their XOR sum from 0 to 1) or not to swap (if their XOR sum is already 1).

Hard variant

For this, we extend the same algorithm to all the bit positions of the input integers in the arrays $a$ and $b$. To find the higher XOR sum between the two players, we need to find which player wins at the highest bit position. Over here we will call it the MSB, as from the perspective of the algorithm it is the most significant.

1. check if MSB can be won by either player
2. if a player is a guaranteed winner for the MSB position, we stop the game
3. if the MSB has no winner, we decrement the MSB position (MSB -= 1) and repeat from step 1

If all bit positions are exhausted, we determine a tie.