I am trying to solve the following leetcode problem of Nim Game. https://leetcode.com/problems/nim-game/
One simple solution in O(1) is:
var canWinNim = function(n) {
return n%4 !== 0;
};
But I am also trying to solve it using DP. Below is my code which is incorrect. I believe there is some issue in the else block at the end. Please help.
var canWinNim = function(n, myChance=true, memo={}) {
if(n in memo) return memo[n];
if(myChance){
if(n<=3) return true;
if(n===4) return false;
} else {
if(n<=3) return false;
if(n===4) return true;
}
let a = canWinNim(n-1, !myChance, memo);
let b = canWinNim(n-2, !myChance, memo);
let c = canWinNim(n-3, !myChance, memo);
if(myChance){
memo[n] = a||b||c;
return memo[n];
}
memo[n] = !(a||b||c);
return memo[n];
};
You're probably right that the problem is there. I think you need to reconsider that a bit.
To my mind, this logic is overly complex, especially the handling of myChance. You can simplify this by simply inverting the value from the cache for n - 1, n - 2, and n - 3 and orring together the results.
It might look like this:
const canWinNim = (n, memo = {}) =>
n in memo
? memo [n]
: memo [n] = (n == 0)
? false
: n < 4
? true
: !canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)
const testCases = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
testCases .forEach (n => console .log (`${n} => ${canWinNim (n)}`)).as-console-wrapper {max-height: 100% !important; top: 0}If nested conditional operators (ternaries) offend you, you could rewrite it like this:
const canWinNim = (n, memo = {}) => {
if (n in memo) {
return memo [n]
}
let val
if (n == 0) {
val = false
} else if (n < 4) {
val = true
} else {
val = !canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)
}
memo [n] = val
return val
}
You can also, if you choose, replace
!canWinNim (n - 1, memo) || !canWinNim (n - 2, memo) || !canWinNim (n - 3, memo)
with
!(canWinNim (n - 1, memo) && canWinNim (n - 2, memo) && canWinNim (n - 3, memo))