Memoization error when converting naive recursive coin problem

Question

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!

If you really want to optimize: 1. subtract one from the pile size => the player to remove the last coin is the winner now (nim). 2. grundy numbers are pile size modulo three. 3. Put everything together: The player to move loses only if n % 3 = 1, otherwise the winning move is to make n % 3 = 1. — maraca
– maraca, Commented Dec 21, 2022 at 22:48
Your recursion depends on both coinsRemaining and currentPlayer but your memoization only depends on coinsRemaining. This inconsistency leads to the wrong behaviour. — Quân Anh Mai
– Quân Anh Mai, Commented Dec 22, 2022 at 7:49
@maraca Yep, I realised that but I wanted to try it with memoization. Thanks for the tip anyway. — testing09
– testing09, Commented Dec 22, 2022 at 10:48

jochen · Accepted Answer · 2022-12-22 01:24:43Z

1

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)

answered Dec 22, 2022 at 1:24

jochen

3,9602 gold badges42 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Memoization error when converting naive recursive coin problem

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related