# Coding Interview: The Matchstick Game

###
Nested Software
Mar 5
*Updated on Apr 11, 2019 *
・7 min read

In this article I'd like to do an interview-style problem-solving and coding exercise. I haven't actually encountered this problem in an interview - I ran across it as a kid on an old computer - but I do think it's a good candidate for an interview. It doesn't rely on sophisticated math or algorithms, so it's a good way to assess basic problem-solving and programming skills. The implementation will be in elm, a pure functional language/front-end web framework. I decided to use elm mainly because I hadn't tried it before, so this article was a good excuse to learn something new.

## The Rules

The rules of this game are very simple: The game starts with 21 matchsticks laid out in front of two players. The players take turns removing 1, 2, or 3 matchsticks at a time. The player who is forced to take the last matchstick loses.

## Simplify The Problem

Is there an optimal way to play this game? To figure this out, let's simplify the problem as much as possible: Let's say there is only 1 matchstick left and it's our turn. We have to take it, and therefore we lose.

However, if there are 2 matchsticks, we can take 1, and leave the last one behind for the other player to take. With 3 matchsticks, we can take two, which also leaves one left over. If there are 4 matchsticks, we can take 3, and the other player is again forced to take the last one.

## The Pattern

We can see the emergence of an inductive pattern: With 1 matchstick, we lose. With 2, 3, and 4, we win. Now, with 5 we're in trouble again: No matter what we do, our opponent will be left with 2, 3, or 4 matches, and we already know that means they can win. With 6, 7, or 8 matches, we are again in a winning position. At 9 we're losing again, and so on.

We can translate this pattern into a bit of simple algebra: If there are m × 4 + 1 matchsticks, where m is an integer between 0 and 5, the current player is in a losing position. The goal of the game therefore becomes to try to get one's opponent into one of these losing positions - from there it becomes a one-way street. We can see that the player who starts the game is sadly doomed to lose! That is, unless the other player makes a mistake!

## Working toward Code

We know that the following values of `count`

represent losing positions:

`count = m × 4 + 1`

`m`

is an integer between 0 and 5, and `4`

is one more than the maximum number of matchsticks a player can take.

Let's solve for m using integer division:

`m = (count - 1) ÷ 4`

The remainder of the integer division is:

`r = (count - 1) mod 4`

If the remainder is 0, we're in a losing position, so we can just take 1 matchstick: Either it's the last one, and the game is over, or we can extend the game, hoping our opponent will make a mistake.

On the other hand, if the remainder is not 0, then we can win. How many matchsticks should we take in that case? The target number of matchsticks we want to leave behind for our opponent is `m × 4 + 1`

where `m`

is the integer quotient resulting from `m = (count - 1) ÷ 4`

.

To reach that target, all we need to do is remove the number corresponding to `r`

. This remainder is always 0, 1, 2, or 3. If it's 1, 2, or 3, that's the number of matchsticks we'll take - it's the difference between the current number of matchsticks and the next losing position.

In pseudocode, we can describe this as `if r is 0 take 1 else take r`

.

## Unit Test

Let's write a unit test to make sure our calculation works out correctly:

```
test "matchsticksToTake gives correct values for 1 to 21" <|
\_ ->
let
expectedMatchsticksToTake =
[ ( 1, 1 ) -- lose
, ( 2, 1 ) -- win
, ( 3, 2 ) -- win
, ( 4, 3 ) -- win
, ( 5, 1 ) -- lose
, ( 6, 1 ) -- win
, ( 7, 2 ) -- win
, ( 8, 3 ) -- win
, ( 9, 1 ) -- lose
, ( 10, 1 ) -- win
, ( 11, 2 ) -- win
, ( 12, 3 ) -- win
, ( 13, 1 ) -- lose
, ( 14, 1 ) -- win
, ( 15, 2 ) -- win
, ( 16, 3 ) -- win
, ( 17, 1 ) -- lose
, ( 18, 1 ) -- win
, ( 19, 2 ) -- win
, ( 20, 3 ) -- win
, ( 21, 1 ) -- lose
]
matchsticks =
List.range 1 21
actualMatchsticksToTake =
List.map
(\count -> matchsticksToTake count)
matchsticks
in
Expect.equal
expectedMatchsticksToTake
actualMatchsticksToTake
```

`matchsticksToTake`

also returns the matchstick count to make testing a bit easier.

## Business Logic

We've already worked out the basic logic, so let's show the actual implementation:

```
matchsticksToTake : Int -> ( Int, Int )
matchsticksToTake count =
let
remainder =
remainderBy 4 (count - 1)
take =
if remainder == 0 then
1
else
remainder
in
( count, take )
```

That's it! Our test passes and the core logic of the game is done!

## User Interface and Gameplay

An interesting aspect of programming is that the business logic can be a relatively small part of the total codebase. In conducting an interview, I think I'd probably just ask for a simple command-line implementation of this game. Even the small amount of code I've written in elm to make the game work may be too much for an interview coding session. However, if you're interested, follow along and I'll briefly summarize that part as well.

We want to make the simplest user interface possible to demonstrate the functionality. Of course we need to display the current number of matchsticks. We also need to know who's turn it is. I also decided to show how many matchsticks were taken on the previous turn. Lastly we need some buttons to let the player choose the number of matchsticks they want to take. Here's the corresponding elm code:

```
view : Model -> Html Msg
view model =
div []
[ h1
[]
[ playerTurnLabel model ]
, h1 [] [ text (String.fromInt model.matchsticks) ]
, button [ onClick (Take 1), disabled (disable model) ]
[ text "take 1" ]
, button [ onClick (Take 2), disabled (disable model) ]
[ text "take 2" ]
, button [ onClick (Take 3), disabled (disable model) ]
[ text "take 3" ]
, p [] [ text <| lastMoveString model.lastSelection ]
]
```

We can see that we just need a very simple model to keep track of the game state for this user interface:

```
type alias Model =
{ currentPlayer : Player
, matchsticks : Int
, lastSelection : Selection
}
type Player
= ComputerPlayer
| HumanPlayer
type Selection
= Selected Player Int
| NoneSelected
```

We're keeping track of the current player, the current number of matchsticks, and the previous player's selection.

On each turn of the game, elm will call our `update`

callback with a message. The message will contain the number of matchsticks the current player wishes to take:

```
type Msg
= ComputerTake Int
| Take Int
| DoNothing
```

Either the computer (`ComputerTake`

) or the human player (`Take`

) wants to play a turn. If the message is `DoNothing`

, that just means we return the current model without making any changes.

When the application starts, the elm runtime calls the `init`

function:

```
init : () -> ( Model, Cmd Msg )
init _ =
-- let the computer start the game
wrapNextMsgWithCmd
( Model ComputerPlayer 21 NoneSelected, computerTakesNextTurn 21 )
```

We want the computer to take the first turn for the human player to have a chance to win, so we initialize `currentPlayer`

to `ComputerPlayer`

. We set up `21`

matchsticks, and the `lastSelection`

is `NoneSelected`

since there was no previous turn.

`computerTakesNextTurn 21`

returns a message that we want to send to update representing the computer's turn. The trick here is that we want to delay this message a bit so that we don't update the screen immediately after each human player's turn. To do that, we use a `Cmd`

. Normally commands are used to perform side-effects, like sending an http request. Here we're using a command to delay the computer's turn. We're basically saying "please issue this command, and then send the following message to `update`

."

For testing purposes, it seemed easier to have `computerTakesNextTurn`

produce just a simple `Msg`

. The purpose of `wrapNextMsgWithCmd`

is to wrap the desired command around that message:

```
wrapNextMsgWithCmd : ( Model, Msg ) -> ( Model, Cmd Msg )
wrapNextMsgWithCmd ( nextModel, nextMsg ) =
( nextModel, wrapWithCmd nextMsg )
wrapWithCmd : Msg -> Cmd Msg
wrapWithCmd nextMsg =
case nextMsg of
DoNothing ->
Cmd.none
Take _ ->
Cmd.none
ComputerTake _ ->
Cmd.batch
[ Task.perform
(\_ -> nextMsg)
(Process.sleep 3000)
]
```

Here we see that if we want the next message sent to `update`

to be a computer turn (`ComputerTake`

), then we produce a `Cmd`

that includes this message. The `Cmd`

will run the `Process.sleep`

task for 3 seconds, then it will call update with `nextMsg`

.

`updateWithoutCmd`

handles the basic game play:

```
updateWithoutCmd : Msg -> Model -> ( Model, Msg )
updateWithoutCmd msg model =
case msg of
Take selectedMatchsticks ->
humanPlayerTakesTurn model selectedMatchsticks
ComputerTake selectedMatchsticks ->
computerPlayerTakesTurn model selectedMatchsticks
DoNothing ->
( model, DoNothing )
humanPlayerTakesTurn : Model -> Int -> ( Model, Msg )
humanPlayerTakesTurn model selectedMatchsticks =
case model.currentPlayer of
HumanPlayer ->
tryToPlayTurn
model
selectedMatchsticks
(computerPlaysNextOrEndOfGame
model.matchsticks
selectedMatchsticks
)
ComputerPlayer ->
rejectPlayerTurn model
computerPlayerTakesTurn : Model -> Int -> ( Model, Msg )
computerPlayerTakesTurn model selectedMatchsticks =
case model.currentPlayer of
ComputerPlayer ->
tryToPlayTurn model selectedMatchsticks DoNothing
HumanPlayer ->
rejectPlayerTurn model
```

This code makes sure that if a player tries to take matchsticks, it's actually their turn. It also checks that the number of matchsticks is valid. `rejectPlayerTurn`

may not really be needed, since we grey out the input buttons, but as someone who's written a lot of server-side code, old habits die hard!

We can see that after a human player takes a turn, we generate the message for the computer player to play next with `computerPlaysNextOrEndOfGame`

:

```
computerPlaysNextOrEndOfGame : Int -> Int -> Msg
computerPlaysNextOrEndOfGame matchsticks selectedMatchsticks =
if gameOver (matchsticks - selectedMatchsticks) then
DoNothing
else
computerTakesNextTurn <|
takeMatchsticks matchsticks selectedMatchsticks
computerTakesNextTurn : Int -> Msg
computerTakesNextTurn matchsticks =
ComputerTake <| Tuple.second <| matchsticksToTake matchsticks
```

We can see that if the game is not over after the human player's current turn, then we generate the appropriate `ComputerTake`

message. This message will include the `matchsticksToTake`

for the computer player based on the number of matchsticks left after the current player's selection.

## Elm Architecture

The basic elm architecture is a fairly simple cycle: When the user interacts with the UI, this triggers the appropriate message to be sent to the `update`

function. `update`

returns a new model with changes based on the message it received. The elm runtime updates its internal state with this new model, and uses it to refresh the view.

`update`

also returns a `Cmd`

which can be used ask elm to perform side-effects. elm is a pure language, so none of the functions in elm directly perform I/O. They just return `Cmd`

objects with instructions. The `elm`

runtime uses these commands to perform the actual I/O, but it's done as a separate step.

In addition to commands, elm also supports subscriptions, which can be used to handle periodic updates, but we aren't using subscriptions in this example.

## Demo

You can view a demo of this example at codepen:

## Source Code

All of the source code is available at github:

## nestedsoftware / matchstick-game

### 21 matchsticks game implemented in elm

This code requires elm to be installed.

- To compile the code and generate Main.js, run
`elm make src/Main.elm --output=Main.js`

- To run the unit tests, run
`elm-test`

. - Demo

Both commands can be run from the root directory of the project.

Rules of the game: There are 21 matchsticks. Two players take turns, removing 1, 2, or 3 matchsticks at a time. The player who is forced to remove the last matchstick loses.

Awesome, I've also built a similar game before when I was learning Angular.

My solution is different though, I get the computer input by subtracting the player input to 4.

x = 4 - playerInput

If the player inputs 1, the computer would input 3.

If the player inputs 2, the computer would input 2.

If the player inputs 3, the computer would input 1.

Live demo

Thanks for the comment @devkumi ! If the human player takes the first turn (and therefore can't win, no matter what), then that's all you need to do!

This version forces the computer to play first, which means the computer needs to know whether the human player has made a mistake or not. If the human player makes a mistake, then the remainder,

`r = (count - 1) mod 4`

is used to compute the right move for the computer. I think in your case it would be`4 - (count mod 4)`

because you're going up from 0 to 21.