The Josephus Problem

…is a famous puzzle in computer science and mathematics, related to a certain counting-out game.

From Wikipedia:

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.

The “standard” variant of this puzzle is to skip one person a time. Let’s focus on this, for now.

Here’s a visualisation for how the puzzle plays out with 13 people in the circle:

Credit to Numberphile for the above animation

The order of deaths is: 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3; which leaves position 11 as the winner.

How can we easily determine the winner in general? Let’s write some code.


The Mathematical Solution

Let’s take a quick look at the winning position, in the first few cases:

+---------+--------+
| Players | Winner |
+---------+--------+
| 1 | 1 | <--
| 2 | 1 | <--
| 3 | 3 |
| 4 | 1 | <--
| 5 | 3 |
| 6 | 5 |
| 7 | 7 |
| 8 | 1 | <--
| 9 | 3 |
| 10 | 5 |
| 11 | 7 |
| 12 | 9 |
| 13 | 11 |
| 14 | 13 |
| 15 | 15 |
| 16 | 1 | <--
+---------+--------+

A clear pattern seems to have emerged: When the number of players is a power of 2 (1, 2, 4, 8, 16, …), the first position always wins. This fact is best understood when seen visually: After each cycle of the circle, it will always be player 1’s turn!

In fact, this symmetry can be used to generalise the solution mathematically. Without going into details of the proof (Wikipedia can fill you in there), the problem always quickly simplifies to a scenario such as the above — and therefore one can derive the following formula for the winning position:

Where n is the number of players

Turning this equation into ruby code is fairly straightforward:

def josephus(n)
2 * (n - 2 ** Math.log(n, 2).floor) + 1
end

This is a great solution, but let’s suppose you don’t know about this “magic” formula — for instance, what if this question were posed to you during a job interview?

How might you try to solve the problem “manually”, by actually playing out the game? Let’s write something a little more fun.


Playing The Game

Given how concise and expressive the ruby language is, there are many interesting ways to code this. Let’s look at a few of them.

Throughout all of these examples, let players be an array of integers representing each position at the table. For example, in the case of 10 players: players = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. (Apologies to those who insist all arrays must start at zero!)

In each code sample, we’ll delete elements from that array, in the order of execution. So again, using the above example of 10 players, we want a final result of players = [5] — since we know that’s the winning seat.

  1. Turning the table
until players.size == 1
players.rotate!
players.delete_at(0)
end

By using Array#rotate! and Array#delete_at (note: we could also accomplish this with Array#shift but I feel that’s less expressive), we can solve the problem by effectively “turning the table” and always executing the player in the “first” seat.

2. Around and around

should_execute = [false, true].cycle
until players.size == 1
players
.delete_if { should_execute.next }
end

Here’s an interesting one. First, using Array#cycle, we define an infinite enumerator: [false, true, false, true, false, ...]; the next value represents whether the next player should be executed.
Then withArray#delete_if, we then loop through all the remaining players, over and over, until only one is left.

3. Tracking the offset

offset = 0
until players.size == 1
next_offset = offset + players.count % 2
players.delete_if.with_index do |player, position|
(position + offset) % 2 == 1
end
offset = next_offset
end

This version’s a bit uglier. But I’ve included it to illustrate a point:
Naively, when first tackling this problem, you may falsely assume that you can just loop through the array over and over, deleting odd-indexed positions. However, this assumption fails, for example, when there are 5 players: On the second loop, we need to delete even-indexed players from the array.

You could keep track of this odd vs even offset via a boolean variable, but the logic above is written with the intention to be “generalised” (as discussed later on) for any number of skips.

There are several possible variations of this method, using e.g.Array#select , Enumberable#each_slice or Array#values_at; but they all suffer from this same “offset” problem.

4. Modular counting

delete_index = 1
until players.size == 1
players.delete_at(delete_index)
delete_index += 1
delete_index %= players.size
end

Utilising the rarely-seen %= operator, we can simplify this “offset” solution. After each iteration of the loop, if we find ourselves “out of bounds” then we jump back to the correct position from the start of the array.


A Generic Method

Taking the first solution above, we can write a method to solve the “standard” Josephus Problem as follows:

def josephus_winner(player_count)
players = (1..player_count).to_a
  until players.size == 1
players.rotate!
players.delete_at(0)
end
players.first
end

And in fact, we can now quite easily generalise this solution for skipping any number of players between executions:

def josephus_winner(player_count, skips = 1)
players = (1..player_count).to_a
  until players.size == 1
players.rotate!(skips)
players.delete_at(0)
end
players.first
end

Generalising the other solutions shown above should be relatively straightforward; I leave that as an exercise for the reader.

Can you think of any other clever solutions? Let me know in the comments below.