Nim Game

You are playing the following Nim Game with your friend:

• Initially, there is a heap of stones on the table.

• You and your friend will alternate taking turns, and you go first.

• On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.

• The one who removes the last stone is the winner.

  Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

  Source – Solution

package questions

import _utils.UseCommentAsDocumentation
import utils.shouldBe

/**
 * You are playing the following Nim Game with your friend:
 *
 * * Initially, there is a heap of stones on the table.
 * * You and your friend will alternate taking turns, and you go first.
 * * On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
 * * The one who removes the last stone is the winner.
 *
 * Given n, the number of stones in the heap, return true if you can win the game assuming
 * both you and your friend play optimally, otherwise return false.
 *
 * [Source](https://leetcode.com/problems/nim-game/)  – [Solution](https://leetcode.com/problems/nim-game/discuss/73749/Theorem:-all-4s-shall-be-false)
 */
@UseCommentAsDocumentation
private fun canWinNim(n: Int): Boolean {
    // Anyone who gets a 4 is destined to lose as other player gets either 1,2,3 stones remaining
    return n % 4 != 0
}

//    if (n <= 3) {
//        return true
//    }
//    val memo = Array<Boolean?>(n + 1) { null }
//    return playNim(n - 1, true, memo)
//            || playNim(n - 2, true, memo)
//            || playNim(n - 3, true, memo)
//}
//
//private fun playNim(remaining: Int, iRemovedIt: Boolean, memo: Array<Boolean?>): Boolean {
//    if (memo.getOrNull(remaining) != null) {
//        return memo[remaining]!!
//    }
//    if (remaining == 0) {
//        return iRemovedIt
//    }
//    if (remaining <= 3 && iRemovedIt) {
//        return false
//    } else if (remaining <= 3 && !iRemovedIt) {
//        return true
//    } else if (remaining == 4 && iRemovedIt) {
//        return true
//    }
//    return playNim(remaining - 1, !iRemovedIt, memo).also { println("${remaining - 1} == $it") }
//            || playNim(remaining - 2, !iRemovedIt, memo).also { println("${remaining - 2} == $it") }
//            || playNim(remaining - 3, !iRemovedIt, memo).also { println("${remaining - 3} == $it") }
//
//}
//
fun main() {
    canWinNim(8) shouldBe false
    canWinNim(5) shouldBe true
    canWinNim(4) shouldBe false
    canWinNim(2) shouldBe true
    canWinNim(1) shouldBe true

}

---

View on GitHub

Updated on 2021-10-31