This is a follow-up blog to this talk Please let me know if there are any errors. I might not be able to reply rapidly as it is finals week for me.\

The previous post doesn't exactly explain how to actually work out the solutions to Sprague-Grundy problems, or how to code them. Within this follow-up blog, I shall attempt to explain some of my thought process on working through Sprague-Grundy and similar problems, as well as including some code.

First, some pseudo-code of calculating the Sprague-Grundy, and how to find the MEX.

**Recursive Sprague-Grundy**

However, this implementation is inefficient, as it's not memoized, and we might recompute Sprague-Grundy of certain games quite a lot. Usually, if the game is just in terms of stack size, we can just go in increasing order to evaluate, since each move reduces the stack size, and we would have stored the values for smaller stacks into an array. This is a fairly simple example of dynamic programming.

Consider a game where we're given a set S of numbers by which we can reduce the size of a pile. The following outlines how to use an array to calculate the Sprague-Grundy of a single pile.

**Array Sprague-Grundy**

Now, since we've computed the Sprague-Grundy for any given pile, we can determine who wins given a list of piles in the starting position in linear time. The S-Nim problem on kattis is basically these.

Sometimes, a turn on a game results in a combination of games of the same type. This is usually a strong indication for the usage of Sprague-Grundy. As an example, let us consider the Cuboid Slicing Game.

Each move can result in up to 8 different games of the same type. We consider any 0-volume cuboid as a losing position, as no further moves can be made upon it.

However, calculating the set of all possible next games might seem intimidating, but we can compute the Sprague-Grundy of game combinations using the Sprague-Grundy of the original games!

Let us first consider a pseudo-code of the recursion.

**Inside the Sprague-Grundy**

Converting this recursive definition to a solution that runs fast enough is left as an exercise. Additionally, some constant-factor optimizations may be needed.

Some further problems I could find are as follows:

One of the techniques mentioned in the previous post can be used for this problem: 717D - Dexterina’s Lab

In addition, there are quite a few problems on ProjectEuler that these concepts are also applicable to.

Now, for outlines of solutions to the problems from the previous blog:

**The Simplest Subtraction Game**

**Slightly More Complicated**

**One more for the road**

Since someone was asking for the proof of the Sprague-Grundy Theorem, since it was omitted for brevity in the previous post, here is one.

**Finally putting Sprague-Grundy together**