codepad

Language:

(define (range first past . step)
  (let* ((xs '()) (f first) (p past)
         (s (cond ((pair? step) (car step))
                  ((< f p) 1) (else -1)))
         (le? (if (< 0 s) <= >=)))
    (do ((x f (+ x s))) ((le? p x) (reverse xs))
      (set! xs (cons x xs)))))

(define (josephus1 n m)
  (let loop ((k m) (alive (range 0 n)) (dead '()))
    (cond ((null? (cdr alive)) (reverse (cons (car alive) dead)))
          ((= k 1) (loop m (cdr alive) (cons (car alive) dead)))
          (else (loop (- k 1) (append (cdr alive) (list (car alive))) dead)))))

(display (josephus1 41 3)) (newline)

(define (josephus2 n m)
  (let loop ((k m) (front (range 0 n)) (back '()) (dead '()))
    (cond ((and (null? front) (null? back)) (reverse dead))
          ((null? front) (loop k (reverse back) '() dead))
          ((= k 1) (loop m (cdr front) back (cons (car front) dead)))
          (else (loop (- k 1) (cdr front) (cons (car front) back) dead)))))

(display (josephus2 41 3)) (newline)

(define (last-pair xs)
  (if (null? (cdr xs))
      xs
      (last-pair (cdr xs))))

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus3 n m)
  (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))
    (cond ((= (car alive) (cadr alive))
            (reverse (cons (car alive) dead)))
          ((= k 1)
            (let ((dead (cons (cadr alive) dead)))
              (set-cdr! alive (cddr alive))
              (loop (- m 1) (cdr alive) dead)))
          (else (loop (- k 1) (cdr alive) dead)))))

(display (josephus3 41 3)) (newline)

Private [?]

Run code