The Challenge

The Josephus Problem is a mathematical problem based on a firsthand account from Flavius Josephus (I won’t go into a history lesson here, but you can find plenty of details online about his grisly account.).

The goal is simple. You are provided with an array of integers and an interval – ‘k’. For example, 41 integers with k being 3. If you eliminate every 3rd integer, then what will be the last remaining number?

This is how the elimination looks:

Approaches to solving

A shortcut exists with a bitwise operation to solving this problem when k = 2 where the least signification digit is shifted to the end:

There are other approaches for when  k = 3 but I was more interested in a general solution capable of solving for when k = (2 to 10) and the number of integers provided is = (2 to 41).

The scrapped approaches:

1. A recursive SCAN.  This memory intensive approach’s goal was to SCAN the array until the last digit remained.  The issues being carrying over the last removed position to the next round and the removal of integers.  I played with keeping the integer places with 0s or #N/A but it got messy, so it was scrapped early.

2. Wrap/Drop – This approach was tempting because it was capable of eliminating a good chunk of integers with each round.  On the first pass through, the last column on the right was always dropped because WRAPROWS used ‘k’ to wrap.  The big problem being the padding of jagged arrays with 0s.  It was very easy to lose track of which column would be removed next.  Then there was always the problem of how to proceed when the number of integers remaining was less than or equal to k.

 n <= k

At some point I gave up on the Wrap/Drop approach and simplified the function.  I found I was solving the problem in many cases, but the accuracy wasn’t 100% correct.  The big problem being what happens when n <= k

The solution

I’m interested in any different approaches someone may have to solving this problem.  Particularly with dynamic arrays, and recursion, or even making the Wrap ‘n Drop method work.  I usually use dynamic arrays and not recursion but went with recursion for this project because I’ve been devoting a lot of hours to studying recursion lately (and this is good practice!).

My annotated solution follows.

// Recursion Case Study – The Josephus Problem
// Function created by Patrick – June 2024
// Challenge from Edabit (Python):
//https://edabit.com/challenge/Mb8KmicGqpP3zDcQ5

// J – for Flavius Josephus
// arr – supplied integers
// k – this represents the interval for elimination each round. If k is 3, then integers
// 3, 6, 9, 12, etc. will be eliminated in the first pass through the array.

J = LAMBDA(arr, k,
LET(
//These integers are retained
spared, TAKE(arr, k – 1),

//Stack the existing array with integers retained.
acc, VSTACK(arr, spared),

// How many integers remain?
n, COUNT(arr),

//Discard integers from the top of ‘acc’.
//Saved integers have been moved to bottom of stack.
eliminate, DROP(acc, k),

//an array of integers to be used when n <= k.
i, SEQUENCE(n),

//This function is used when n <= k. MOD must be used to ‘wrap around’ since
//the method for removal used above cannot be used when few integers remain.
//This function determines the safe spots for each of the remaining
//rounds when n <= k so the remaining integer can be determined.
safe, REDUCE(
0,
i,
LAMBDA(a, v,
IF(v = 1, 0, MOD(TAKE(a, -1) + k, v))
)
) + 1,

//Get the last integer remaining.
last, INDEX(arr, safe),

//Utlize the keep ‘n drop method of elimination
//until n <= k then do some modular arithmetic.
decide, IF(n >= k, eliminate, last),

IF(n < k, last, J(decide, k))
)
)

​The ChallengeThe Josephus Problem is a mathematical problem based on a firsthand account from Flavius Josephus (I won’t go into a history lesson here, but you can find plenty of details online about his grisly account.). The goal is simple. You are provided with an array of integers and an interval – ‘k’. For example, 41 integers with k being 3. If you eliminate every 3rd integer, then what will be the last remaining number?This is how the elimination looks: Approaches to solvingA shortcut exists with a bitwise operation to solving this problem when k = 2 where the least signification digit is shifted to the end:There are other approaches for when  k = 3 but I was more interested in a general solution capable of solving for when k = (2 to 10) and the number of integers provided is = (2 to 41). The scrapped approaches:1. A recursive SCAN.  This memory intensive approach’s goal was to SCAN the array until the last digit remained.  The issues being carrying over the last removed position to the next round and the removal of integers.  I played with keeping the integer places with 0s or #N/A but it got messy, so it was scrapped early.2. Wrap/Drop – This approach was tempting because it was capable of eliminating a good chunk of integers with each round.  On the first pass through, the last column on the right was always dropped because WRAPROWS used ‘k’ to wrap.  The big problem being the padding of jagged arrays with 0s.  It was very easy to lose track of which column would be removed next.  Then there was always the problem of how to proceed when the number of integers remaining was less than or equal to k. n <= k At some point I gave up on the Wrap/Drop approach and simplified the function.  I found I was solving the problem in many cases, but the accuracy wasn’t 100% correct.  The big problem being what happens when n <= k The solutionI’m interested in any different approaches someone may have to solving this problem.  Particularly with dynamic arrays, and recursion, or even making the Wrap ‘n Drop method work.  I usually use dynamic arrays and not recursion but went with recursion for this project because I’ve been devoting a lot of hours to studying recursion lately (and this is good practice!). My annotated solution follows.// Recursion Case Study – The Josephus Problem
// Function created by Patrick – June 2024
// Challenge from Edabit (Python):
//https://edabit.com/challenge/Mb8KmicGqpP3zDcQ5

// J – for Flavius Josephus
// arr – supplied integers
// k – this represents the interval for elimination each round. If k is 3, then integers
// 3, 6, 9, 12, etc. will be eliminated in the first pass through the array.

J = LAMBDA(arr, k,
LET(
//These integers are retained
spared, TAKE(arr, k – 1),

//Stack the existing array with integers retained.
acc, VSTACK(arr, spared),

// How many integers remain?
n, COUNT(arr),

//Discard integers from the top of ‘acc’.
//Saved integers have been moved to bottom of stack.
eliminate, DROP(acc, k),

//an array of integers to be used when n <= k.
i, SEQUENCE(n),

//This function is used when n <= k. MOD must be used to ‘wrap around’ since
//the method for removal used above cannot be used when few integers remain.
//This function determines the safe spots for each of the remaining
//rounds when n <= k so the remaining integer can be determined.
safe, REDUCE(
0,
i,
LAMBDA(a, v,
IF(v = 1, 0, MOD(TAKE(a, -1) + k, v))
)
) + 1,

//Get the last integer remaining.
last, INDEX(arr, safe),

//Utlize the keep ‘n drop method of elimination
//until n <= k then do some modular arithmetic.
decide, IF(n >= k, eliminate, last),

IF(n < k, last, J(decide, k))
)
)   Read More

​