Lambda Recursion Case Study - The Josephus Problem

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!