Engineer's Blog #5 - Nim Game

Yo!

One of the leetcode problems I worked on this week, is called Nim game.

I coded it well, and the solution got accepted!

But, upon submitting for complete review, only 15 out of 60 cases worked, so it's not truly accepted.

In true Suman fashion, will still share what I have so far, because I was surprised, and am happy, that at least 15 passed.

Before that, you might want to try solving it yourself....This is as much a logic puzzle, as it is a game, as it is computer science.

I will pause.

Ready? It's only 3 lines of code for 25% success:

if(n<4) return true; 

if(n>12) CanWinNim(n-12); 

return false;

Here is my reasoning:

if(n<4) return true; // I go first, and remove 1, 2, or 3 stones.


if(n>12) CanWinNim(n-12); // 12 is the magic number I came up with, by combining the total options for each player, plus 6. 

// the first 6 represents what a player can do - take upto 3 stones away. Together, 2 players can take away 2 stones, or 6 stones total.

// the second 6 represents the leeway for first player advantage to hold; should a player take away less than 3 stones, and I accomodate this change, less than 6 stones will allow the opponent to win. 

// I don't think it's a coincidence that 12 is 6 + 6; the first 6 represents what both can do; the second 6 represents how even if it's NOT my turn, an unkonwn number  of stones, (n) can, or cannot, become 6.
 
return false; 

// if n is less than 4, we would have won. If it was more than 12, we would assume both me, and my opponent would act, leaving some more stones (6) for our win.

// should it ever turn out that the number of stones are less than 6, representing first player advantage,
// then the opponent will win - because whether I take away 1, 2, or 3 stones, he will react accordingly by adjusting the number of stones he takes away.

// Gosh I can't believe this is an easy. The problem relies on figuring out a shared action pool for both players, but also finding a sweet spot where the shared action pool no longer applies (6 stones)

What are the exact changes I need to make, so I can make my test coverage, 100%?

Put another way: what core logic, does my algorithm miss, so the next time I code I get all of 60 cases correctly?