Forum Discussion
Patrick2788
Jul 08, 2024Silver Contributor
Lambda Recursion Case Study - The Josephus Problem
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))
)
)
- djclementsBronze Contributor
Patrick2788 Nice challenge. Here's my take...
FJ: =LAMBDA(array,k,[offset], LET( n, ROWS(array), m, MOD(SEQUENCE(n) - offset, k), IF(n = 1, array, FJ(FILTER(array, m), k, k - TAKE(m, -1))) ) )
Or, to allow for both vertical and horizontal arrays (or 2D arrays):
FJ: =LAMBDA(array,k,[offset], LET( a, TOCOL(array), n, ROWS(a), m, MOD(SEQUENCE(n) - offset, k), IF(n = 1, a, FJ(FILTER(a, m), k, k - TAKE(m, -1))) ) )
When applied, the syntax would be:
=FJ(SEQUENCE(integers), interval)
Cheers! π
- Patrick2788Silver Contributor
I like your solution because it's simple but still clever. One of the things I like to do with recursion is to add a 'counter' so I can step through the progressions. The counter is removed in the final function.
Stepping through your function:
This deals with the issue of finding the position of last discarded very elegantly. Thank you for sharing!
In researching this problem it seems it's often regarded as a difficult challenge no matter the coding language used to solve it. I found this challenge on Edabit where it was listed under Python (and several other languages). Excel is not yet included in these coding challenge web sites but that could soon change!
- djclementsBronze Contributor
Patrick2788 Great tip for using a counter to show the results of a variable at any given step! The only thing I've used a counter for thus far is to return the total iteration count when recursion limits are a concern, or if I'm just interested to see how many iterations it takes to return the final result. Also, I haven't tried Excel Labs yet, but usually build and test my recursive LAMBDA functions directly in-cell using LET with a fixed-point combinator (ME). For example:
=LET( FJ, LAMBDA(ME,array,k,[offset],[i],[show_i], LET( n, ROWS(array), m, MOD(SEQUENCE(n) - offset, k), IF( n = 1, IF(show_i, i + 1, array), ME(ME, FILTER(array, m), k, k - TAKE(m, -1), i + 1, show_i) ) ) ), FJ(FJ, SEQUENCE(250000), 3,,, TRUE) )
While reviewing my formula again, I realized that the offset variable could be used as the optional [start] argument of the SEQUENCE function by subtracting it from 1, rather than subtracting it from the entire sequence array. In order to do so, however, the data type must be taken into consideration, because SEQUENCE does not work properly when array objects (type 64) are passed to its arguments. As it's currently written, k - TAKE(m, 1) returns a single element array (e.g. {1}), so it needs to be coerced into a single numeric value (type 1). The easiest way to do so is to use the implicit intersection operator (@).
FJ: =LAMBDA(array,k,[offset], LET( n, ROWS(array), m, MOD(SEQUENCE(n,, 1 - offset), k), IF(n = 1, array, FJ(FILTER(array, m), k, k - @TAKE(m, -1))) ) )
Alternatively, the offset variable could be coerced with:
- SUM(k, -TAKE(m, -1))
- k - INDEX(m, n, 1)
Regarding the overall logic used, when n < k it just keeps iterating through the interval positions until the next item is removed (the offset value continues on from the last m value from the previous iteration). The higher the interval (k), the more iterations are needed to remove the final items. For example, if k is set to 10, when the number of items remaining (n) is 2, it could take up to 5 iterations to remove the final item.
I quite enjoy working with lambda recursion and am always looking for a good challenge. Thank you for sharing!
p.s. I thought I saw a previous challenge shared by you that had something to do with pyramid patterns generated using OR and XOR logic but couldn't find it again when I went back and looked. I'd love to see that one again. π
UPDATE: an alternative method using REDUCE with the same logic could be:
FJ: =LAMBDA(array,k,[i], LET( i, IF(ISOMITTED(i), 100, i), j, REDUCE(VSTACK(0, array), SEQUENCE(i), LAMBDA(p,v, LET( a, DROP(p, 1), n, ROWS(a), m, MOD(SEQUENCE(n,, 1 - @p), k), IF(n = 1, p, VSTACK(k - TAKE(m, -1), FILTER(a, m))) ) ) ), n, ROWS(j), IF( n = 2, INDEX(j, n), "Not enough iterations ( [i] = " & i & "; " & n - 1 & " items remain )" ) ) )
The only issue with this method is that the number of iterations needs to be determined beforehand. I'm not too sure how that could be calculated, so I left it up to the user to adjust the number of iterations [i] as needed. For example:
=FJ(SEQUENCE(1000), 500, 3240)
Fun, fun, fun!