# Re: [stack] the josephus problem

## sa@dfa.com — 2000-07-05 15:08:45

    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