import Cocoa

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return canWinNim(n, myTurn: true)
    }

    func canWinNim(_ n: Int, myTurn: Bool) -> Bool {
        print("Turn: \(myTurn ? "Mine" : "Enemy"). Number of stones remaining: \(n)")
        if myTurn && n <= 3 {
            return true
        } else if !myTurn && n <= 3 {
            return false;
        }

        let one = canWinNim(n-1, myTurn: !myTurn)
        let two = canWinNim(n-2, myTurn: !myTurn)
        let three = canWinNim(n-3, myTurn: !myTurn)

        if myTurn {
            if one {
                return canWinNim(n-1, myTurn: !myTurn)
            } else if two {
                return canWinNim(n-2, myTurn: !myTurn)
            } else if three {
                return canWinNim(n-3, myTurn: !myTurn)
            } else {
                print("Turn: \(myTurn ? "Mine" : "Enemy"), failed to win with 1,2,3. Returning false.")
                return false;
            }
        } else {
            if !one {
                return canWinNim(n-1, myTurn: !myTurn)
            } else if !two {
                return canWinNim(n-2, myTurn: !myTurn)
            } else if !three {
                return canWinNim(n-3, myTurn: !myTurn)
            } else {
                print("Turn: \(myTurn ? "Mine" : "Enemy"), failed to win with 1,2,3. Returning true.")
                return true;
            }
        }
    }
}

let solution = Solution()
print(solution.canWinNim(8))