urk. that should be:
josephus == [x][[x rot 1 drop] scanto [swap dvl first] prior last] ->
i.e.
12 dom 1 +
[1 2 3 4 5 6 7 8 9 10 11 12]
[3 rot 1 drop] scanto
[[1 2 3 4 5 6 7 8 9 10 11 12] [5 6 7 8 9 10 11 12 1 2 3] [9 10 11 12 1 2 3
5 6 7] [1 2 3 5 6 7 9 10 11] [6 7 9 10 11 1 2 3] [11 1 2 3 6 7 9] [6 7 9 11
1 2] [1 2 6 7 9] [9 1 2 6] [9 1 2] [1 2] [1] nullint]
[swap dvl first]prior
[4 8 12 5 10 3 11 7 6 9 2 1]
last
1
type less, think more.
sa@...
To: concatenative@egroups.com
07/05/00 cc:
10:05 AM Subject: [stack] the josephus problem
Please
respond to
concatenative
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.
------------------------------------------------------------------------
Was the salesman clueless? Productopia has the answers.
http://click.egroups.com/1/4633/7/_/_/_/962806105/
------------------------------------------------------------------------
To unsubscribe from this group, send an email to:
concatenative-unsubscribe@egroups.com