Takeaway

Whiteboard: Harder
Challenge: Medium
Concepts: Game Theory
Download: takeaway.zip
Solution: Takeaway: Solution

There’s a game, “takeaway”, that is played by two players, using a number of stones.

The first player goes first. She can take 2, 3, or 5 stones from the pool. The second player goes next; she can also remove 2, 3, or 5 stones. The first player then goes, and so on.

If a player is unable to move (there are fewer than 2 stones), they lose.

Your Challenge

Imagine that both players have “perfect play” — that is, they always make the best possible move. Then, you can absolutely determine who would win a game with n stones.

For example:

1

Player #1 cannot move, so player #2 win

2

Player #1 takes 2 stones, and player #2 cannot move

3

Player #1 takes either 2 or 3 stones; either way, player #2 cannot move

4

Player #1 has two choices, one of which wins:

she takes 2 stones, leaving 2 (a win for player #2)
she takes 3 stones, leaving 1 (a win for player #1)

5

Player #1 has three choices, one of which wins:

she takes 2 stones, leaving 3 (a win for player #2)
she takes 3 stones, leaving 2 (a win for player #2)
she takes 5 stones, leaving 0 (a win for player #1)

6

Player #1 has three choices, one of which wins;

she takes 2 stones, leaving 4 (a win for player #2)
she takes 3 stones, leaving 3 (a win for player #2)
she takes 5 stones, leaving 1 (a win for player #1)

7

Player #1 has three choices, but none will win:

she takes 2 stones, leaving 5 (a win for player #2)
she takes 3 stones, leaving 4 (a win for player #2)
she takes 5 stones, leaving 2 (a win for player #2)

8

Player #1 has three choices, but none will win:

she takes 2 stones, leaving 6 (a win for player #2)
she takes 3 stones, leaving 5 (a win for player #2)
she takes 5 stones, leaving 3 (a win for player #2)

9

Player #1 has three choices, with one being a win:

she takes 2 stones, leaving 7 (a win for player #1)
she takes 3 stones, leaving 6 (a win for player #2)
she takes 5 stones, leaving 4 (a win for player #2)

10

Player #1 has three choices, with two being wins:

she takes 2 stones, leaving 8 (a win for player #1)
she takes 3 stones, leaving 7 (a win for player #1)
she takes 5 stones, leaving 5 (a win for player #2)

Remember: both players make the best possible moves, so if player #1 has a winning strategy, she will use it (and player #2 will defend as well as possible).

Code

We’ve written a function which takes one parameter, n, the number of stones in the game. It should True if the active play could win a game starting with that number of stones and False if not.

For example:

>>> can_win(1)
False

>>> can_win(2)
True

>>> can_win(3)
True

>>> can_win(4)
True

>>> can_win(5)
True

>>> can_win(6)
True

>>> can_win(7)
False

>>> can_win(8)
False

>>> can_win(9)
True

>>> can_win(10)
True

Complete this function:

takeaway.py

def can_win(n):
    """Can this player win takeaway?"""