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

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 %}