Let’s begin by describing Josephus problem:

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.

Sound pretty interesting right ? If you were in this situation, which seat would you sit in?

Let’s start with two soldiers sitting in two chairs, in this case it’s pretty straightforward. If we start with soldier 1, then soldier 1 kills soldier 2 and he survives, so in case of two soldiers, chair 1 is the safest.

Let’s extend this logic to 3 chairs, soldier 1 kills soldier 2 and soldier 3 kills soldier 1. Chair 3 is the safest.

This is easy to do for few soldiers, but when the number of soldiers increase it becomes difficult to calculate. Surely there must be a better approach, let’s draw out a chart showing who survives based on the number of soldiers.

There’s an interesting observation here, for every 2^n th seat 1 always wins and for anything between 2^n and 2^(n+1) the winners are just consecutive odd numbers. We have a pattern here.

For a given configuration of X soldiers, find the closest 2^n that is less than X. Then the safest seat is 2 * [X - (2^n)] + 1. Here we find the closest 2^n number and jump those many numbers in the odd number scale.

Let’s take an example, for X = 5, nearest (2^n) is 4 which is 2², so 2 * [5 - 2²] + 1 is 3. Which is the right answer.

There you have it, now you know which seat to pick if you ever face such a situation. Choose wisely 😉.

But this isn’t fun. It’d be fun to actually simulate the whole process right? Let’s do that.

We’ll use p5.js to simulate this using JavaScript(why JavaScript you ask? read my bio).

We can split the project into two main blocks:

1. Soldier class that knows how to draw itself on the screen, change states from alive to dead and kill another soldier.
2. The actual algorithm that runs the simulation.

Here’s what a soldier class would look like:

Now that we the soldier class out of the way, let’s see how the main algorithm works.

Let us store all the users in a circular array, soldier class has two static variables which store the total number of soldiers and the number of soldiers alive.

p5.js has two critical functions setup and draw . In the setup function, we will initialise coordinates for all soldier objects. These soldier objects need to be drawn in a circular fashion, each of the soldier has a x and y value, these determine where the soldier will be drawn on the screen.

We need to be able to draw points in a circular fashion.

Each point on the circle represents a soldier. r is the distance the soldier is going to be placed from the center of the circle. We space all soldiers equidistantly on the circle’s circumference.

We need to convert Cartesian coordinates to polar and plot equal number of points on the circle.

360 / numberOfSoldiers;

Here the numberOfSoldiers is a arbitrary constant we set at the beginning of the simulation, this can be altered to find solutions for various values of n.

Dividing 360⁰ into equal angles and plotting them on the circle.

Now to the final part of the simulation, the main simulation algorithm:

1. Check if the number of soldiers alive is equal to 1, if yes then his seat number is the safest, end the simulation.
2. If the number of soldiers alive is greater than 1, then find the soldier who is alive and store his seat number let’s call this prevIndex, now loop through the array and find the next soldier who is alive, let’s save his seat number as currentIndex , now soldier at prevIndex kills soldier at currentIndex . While iterating through the array make sure you account for index overflow by implementing a circular array.
3. Goto step 1

Here’s what the final output looks like -

The code is available on github( view ).

Back to posts