the josephus problem

sa@dfa.com — 2000-07-05 14:05:13

from comp.lang.apl:



"The [josephus problem] is where a number of prisoners are arranged

in a circle and the executioner, standing in the middle, starts at a

given place in the circle, passes by a set number of prisoners and then

shoots one. The executioner then repeats the process, starting at the

next prisoner in the circle. This is continued until there is a single

prisoner standing whose life is then spared. The problem is to determine

for a given number of prisoners and a given gap which prisoner is the

last one standing." [jim ryan]



in conk, with 12 prisoners and a gap of 3:



     12 dom 1+

    [1 2 3 4 5 6 7 8 9 10 11 12]

      [1 drop 3 rot] scanto

    [[1 2 3 4 5 6 7 8 9 10 11 12] [5 6 7 8 9 10 11 12 2 3 4] [9 10 11 12 2

3 4 6 7 8] [2 3 4 6 7 8 10 11 12] [7 8 10 11 12 3 4 6] [12 3 4 6 8 10 11]

[8 10 11 3 4 6] [4 6 10 11 3] [3 6 10 11] [6 10 11] [11 10] [10] nullint]

     [swap dvl first] prior

    [1 5 9 2 7 12 8 4 3 6 11 10]

     last

    10



using lambda notation:



      josephus ==

     [x]

     [[1 drop x rot] scanto [swap dvl first] prior last]

     ->



n dom is the list [0 1 2 ... n-1]

x y dvl is the difference between two lists x and y.

x n rot rotates the list x n positions leftwards.

x n drop drops the first n elements of list x.

x [p] scanto keeps applying p to its own result until either its

result matches twice in a row, or its result matches the initial

argument x.

x [p] prior applies p between elements of list x.