I was doing a coding problem which I somehow passed all test cases but I did not understand exactly what was going on. The problem was a small twist on the classic nim game:
There are two players A and B. There are N piles of various stones. Each player can take any amount of stones if the pile is less than K, otherwise they must take a multiple of K stones. The last person to take stones wins.
python
# solution -> will A win the game of piles, k?
def solution(piles, k):
gn = 0 # Grundy number
for pile in piles:
if pile % 2 != 0:
gn ^= pile + 1
else:
gn ^= pile - 1
return gn != 0
I'm not sure if there was enough test cases, but k was not even used here. To be honest, I am having a difficult time even understanding what gn (Grundy number) really means. I realize there is a proof of winning the Nim game if the xor of all piles is not zero, but I don't really understand why this variation requires checking the parity of the pile.
First, the given solution is incorrect. You noticed that it does not use k, and indeed this is a big red flag. You can also look at the result it gives for a single pile game, where it seems to say that player A only wins if the size of the pile is one which you should fairly quickly be able to show is incorrect.
The structure of the answer is sort of correct, though. A lot of the power of the Grundy number is that the Grundy number of a combined game state is the nim sum (XOR in the case of finite ordinals) of the Grundy numbers of the individual game states. (This only works for a very specific way of combining game states, but this turns out to be the natural way of considering Nim piles together.) So, this problem can indeed be solved by finding the Grundy number for each pile (considering k) and XOR-ing them together to get the Grundy number for the full game state. (In Nim where you can take any number of stones from a pile and win by taking the last stone, the Grundy number of a pile is just the size of a pile. That's why the solution to that version of Nim just XOR-s the sizes of the piles.)
So, taking the theory for granted, you can solve the problem by finding the correct Grundy values for a single pile given k. You only need to consider one pile games to do this. This is actually a pretty classic problem, and IMO significantly simpler to correctly analyze than multi-pile Nim. You should give it a go.
As for how to think of Grundy numbers, there are plenty of places to read about it, but here's my approach. The thing to understand is why the combination of two game states allows the previous player (B) to win exactly when the Grundy numbers are equal.
To do this, we need only consider what effect moves have on the Grundy numbers of the two states.
By definition as the minimum excluded value of successor states, there is always a move that changes the Grundy number of a state to any lower value (ie n could become any number from 0 up to n - 1). There is never a move that leaves the Grundy number the same. There may or may not be moves that increase the Grundy number.
Then, in the case of the combination of two states with the same Grundy number, the player B can win by employing the "copycat strategy". If player A makes a move that decreases the Grundy number of one state, player B can "copy" by reducing the Grundy number of the other state to the same value. If player A makes a move that increases the Grundy number of one state, player B can "undo" it by making a move on the same state to reduce it to the same value it was before. (Our game is finite, so we don't have to worry about an infinite loop of doing and undoing.) These are the only things A can do. (Remember, importantly, there is no move that leaves a Grundy number unchanged.)
If the states don't have the same Grundy number, then the way for the first player to win is clear, then; they just reduces the number of the state with a higher value to match the state with the lower value. This reduces things to the previous scenario.
Here we should note that the minimum excluded value definition allows us to construct the Grundy number for any states recursively in terms of their successors (at least for a finite game). There are no choices, so these numbers are in fact well-defined.
The next question to address is why we can calculate the Grundy number of a combined state. I prefer not to think about XOR at all here. We can define this nim sum operation purely from the minimum excluded value property. We abstractly consider the successors of nim_sum(x, y) to be {nim_sum(k, y) for k in 0..x-1} and {nim_sum(x, k) for k in 0..y-1}; in other words, making a move on one sub-state or the other. (We can ignore successor of one of the sub-states that increase the Grundy number, as such a state would have all the successors of the original state plus nim_sum(x, y) itself as another successor, so it must then have a strictly larger Grundy number. Yes, that's a little bit hand-wavy.) This turns out to be the same as XOR. I don't have a particularly nice explanation for this, but I feel it isn't really necessary to a basic understanding. The important thing is that it is a well-defined operation.