The Josephus Problem

What is the Josephus problem? To quote from Concepts, Techniques, and Models of Computer Programming (a daunting title if ever there was one):

Flavius Josephus was a roman historian of Jewish origin. During the Jewish-Roman wars of the first century AD, he was in a cave with fellow soldiers, 40 men in all, surrounded by enemy Roman troops. They decided to commit suicide by standing in a ring and counting off each third man. Each man so designated was to commit suicide...Josephus, not wanting to die, managed to place himself in the position of the last survivor.

In the general version of the problem, there are n soldiers numbered from 1 to n and each k-th soldier will be eliminated. The count starts from the first soldier. What is the number of the last survivor?


I decided to model this situation using objects in three different scripting languages, Perl, Ruby, and Python. The solution in each of the languages is similar. A Person class is defined, which knows whether it is alive or dead, who the next person in the circle is, and what position number it is in. There are methods to pass along a kill signal, and to create a chain of people. Either of these could have been implemented using iteration, but I wanted to give recursion a whirl, since it's tougher on the languages. Here are my results.

(define mass-grave '())
(define (kike n c) (list n #t c))
(define (kill kike) (set-car! (cdr kike) #f) kike)
(define (bury kike) (set! mass-grave (cons kike mass-grave)))

(define (range i n) (if (= i n) (cons n '()) (cons i (range (+ i 1) n))))
(define (last-pair L) (if (null? (cdr L)) L (last-pair (cdr L))))

(define (kike-ring n c)
  (let ((ring (map (lambda (n) (kike n c)) (range 1 n))))
    (set-cdr! (last-pair ring) ring)
    ring))

(define shoah-counter 0)
(define (shoah n k)
  (set! shoah-counter (+ shoah-counter 1))
 
  (define (shoah-helper ring k)
    (cond ((eq? (car ring) (cadr ring)) (car ring))
          (else (shoah-helper (kill-kth ring k) k))))
  (define (kill-kth ring k)
    (if (= k 1)
        (begin (bury (kill (cadr ring))) (set-cdr! ring (cddr ring)) ring)
        (kill-kth (cdr ring) (- k 1))))
  (shoah-helper (kike-ring n shoah-counter) k))