dev.to staff

Posted on Sep 9, 2019

Daily Challenge #62 - Josephus Survivor

#challenge

Josephus and his forty men were trapped in a cave by the Romans. Rather than reveal secrets or be captured, they opted for a mass suicide. They gathered in a circle and killed one man every three. The man who survived was supposed to end his own life.

Your challenge for today is to write a function that will return the winning survivor of a Josephus permutation. It should accept two parameters, the amount of people in total n, and the amount of steps between eliminations k.

For example, with n=7 and k=3 josephus_survivor(7,3) should act this way:

josephus_survivor(7,3) => means 7 people in a circle;
one every 3 is eliminated until one remains
[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out
[1,2,4,5,7] => 6 is counted out
[1,4,5,7] => 2 is counted out
[1,4,5] => 7 is counted out
[1,4] => 5 is counted out
[4] => 1 counted out, 4 is the last element - the survivor!

Good luck! Happy coding.

Today's challenge comes from GiacomoSorbi on CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (8)

Donald Feury • Sep 9 '19 • Edited

I needed to Go find the formula for this one. This is essentially my implementation of it in Go.

Formula was found here en.wikipedia.org/wiki/Josephus_pro...

Would be interesting to see a non recursive implementation of this, as Go does not optimize recursion very well from what I understand.

josephus.go

package josephus

import "math"

// Survivor indicates which man will be the survivor of a Josephus permutation
func Survivor(size uint, steps uint) uint {
    if size == 1 {
        return 0
    }

    if size < steps {
        return (Survivor(size-1, steps) + steps) % size
    }

    floor := size - uint(math.Floor(float64(size/steps)))

    return uint(math.Floor(float64((steps * ((Survivor(floor, steps) - size%steps) % floor)) / (steps - 1))))
}

josephus_test.go

package josephus

import "testing"

type testCase struct {
    description string
    input       []uint
    expected    uint
}

func TestSurvivor(t *testing.T) {
    testCases := []testCase{
        {
            "1 man",
            []uint{1, 5},
            0,
        },
        {
            "more men than steps",
            []uint{7, 3},
            3,
        },
        {
            "less men than steps",
            []uint{3, 5},
            0,
        },
        {
            "another with more men than steps",
            []uint{15, 2},
            14,
        },
        {
            "another with less men than steps",
            []uint{5, 17},
            3,
        },
    }

    for _, test := range testCases {
        if result := Survivor(test.input[0], test.input[1]); result != test.expected {
            t.Fatalf("FAIL: %s - Survivor(%+v): %d - expected: %d", test.description, test.input, result, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

Melvin Yeo • Sep 10 '19

Correct me if I'm wrong.

Your test case for n = 7, k = 3 checks for an expected result of 3, but based on the same example above, the results should be 4.

Is there a mistake in the test cases?

Donald Feury • Sep 10 '19 • Edited

No its right, what the Josephus permutation is doing is telling us which solider will survive after all eliminations have happened. The example above gives us soldier 4, which, in a standard array would be position 3 in the array as arrays start at 0 and count up.

Example:

In Go, if you had a slice that represented the group of solders in the example, you would get the index of soldier in the slice that will survive the elimination.

If you wanted to print a more human readable output using the result of the Josephus permutation, you would simply do something like:

soldiers := []string{"Bob", "Mark", "DatBoi", "John", "Josephus", "Donald", "Melvin"}
survivor := josephus.Survivor(len(soldiers), 3)
fmt.Println("Soldier %d: '%s' - survived!", survivor + 1, soldiers[survivor])

Which would produce the output:

"Soldier 4: 'John' - survived!"

Melvin Yeo • Sep 11 '19

I see, if the array starts from 0, the results from your test cases would make sense.

Thanks for clarifying!

Donald Feury • Sep 11 '19

Thank you for the question! In the future if my test cases look different than the examples given I will clarify the reason in my original post.

LordApple • Sep 9 '19 • Edited

C++

    constexpr auto Josephus = [](int max, int step, const auto fn){
        if(step == 2){
            return ~(1 << static_cast<int>(log2(max * 2))) & ((max << 1) | 1);
        }

        if(max == 1){
            return 1;
        }
        return (fn(max - 1, step, fn) + step - 1) % max + 1;
    };

Avalander • Sep 10 '19 • Edited

Wow, this one was hard to figure out.

Haskell

survivor :: Int -> Int -> Int
survivor k step =
  survivor' step [ 1 .. k ]
  where
    survivor' :: Int -> [Int] -> Int
    survivor' step [x] = x
    survivor' step xs  = survivor' step (remove_at step' xs)
      where
        step' = reduce_step (length xs) step

    reduce_step :: Int -> Int -> Int
    reduce_step len step
      | step <= len = step
      | otherwise   = reduce_step len (step - len)

    remove_at :: Int -> [Int] -> [Int]
    remove_at i xs = (drop i xs) ++ (take (i - 1) xs)

Melvin Yeo • Sep 11 '19

In Python, not the best answer though, with a complexity of O(n)

def josephus_survivor(n, k):
    arr = list(range(1, n+1))
    idx = 0
    step = k - 1

    while len(arr) > 1:
        idx = (idx + step) % len(arr)
        arr.pop(idx)

    return arr.pop()

DEV Community

Daily Challenge #62 - Josephus Survivor

Top comments (8)

Haskell

Read next

Tìm hiểu Object trong JavaScript

VizBlend: Solving the Challenge of Interactive Data Reporting with Python 🚀

Building a File Upload App with TypeScript, React, and Auto-Drive API

Serverless semantic search - AWS Lambda, AWS Bedrock, Neon