Memoization error when converting naive recursive coin problem-CodePudding

I am attempting the following problem:

Two players start with a pile of coins, and each player has the choice of removing either one or two coins from the pile. The player who removes the last coin loses.

I have come up with the following naive, recursive implementation (playgound):

func gameWinner(coinsRemaining int, currentPlayer string) string {
    if coinsRemaining <= 0 {
        return currentPlayer
    }

    var nextPlayer string

    if currentPlayer == "you" {
        nextPlayer = "them"
    } else {
        nextPlayer = "you"
    }

    if gameWinner(coinsRemaining-1, nextPlayer) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer) == currentPlayer {
        return currentPlayer
    } else {
        return nextPlayer
    }
}

func main() {
  fmt.Println(gameWinner(4, "you")) // "them"
}

The above code works fine.

However, when I improve this solution by implementing memoization (see below, or on the playgound), I get the wrong answer.

func gameWinner(coinsRemaining int, currentPlayer string, memo map[int]string) string {
    if coinsRemaining <= 0 {
        return currentPlayer
    }

    var nextPlayer string

    if currentPlayer == "you" {
        nextPlayer = "them"
    } else {
        nextPlayer = "you"
    }

    if _, exists := memo[coinsRemaining]; !exists {
        if gameWinner(coinsRemaining-1, nextPlayer, memo) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer, memo) == currentPlayer {
            memo[coinsRemaining] = currentPlayer
        } else {
            memo[coinsRemaining] = nextPlayer
        }
    }

    return memo[coinsRemaining]
}

func main() {
    memo := make(map[int]string)
    fmt.Println(gameWinner(4, "you", memo))
}

Any help as to why the second implementation is returning different values to the first would be greatly appreciated!

CodePudding user response：

Your memoization is wrong: the winner does not only depend on the current number of coins, but also on whose turn it is. You need something like the following:

type state struct {
    coinsRemaining int
    currentPlayer string
}
memo := make(map[state]string)