Official link: https://projecteuler.net/problem=933
Note: My code takes around ~6136s (WITH PYPY, so actually it's way slower) which makes it my longest running piece of code! I'm still happy with my understanding as my solution was identical to a lot of other top solvers
Another note: Problem does not have official difficulty yet but my guess is ~50%
This problem is not super difficult to implement if you know some combinatorial game theory, which I didn't!
I recommend you read my post for Problem 310 first, other wise a lot of what I'm about to say is going to sound like gibberish.
The method is actually near identical to Problem 310, firstly we calculate the Grundy numbers for each possible position, then for each possible starting position we simply go through the all the possible moves we can make. This splits our board into 4 smaller boards, call them TL (Top left), TR (Top right), BL (Bottom left), BR (Bottom right), then if Grundy(TL) XOR Grundy(TR) XOR Grundy(BL) XOR Grundy(BR) = 0, then this means the position is losing for the next player and hence the original move would force a win.
To calculate the Grundy number for each position it is actually near identical!
Suppose we begin in a position P, then Grundy(P) = mex{Grundy(TL) XOR Grundy(TR) XOR Grundy(BL) XOR Grundy(BR): for each possible move we can make} and our base case is if we have a 1 X N (or N X 1) position, say R, then Grundy(R) = 0.
Using this we can now compute C(w, h), but simply finding them all would take forever. In order to solve the problem you have to notice that at some point C(w, h + 1) - C(w, h) = w - 1, once we've reached this point we can instantly compute the remaining terms. I simply computed C(w, h) until I had a run of length 150 (This was a completely arbitrary guess, made through trial and error) of successive differences equal to w - 1
Input 2 integers separated by a space (W, H)
Code will output D(W, H)
Note: Due to time issues W > 20 will take too long, either way that should be enough test cases!