# The Josephus Problem

The Josephus Problem is deceptively simple. A number of people stand in a circle. (Let’s call this number N.) They agree to count around the circle, and every /M/th person will be killed. As they go around the circle, in what order do they die? Another way of looking at it is: who is the last person left alive?

For an interesting introduction, I recommend checking out the Wikipedia article.

I recently found this problem described in the 2nd edition of Sedgwick’s Algorithms, and thought it would be fun to implement in Scheme. Because I’m not a real programmer (and I had to translate to Scheme from the Pascal in the book), it took me a couple of hours instead of a couple of minutes. But what an enjoyable couple of hours!

I started, as usual for algorithmic programming tasks, with a simulation. In the book, Sedgwick provides an example: If there are 9 people, and every 5th person in the circle is killed, the order in which they’ll die is: 5, 1, 7, 4, 3, 6, 9, 2, 8.

It’s usually easier to start work on a problem by thinking about a simpler case, so that’s what I did. I chose N = 5, and M = 2. Below I’ll show the results of my “paper” simulation (OK, the paper was actually an Emacs buffer).

First, let me show you how to read my “notation”. It should be pretty easy to figure out. Below is an example of one “state snapshot”. I’ve labelled each line with its meaning. If you are a Scheme programmer, you will surmise that each named item corresponds to a “named-let” loop variable. In addition, the vertical bar character in the `XS` row represents the state of the “cursor” as it goes around the circle of 5 people.

```;; I.                           <-- State Number
;; ------------
;; |1 2 3 4 5                   <--    XS
;; '()                          <--    YS
;; 0                            <-- COUNT
```

Above, we are in state 1, at the start of the program. The cursor is at the beginning of the list `XS`, which represents the circle of people. `YS` is our results list, where we will store the “dead”. As we travel around the circle and people are killed, they are added to `YS`. We could think of it as a “death toll”, but really it’s just a list of integers. As we go around the circle of people, we keep incrementing `COUNT`. When `COUNT` reaches the value of M, that person will be “killed”, that is, be added to `YS`.

When this happens, we reset the `COUNT` to 0 and keep going around the circle. There’s a catch, however. As more dead people are added to our result list `YS`, we need to ignore the spaces those people used to occupy in our count as we build `COUNT` back up towards M. In other words, the circle will have 4 people in it after the first person is killed. This means that as the circle gets smaller and smaller, people are killed more frequently.

I’ll show you how I’ve solved that problem in Scheme in a moment; first, the simulation:

```;; I.
;; ------------
;; |1 2 3 4 5
;; '()
;; 0

;; II.
;; ------------
;; 1| 2 3 4 5
;; '()
;; 1

;; III.
;; ------------
;; 1 2| 3 4 5
;; '()
;; 1

;; IV.
;; ------------
;; 1 _ 3| 4 5
;; '(2)
;; 1

;; V.
;; ------------
;; 1 _ 3 4| 5
;; '(2)
;; 2

;; V.
;; ------------
;; 1 _ 3 _ 5|
;; '(4 2)
;; 1

;; VI.
;; ------------
;; 1| _ 3 _ 5
;; '(4 2)
;; 2

;; VII.
;; ------------
;; _ _ 3| _ 5
;; '(1 4 2)
;; 1

;; VIII.
;; ------------
;; _ _ 3 _ 5|
;; '(1 4 2)
;; 2

;; IX.
;; ------------
;; _ _ 3| _ _
;; '(5 1 4 2)
;; 1

;; X.
;; ------------
;; _ _ _| _ _
;; '(5 1 4 2)
;; 2

;; XI.
;; ------------
;; _ _ _| _ _
;; '(3 5 1 4 2)
;; 2

```

Now that you’ve seen how the algorithm should work on paper, let’s write some Scheme! I should state for the record that I did not read the Wikipedia article linked above until after I wrote this code. (This will be pretty obvious when you look at the code.) Here it is:

```(define (josephus xs m)
(let ((orig-xs (list-copy xs))
(true-m (- m 1)))
(let ((len (length xs)))
(let loop ((xs xs)
(ys '())
(count 0))
(cond
;; If the dead list grows to the same length as our original
;; list, we know we're finished.
((= len (length ys))
(reverse ys))
;; If XS is null, we have gone once around the circle.  We
;; start around again, leaving the count unchanged.
((null? xs)
(loop orig-xs ys count))
;; (a ghost), move on.  And don't bother bumping the
;; count.
((member (car xs) ys)
(loop (cdr xs) ys count))
;; If we're here, it's also the case that the current person
;; we're looking at is *not* in the dead list.  Therefore we
;; check if the count is equal to M.  If so, they must die.
((= count true-m)
(loop (cdr xs) (cons (car xs) ys) 0))
;; If we get here, the current person we're looking at is
;; alive.  We check if the count is *not* equal to M.  If it
;; is not, we skip this person and bump the count.
((not (= count true-m))
(loop (cdr xs) ys (+ count 1)))
;; We should never get here.
(else #f))))))
```

How does it compare to the output described in Sedgwick? It seems to work!

```> (josephus '(1 2 3 4 5 6 7 8 9) 5)
'(5 1 7 4 3 6 9 2 8)
```

There are several inefficiencies we could tackle, though. The first and most obvious is that we should try to calculate the solution mathematically (as shown in some of the Wikipedia examples) instead of building up lists using `CONS`. Another is that we make a “canonical” copy of the input list for restarting the loop. A third is the use of `MEMBER` to determine whether the person we’re currently visiting is already in the “dead” list.

For example, here’s the trace output showing 19 calls to `MEMBER` for a pretty small input:

```(josephus '(1 2 3 4 5) 2)
[Enter (member 1 '())
Leave member #f]
... 17 more calls to member ...
[Enter (member 3 '(5 1 4 2))
Leave member #f]
'(2 4 1 5 3)
```

That said, in this case I was happy just to get something working. If this were going to be used for anything “real”, I would probably rewrite it statefully using vectors. Most of the fun was in coming up with this first draft without resorting to any stateful idioms.

(Image courtesy Chris Lott via CC-BY license.)