Sprague–Grundy theorem / Game of nim / Bowlingpins hackerrank

I think this document has a really good explanation of the relevant theory: https://web.mit.edu/sp.268/www/nim.pdf. Personally, it took me a bit to get through the document; at first I just tried reading, but I got much more out of it by writing some of the lemmas/theorems down and practicing a bit myself. I think the graphs under “From Games to Graphs” and “The Sprague-Grundy Function” sections were particularly helpful for this problem.

Here’s how I started thinking about it: a set of pins is a game position. Each game position is either terminal or has followers, which are other game positions that can be moved to. Each game position can be assigned a Sprague-Grundy (SG) based on the SG values of its followers. Now try creating a graph of game positions:

• The only terminal position is no pins left, which we can write as `X` or `XX` or however many `X` based on the number of pins you start with. This position has `SG(X) = 0` because it’s terminal.

• The game position `I` can have one pin knocked down, which would make it `X`. So `X` is a follower of `I`, and `SG(I) = mex{SG(X)} = mex{0} = 1`

• The game position `II` can have either one pin knocked down, making it `XI` == `IX` == `I`, or two, making it `XX` == `X`. So it has these two followers, and `SG(II) = mex{SG(I), SG(X)} = mex{0, 1} = 2`.

• Now let’s look at `III`, since this is where we get to start using some of the other information from the document. The followers are `XII` (SG of 2), `XXI` (SG of 1), and `IXI`. For this last one, we could see that it only has one follower and get the SG like that, OR we could use the Sprague-Grundy theorem. This says “the SG function for a sum of games on a graph is just the Nim sum of the SG functions of its components”. For `IXI`, it has two games of `I`, each with SG of 1. When we take the nim sum (xor the binary representations), we get 0. So in conclusion, `SG(III) = mex{2, 1, 0} = 3`.

And you can keep going bottom to top to get other SGs by taking 1 or 2 `II` away at a time and calculating nim sums.