Challenge #7 – The Josephus Problem

In this mythical-historical mathematical problem, where you end up standing can be the difference between life and death. We’ll let Numberphile explain the problem and solution in the following video.

Challenge

The challenge is to write a twig macro that accepts at least one parameter n (an integer representing the total number of people in the circle) and outputs the position in which one must initially stand in the circle in order to be the last person standing and therefore the only survivor.

{% set n = 41 %}

{{ josephus(n) }}    // Outputs 19

An online search will yield various approaches to solving this problem, but the challenge here is to come up with your own twig-specific solution using the information provided in the video.

Rules

The macro must output an integer as the solution, given the parameter as described above. It should not rely on any plugins and the code will be evaluated based on the following criteria in order of priority:

1. Originality
2. Readability
3. Brevity

The algorithm you use should be based around one of the solutions presented in the video. The code should be readable, concise and non-repetative.

Tips

The problem can be solved in twig using either an iterative or a recursive approach. We covered recursion in a previous challenge (#4) and this may be a good opportunity to put your understanding of it to the test.

Solution

The math­em­at­ic­al for­mula to the prob­lem is provided in the video and can be sum­mar­ised as follows.

If n = p + L, where n is the total num­ber of people and p (referred to as 2^a in the video) is the greatest power of 2 that is less than n, then the win­ning pos­i­tion is 2L + 1.

In order to write an algorithm that uses this for­mula, we simply need to cal­cu­late p, the greatest power of 2 that is less than n, and then we can cal­cu­late L as L = n - p.

We begin with an iter­at­ive approach in which we begin with p = 1 and increase the power of 2 until we reach a num­ber that is great­er than n.

{% set p = 1 %}

{% for i in 0..n %}
    {% if p <= n %}
        {% set p = p * 2 %}
    {% endif %}
{% endfor %}

After the loop has com­pleted, we are left with a value for p that is one power of 2 great­er than n. So we simply divide p by 2 to get the cor­rect value.

{% set p = p / 2 %}

Now all that is left is to cal­cu­late L and plug it into the for­mula above to out­put the solution.

{% set L = n - p %}

{{ (2 * L) + 1 }}

Put­ting this all togeth­er in a macro gives us the fol­low­ing iter­at­ive solution.

{% macro josephus(n) %}
    {% set p = 1 %}

    {% for i in 0..n %}
        {% if p <= n %}
            {% set p = p * 2 %}
        {% endif %}
    {% endfor %}
    
    {% set p = p / 2 %}
    {% set L = n - p %}

    {{ (2 * L) + 1 }}
{% endmacro %}

{% from _self import josephus %}
{{ josephus(n) }}

We clearly do not need to iter­ate over the entire range of 0..n to find p, but since we do not have the equi­val­ent of a while loop in twig, we take the per­form­ance hit (the num­ber of times would actu­ally be Log₂n).

Sim­il­ar solu­tions: Spenser Han­non.

A recurs­ive approach is also pos­sible, since in each iter­a­tion above we are solv­ing a sub­set of the prob­lem. In the recurs­ive approach, we keep track of the value of p using a second parameter.

{% macro josephus(n, p) %}

    {% if p <= n %}
        {% from _self import josephus %}
        {{ josephus(n, p * 2) }}
    {% else %}
        {% set p = p / 2 %}
        {% set L = n - p %}
        
        {{ (2 * L) + 1 }}
    {% endif %}

{% endmacro %}

{% from _self import josephus %}
{{ josephus(n, 1) }}

The res­ult is the same, but note how we recurs­ively call the macro only as long as p <= n. As soon as that con­di­tion does not hold true, we out­put the cal­cu­lated result.

So we have gone from an iter­at­ive solu­tion with a time com­plex­ity of O(n) to a recurs­ive one with a time com­plex­ity of O(Log₂n).

The algorithms above are based on the math­em­at­ic­al solu­tion presen­ted in the video and are per­form­ant ways of cal­cu­lat­ing the res­ult. We could also take a dif­fer­ent approach and try to solve the prob­lem more ​“com­pu­ta­tion­ally”. For example, rather than work­ing with the val­ues n and p, we could begin with an array of the range 1..n and remove a value from it in each recurs­ive call until we are left with an array with only a single value, the result.

{% macro josephus(people, next) %}

    {% if people|length > 1 %}
        {% set next = next % people|length  %}
        {% set people = people|slice(0, next)|merge(people|slice(next + 1))  %}
        
        {% from _self import josephus %}
        {{ josephus(people, next + 1) }}
    {% else %}
        {{ people[0] }}
    {% endif %}

{% endmacro %}

{% from _self import josephus %}
{{ josephus(1..n, 1) }}

This macro takes as para­met­ers an array people and an integer next which rep­res­ents the 0‑index pos­i­tion of the next per­son to be removed. If the value of n is great­er than the num­ber of remain­ing people then we use its mod­ulo value. We then manip­u­late the people array using the slice and merge fil­ters to remove the value at pos­i­tion next. This is rather poor imple­ment­a­tion in terms of per­form­ance as rather than work­ing with an integer as we did in the pre­vi­ous solu­tions, we are work­ing with arrays.

Below is a com­par­is­on of the per­form­ance pro­fil­ing of the 3 approaches described above using the Twig Pro­filer plu­gin and a value of n = 4100 (to help exag­ger­ate the differences).

Iter­at­ive Approach

Recurs­ive Approach

Using Arrays

It is obvi­ous to see that the recurs­ive approach is by far the most per­form­ant with a pro­cessing time of only 0.6ms and a peak memory of 20MB. The iter­at­ive approach comes in second place with a pro­cessing time of 3.1 ms and a peak memory of 21MB. The per­form­ance hit is because of the unne­ces­sary iter­a­tions that it per­forms. In last place is the approach using arrays with a whop­ping pro­cessing time of 614.2ms and a massive peak memory of 455MB. This is due to the fact that we are manip­u­lat­ing arrays with thou­sands of val­ues in them. It would have been made even worse had we used an iter­at­ive approach in the solution.

The per­form­ance pro­fil­ing presen­ted above will hope­fully encour­age you to take cau­tion when writ­ing algorithms that manip­u­late arrays with­in loops or recurs­ive func­tions. This applies in any pro­gram­ming lan­guage and can even affect what might be con­sidered as com­mon manip­u­la­tions such as using an array_merge with­in a loop in PHP.

$values = [];

foreach ($arrays as $array) {
    $values = array_merge($values, $array);
}

A more per­form­ant way, as explained here, is to modi­fy the code and use the array_merge oper­a­tion only once at the end. 

$valueSets = [[]];

foreach ($arrays as $array) {
    $valueSets[] = $array;
}

$values = array_merge(...$valueSets);

Here we use argu­ment unpack­ing to unpack the array $valueSets into an argu­ment list using the ​“splat” oper­at­or … (gotta love the nam­ing), thereby redu­cing the num­ber of merges to one. The res­ults of these bench­marks show that there is sig­ni­fic­ant per­form­ance to be gained.

Submitted Solutions

• Spenser Hannon

Solution submitted by Spenser Hannon on 7 February 2019.

{% macro josephus(number) %}
    {%- set pow = 1 -%}

    {%- for i in 0..number if pow < number -%}
        {%- set pow = pow * 2 -%}
    {%- endfor -%}

    {%- if pow > number -%}
        {%- set pow = pow / 2 -%}
    {%- endif -%}

    {{ (number - pow) * 2 + 1 }}
{% endmacro %}