Problem: Nim Game @ leetcode
(Spoiler alert: the solution is at the very end of the post).
The Mental Game
Despite its classification as "Easy", this was a tough one for me.
In fact, at one point, my primary challenge wasn't the problem itself, but the mental game - managing my sometimes tendency toward negative psychological and emotional response to a problem that frustrates successive waves of assault. In a word, demoralization. Even more acute since the problem was supposed to be "Easy", a cinch, a walk-in-the-park.
If a problem's a no-brainer and I can't solve it, does that mean I have even less than no brain?
I considered recursive (thread stack and regular stack) and dynamic programming approaches. I drew trees that explored every combination of move and countermove. I started several recursive implementations that didn’t feel right and weren’t sufficient, ultimately.
I started having that familiar disconcerting feeling of disorientation. Slipperiness; of the problem, but also my own thoughts about the problem.
Course Correction
Then, I wrote this, and it cracked:
1 2 3 4
W W W L
If there are 1-3 rocks, I win. If there are 4 rocks he wins.
I realized that the reason he wins when there are 4 is that, if he removes 1 rock, he prevents the rock count on my turn from being in the 1-3 rock count range. If I have that range on my turn, I win, because I can block him off from any viable winning paths.
OK. How about larger rock counts?
1 2 3 4 5
W W W L
I can block him off from viable winning paths if I can get him to a rock count of 4 on his turn. And I can do this by removing 1 rock. After doing so, no matter how many rocks he removes, he’ll put me in the 1-3 rock range on my turn. So 5 is winnable.
How about 6?
1 2 3 4 5 6
W W W L W
Similar to 5, I can block him off if I can get him to a rock count of 4 on his turn. I can do this by removing 2 rocks. After doing so, no matter how many rocks he removes, he’ll put me in the 1-3 rock range on my turn. So 6 is winnable.
Larger?
1 2 3 4 5 6 7 8
W W W L W W W
At 8 I have no way to get him to a rock count of 4 on his turn. Furthermore, no matter how many rocks I remove, he can force me to a rock count of 4 on my turn. This isn’t winnable.
1 2 3 4 5 6 7 8
W W W L W W W L
Interesting... From the looks of it, if, on my turn, the remainder of the rock count divided by 4 is in the range 1-3, I win. Put another way, if the rock count is a multiple of 4, he can force me to lose. Or, if the rock count is not a multiple of 4, I win.
While the solution is indeed extreme in terseness - a one-liner - I don’t think that's sufficient reason for the problem to be classified as easy.
Learnings
I really struggled. If I were to do it again, I would explore alternative algorithmic approaches, and non-tree ways of graphically representing a series of moves and outcomes (such as the linear, dynamic programming-like one I described), much much earlier.
How I represented the problem determined the complexity I encountered thinking about the problem and experimenting with sample cases. This, in turn, determined the complexity of the solution and the ease with which I arrived at a solution.
How we choose to represent a problem, well before we even attempt to solve it, can have a powerful steering effect on the outcome - the possibility and quality of a solution, and one's subjective experience of the process (as easy, hard, frustrating, irritating, complex, etc).
Nevertheless, the difference between ultimate success and failure, regardless of how long or short, unpleasant or pleasant, the path was, lay in having switched attention from the challenge of the problem to the challenge of the mental game.
Solution
func canWinNim(_ n:Int) -> Bool {
return n % 4 != 0
}