Forum Discussion
Lambda Recursion Case Study - The Josephus Problem
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! 🙂
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!