Josephus problem
You are encouraged to solve this task according to the task description, using any language you may know.
Josephus problem is a math puzzle with a grim description: prisoners are standing on a circle, sequentially numbered from to . An executioner walks along the circle, starting from prisoner , removing every -th prisoner and killing him. As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. For example, if there are prisoners and , the order the prisoners are killed in (let's call it the "killing sequence") will be 1, 3, 0, and 4, and the survivor will be #2.
Task Given any , find out which prisoner will be the final survivor. In one such incident, there were 41 prisoners and every 3rd prisoner was being killed (). Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?
Extra The captors may be especially kind and let survivors free, and Josephus might just have friends to save. Provide a way to calculate which prisoner is at any given position on the killing sequence.
Notes
- You can always play the executioner and follow the procedure exactly as described, walking around the circle, counting (and cutting off) heads along the way. This would yield the complete killing sequence and answer the above questions, with a complexity of probably . However, individually it takes no more than to find out which prisoner is the -th to die.
- If it's more convenient, you can number prisoners from to instead. If you choose to do so, please state it clearly.
- An alternative description has the people committing assisted suicide instead of being executed, and the last person simply walks away. These details are not relevant, at least not mathematically.
Ada
The procedure reads up to 4 parameters from the command line: the number N of prisoners, the step size K, the number M of survivors, and an indicator whether the executions shall be printed ("1") or only surviving prisoners (any other input). The defaults are 41, 3, 1, 1. The prison cells are numbered from 0 to N-1. <lang Ada>with Ada.Command_Line, Ada.Text_IO;
procedure Josephus is
function Arg(Idx, Default: Positive) return Positive is -- read Argument(Idx) (if Ada.Command_Line.Argument_Count >= Index then Positive'Value(Ada.Command_Line.Argument(Index)) else Default);
Prisoners: constant Positive := Arg(Idx => 1, Default => 41); Steps: constant Positive := Arg(Idx => 2, Default => 3); Survivors: constant Positive := Arg(Idx => 3, Default => 1); Print: Boolean := (Arg(Idx => 4, Default => 1) = 1);
subtype Index_Type is Natural range 0 .. Prisoners-1; Next: array(Index_Type) of Index_Type; X: Index_Type := (Steps-2) mod Prisoners;
begin
Ada.Text_IO.Put_Line ("N =" & Positive'Image(Prisoners) & ", K =" & Positive'Image(Steps) & (if Survivors > 1 then ", #survivors =" & Positive'Image(Survivors) else "")); for Idx in Next'Range loop -- initialize Next Next(Idx) := (Idx+1) mod Prisoners; end loop; if Print then Ada.Text_IO.Put("Executed: "); end if; for Execution in reverse 1 .. Prisoners loop if Execution = Survivors then Ada.Text_IO.New_Line; Ada.Text_IO.Put("Surviving: "); Print := True; end if; if Print then Ada.Text_IO.Put(Positive'Image(Next(X))); end if; Next(X) := Next(Next(X)); -- "delete" a prisoner for Prisoner in 1 .. Steps-1 loop X := Next(X); end loop; end loop;
end Josephus;</lang>
- Output:
$ ./josephus N = 41, K = 3 Executed: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Surviving: 30 $ ./josephus 23482 3343 3 0 N = 23482, K = 3343, #survivors = 3 Surviving: 13317 1087 1335
AutoHotkey
<lang AHK>; Since AutoHotkey is 1-based, we're numbering prisoners 1-41. nPrisoners := 41 kth := 3
- Build a list, purposefully ending with a separator
Loop % nPrisoners list .= A_Index . "|"
- iterate and remove from list
i := 1 Loop { ; Step by 2; the third step was done by removing the previous prisoner i += kth - 1 if (i > nPrisoners) i := Mod(i, nPrisoners) ; Remove from list end := InStr(list, "|", 0, 1, i) bgn := InStr(list, "|", 0, 1, i-1) list := SubStr(list, 1, bgn) . SubStr(list, end+1) nPrisoners-- } Until (nPrisoners = 1) MsgBox % RegExReplace(list, "\|") ; remove the final separator</lang>
- Output:
31
Note that since this is one-based, the answer is correct, though it differs with many other examples.
Using Objects
<lang AHK>nPrisoners := 41 kth := 3 list := []
- Build a list of 41 items
Loop % nPrisoners list.insert(A_Index)
- iterate and remove from list
i := 1 Loop { ; Step by 3 i += kth - 1 if (i > list.MaxIndex()) i := Mod(i, list.MaxIndex()) list.remove(i) } Until (list.MaxIndex() = 1) MsgBox % list.1 ; there is only 1 element left</lang>
C
<lang c>#include <stdio.h>
// m-th on the reversed kill list; m = 0 is final survivor int jos(int n, int k, int m) { int a; for (a = m + 1; a <= n; a++) m = (m + k) % a; return m; }
typedef unsigned long long xint;
// same as jos(), useful if n is large and k is not xint jos_large(xint n, xint k, xint m) { if (k <= 1) return n - m - 1;
xint a = m; while (a < n) { xint q = (a - m + k - 2) / (k - 1);
if (a + q > n) q = n - a; else if (!q) q = 1;
m = (m + q * k) % (a += q); }
return m; }
int main(void) { xint n, k, i;
n = 41; k = 3; printf("n = %llu, k = %llu, final survivor: %d\n", n, k, jos(n, k, 0));
n = 9876543210987654321ULL; k = 12031; printf("n = %llu, k = %llu, three survivors:", n, k);
for (i = 3; i--; ) printf(" %llu", jos_large(n, k, i)); putchar('\n');
return 0; }</lang>
- Output:
n = 41, k = 3, final survivor: 30 n = 9876543210987654321, k = 12031, three survivors: 6892710366467541051 1946357796579138992 3554846299321782413
C++
<lang cpp>
- include <iostream>
- include <vector>
//-------------------------------------------------------------------------------------------------- using namespace std; typedef unsigned long long bigint;
//-------------------------------------------------------------------------------------------------- class josephus { public:
bigint findSurvivors( bigint n, bigint k, bigint s = 0 ) {
bigint i = s + 1; for( bigint x = i; x <= n; x++, i++ ) s = ( s + k ) % i;
return s;
}
void getExecutionList( bigint n, bigint k, bigint s = 1 ) {
cout << endl << endl << "Execution list: " << endl;
prisoners.clear(); for( bigint x = 0; x < n; x++ ) prisoners.push_back( x );
bigint index = 0; while( prisoners.size() > s ) { index += k - 1; if( index >= prisoners.size() ) index %= prisoners.size(); cout << prisoners[static_cast<unsigned int>( index )] << ", ";
vector<bigint>::iterator it = prisoners.begin() + static_cast<unsigned int>( index ); prisoners.erase( it ); }
}
private:
vector<bigint> prisoners;
}; //-------------------------------------------------------------------------------------------------- int main( int argc, char* argv[] ) {
josephus jo; bigint n, k, s; while( true ) {
system( "cls" ); cout << "Number of prisoners( 0 to QUIT ): "; cin >> n; if( !n ) return 0; cout << "Execution step: "; cin >> k; cout << "How many survivors: "; cin >> s;
cout << endl << "Survivor"; if( s == 1 ) { cout << ": " << jo.findSurvivors( n, k ); jo.getExecutionList( n, k ); } else { cout << "s: "; for( bigint x = 0; x < s; x++ ) cout << jo.findSurvivors( n, k, x ) << ", ";
jo.getExecutionList( n, k, s ); }
cout << endl << endl; system( "pause" );
} return 0;
} //-------------------------------------------------------------------------------------------------- </lang> Output:
Number of prisoners( 0 to QUIT ): 41 Execution step: 3 How many survivors: 1 Survivor: 30 Execution list: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36 , 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15, Number of prisoners( 0 to QUIT ): 41 Execution step: 3 How many survivors: 3 Survivors: 30, 15, 34, Execution list: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36 , 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, Number of prisoners( 0 to QUIT ): 71 Execution step: 47 How many survivors: 11 Survivors: 29, 58, 41, 14, 39, 28, 35, 45, 64, 49, 27, Execution list: 46, 22, 70, 48, 26, 5, 56, 36, 17, 0, 54, 38, 23, 9, 66, 55, 43, 33, 25, 16, 11, 6, 2, 69, 68, 1, 4, 10, 15, 24, 32, 42, 53, 65, 20, 40, 60, 19, 47, 8, 44, 13, 52, 31, 12, 62, 57, 50, 51, 61, 7, 30, 59, 34, 18, 3, 21, 37, 67, 63,
Common Lisp
Using a loop: <lang lisp>(defun kill (n k &aux (m 0))
(loop for a from (1+ m) upto n do (setf m (mod (+ m k) a))) m)</lang>
Using a circular list. <lang lisp>(defun make-circular-list (n)
(let* ((list (loop for i below n collect i)) (last (last list))) (setf (cdr last) list) list))
(defun kill (n d)
(let ((list (make-circular-list n))) (flet ((one-element-clist-p (list) (eq list (cdr list))) (move-forward () (loop repeat (1- d) until (eq list (cdr list)) do (setf list (cdr list)))) (kill-item () (setf (car list) (cadr list) (cdr list) (cddr list)))) (loop until (one-element-clist-p list) do (move-forward) (kill-item)) (first list))))</lang>
- Example:
CL-USER > (kill 41 3) 30
D
<lang d>import std.stdio, std.algorithm, std.array, std.string, std.range;
T pop(T)(ref T[] items, in size_t i) pure {
auto aux = items[i]; items.remove(i); items.length--; return aux;
}
string josephus(in int n, in int k) {
auto p = iota(n).array(); int i; int[] seq; while (!p.empty) { i = (i + k - 1) % p.length; seq ~= p.pop(i); }
return xformat("Prisoner killing order: %(%d, %).\nSurvivor: %d", seq[0 .. $-1], seq[$ - 1]);
}
void main() {
writeln(josephus(5, 2)); writeln(); writeln(josephus(41, 3));
}</lang>
- Output:
(Some newlines added)
Prisoner killing order: 1, 3, 0, 4. Survivor: 2 Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15. Survivor: 30
Factor
<lang factor>USING: kernel locals math math.ranges sequences ; IN: josephus
- josephus ( k n -- m )
n [1,b] 0 [ [ k + ] dip mod ] reduce ;</lang>
IN: scratchpad 3 41 josephus . 30
Fortran
Naive approach: prisonners are put in a "linked buffer" (implemented as an array giving number of "next living prisonner"). Then we iterate, killing one after each loop, until there is only one left. <lang fortran>program josephus
implicit none integer :: n, i, k, p integer, allocatable :: next(:) read *, n, k allocate(next(0:n - 1)) do i = 0, n - 2 next(i) = i + 1 end do next(n - 1) = 0 p = 0 do while(next(p) /= p) do i = 1, k - 2 p = next(p) end do print *, "Kill", next(p) next(p) = next(next(p)) p = next(p) end do print *, "Alive", p deallocate(next)
end program</lang>
friendly interactive shell
<lang fishshell>function execute
# If the list is empty, don't do anything. test (count $argv) -ge 2; or return # If the list has only one element, return it if test (count $argv) -eq 2 echo $argv[2] return end # Rotate prisoners for i in (seq 2 $argv[1]) set argv $argv[1 3..-1 2] end # Mention killed prisoner echo $argv[2] # Kill rest recursively execute $argv[1 3..-1]
end
echo Prisoner (execute 3 (seq 0 40))[-1] survived.</lang>
- Output:
Prisoner 30 survived.
It's also possible to calculate more than one survivor. <lang fishshell>echo Prisoners (execute 3 (seq 0 40))[-3..-1] survived.</lang>
- Output:
Prisoners 34 15 30 survived.
Prisoners don't have to be numbers. <lang fishshell>echo Prisoner (execute 2 Joe Jack William Averell Rantanplan)[-1] survived.</lang>
- Output:
Prisoner William survived.
Go
<lang go>package main
import "fmt"
// basic task function func finalSurvivor(n, k int) int {
// argument validation omitted circle := make([]int, n) for i := range circle { circle[i] = i } k-- exPos := 0 for len(circle) > 1 { exPos = (exPos + k) % len(circle) circle = append(circle[:exPos], circle[exPos+1:]...) } return circle[0]
}
// extra func position(n, k, pos int) int {
// argument validation omitted circle := make([]int, n) for i := range circle { circle[i] = i } k-- exPos := 0 for len(circle) > 1 { exPos = (exPos + k) % len(circle) if pos == 0 { return circle[exPos] } pos-- circle = append(circle[:exPos], circle[exPos+1:]...) } return circle[0]
}
func main() {
// show basic task function on given test case fmt.Println(finalSurvivor(41, 3)) // show extra function on all positions of given test case fmt.Println("Position Prisoner") for i := 0; i < 41; i++ { fmt.Printf("%5d%10d\n", i, position(41, 3, i)) }
}</lang>
- Output:
30 Position Prisoner 0 2 1 5 2 8 3 11 4 14 5 17 6 20 7 23 8 26 9 29 10 32 11 35 12 38 13 0 14 4 15 9 16 13 17 18 18 22 19 27 20 31 21 36 22 40 23 6 24 12 25 19 26 25 27 33 28 39 29 7 30 16 31 28 32 37 33 10 34 24 35 1 36 21 37 3 38 34 39 15 40 30
Haskell
Shows only the surviving prisoners. Change "print $ snd" to just "print" to show the killed prisoners, too. The arguments to the "main" function are: n = number of prisoners, k = kill every kth prisoner, m = show at most m survivors <lang Haskell>import Data.List ((\\)) import System.Environment (getArgs)
prisoners :: Int -> [Int] prisoners n = [0 .. n - 1]
counter :: Int -> [Int] counter k = cycle [k, k-1 .. 1]
killList :: [Int] -> [Int] -> ([Int], [Int], [Int]) killList xs cs = (killed, survivors, newCs)
where (killed, newCs) = kill xs cs [] survivors = xs \\ killed kill [] cs rs = (rs, cs) kill (x:xs) (c:cs) rs | c == 1 = let ts = rs ++ [x] in kill xs cs ts | otherwise = kill xs cs rs
killRecursive :: [Int] -> [Int] -> Int -> ([Int], [Int]) killRecursive xs cs m = killR ([], xs, cs)
where killR (killed, remaining, counter) | length remaining <= m = (killed, remaining) | otherwise = let (newKilled, newRemaining, newCounter) = killList remaining counter allKilled = killed ++ newKilled in killR (allKilled, newRemaining, newCounter)
main :: IO () main = do
args <- getArgs case args of [n, k, m] -> print $ snd $ killRecursive (prisoners (read n)) (counter (read k)) (read m) _ -> print $ snd $ killRecursive (prisoners 41) (counter 3) 1
</lang>
Using modulo and list split, indices are 1-based. This is much faster than cycled list for larger numbers: <lang Haskell>jseq n k = f n [1 .. n] where
f 0 _ = [] f m s = x:f (m-1) (right ++ left) where (left,x:right) = splitAt ((k-1) `mod` m) s
-- the final survivor is ((k + ...((k + ((k + 0)`mod` 1)) `mod` 2) ... ) `mod` n) jos n k = 1 + foldl (\x->((k+x)`mod`)) 0 [2..n]
main = do
print $ jseq 41 3 print $ jos 10000 100</lang>
J
Using the executioner's algorithm.
Tacit version
<lang J> 3 ([ (1 }. <:@[ |. ])^:(1 < #@])^:_ i.@]) 41 30</lang> Structured derivation of the fixed tacit code <lang J> DropNext=. 1 }. <:@[ |. ]
MoreThanOne=. 1 < #@] WhileMoreThanOne=. (^:MoreThanOne f.) (^:_) prisoners=. i.@] [ DropNext WhileMoreThanOne prisoners f.
[ (1 }. <:@[ |. ])^:(1 < #@])^:_ i.@]</lang>
Explicit version
<lang J>Josephus =: dyad define NB. explicit form, assume executioner starts at position 0
NB. use: SKIP josephus NUMBER_OF_PRISONERS N =: y K =: N | x EXECUTIONER =: 0 PRISONERS =: i. N kill =: ] #~ (~: ([: i. #)) while. 1 (< #) PRISONERS do. EXECUTIONER =: (# PRISONERS) | <: K + EXECUTIONER PRISONERS =: EXECUTIONER kill PRISONERS end.
)
3 Josephus 41
30</lang>
Explicit version 2
<lang J> Josephus2 =: 4 : '(|x&+)/i.->:y' NB. this is a direct translation of the algo from C code above.
3 Josephus2 41 30
</lang>
Java
<lang java5>import java.util.ArrayList;
public class Josephus {
public static int execute(int n, int k){ int killIdx = 0; ArrayList<Integer> prisoners = new ArrayList<Integer>(n); for(int i = 0;i < n;i++){ prisoners.add(i); } System.out.println("Prisoners executed in order:"); while(prisoners.size() > 1){ killIdx = (killIdx + k - 1) % prisoners.size(); System.out.print(prisoners.get(killIdx) + " "); prisoners.remove(killIdx); } System.out.println(); return prisoners.get(0); } public static ArrayList<Integer> executeAllButM(int n, int k, int m){ int killIdx = 0; ArrayList<Integer> prisoners = new ArrayList<Integer>(n); for(int i = 0;i < n;i++){ prisoners.add(i); } System.out.println("Prisoners executed in order:"); while(prisoners.size() > m){ killIdx = (killIdx + k - 1) % prisoners.size(); System.out.print(prisoners.get(killIdx) + " "); prisoners.remove(killIdx); } System.out.println(); return prisoners; } public static void main(String[] args){ System.out.println("Survivor: " + execute(41, 3)); System.out.println("Survivors: " + executeAllButM(41, 3, 3)); }
}</lang>
- Output:
Prisoners executed in order: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Survivor: 30 Prisoners executed in order: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 Survivors: [15, 30, 34]
Mathematica
<lang mathematica>survivor[n_, k_] := Nest[Most[RotateLeft[#, k]] &, Range[0, n - 1], n - 1] survivor[41, 3]</lang>
- Output:
{30}
NetRexx
Hardly any changes at all... <lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
/* REXX **************************************************************
- 15.11.2012 Walter Pachl - my own solution
- 16.11.2012 Walter Pachl generalized n prisoners + w killing distance
- and s=number of survivors
- /
dead = 0 /* nobody's dead yet */ n = 41 /* number of alive prisoners */ nn = n /* wrap around boundary */ w = 3 /* killing count */ s = 1 /* nuber of survivors */ p = -1 /* start here */ killed = /* output of killings */ Loop until n = s /* until one alive prisoner */
found = 0 /* start looking */ Loop Until found = w /* until we have the third */ p = p + 1 /* next position */ If p = nn Then p = 0 /* wrap around */ If dead[p] = 0 Then /* a prisoner who is alive */ found = found + 1 /* increment found count */ End dead[p] = 1 n = n - 1 /* shoot the one on this pos. */ killed = killed p /* add to output */ End /* End of main loop */
Say 'killed:'killed.subword(1, 20) /* output killing sequence */ Say ' 'killed.subword(21) /* output killing sequence */ Say 'Survivor(s):' /* show */ Loop i = 0 To 40 /* look for the surviving p's */
If dead[i] = 0 Then Say i /* found one */ End</lang>
- Output:
killed:2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Survivor(s): 30
PARI/GP
<lang parigp>Josephus(n, k)=if(n<2, n>0, my(t=(Josephus(n-1, k)+k)%n); if(t, t, n))</lang>
Perl
<lang Perl>my @prisoner = 0 .. 40; my $k = 3; until (@prisoner == 1) {
push @prisoner, shift @prisoner for 1 .. $k-1; shift @prisoner;
}
print "Prisoner @prisoner survived.\n"</lang>
- Output:
Prisoner 30 survived.
Perl 6
Straightforward implementation of the executioner's algorithm: <lang Perl6>sub Execute(@prisoner is rw, $k) {
until @prisoner == 1 {
@prisoner.=rotate($k - 1); @prisoner.shift;
}
}
my @prisoner = ^41; Execute @prisoner, 3; say "Prisoner {@prisoner} survived.";</lang>
- Output:
Prisoner 30 survived.
We don't have to use numbers. Any list will do: <lang Perl6>my @dalton = <Joe Jack William Averell Rantanplan>; Execute @dalton, 2; say "{@dalton} survived.";</lang>
- Output:
William survived.
Python
<lang python>>>> def j(n, k): p, i, seq = list(range(n)), 0, [] while p: i = (i+k-1) % len(p) seq.append(p.pop(i)) return 'Prisoner killing order: %s.\nSurvivor: %i' % (', '.join(str(i) for i in seq[:-1]), seq[-1])
>>> print(j(5, 2)) Prisoner killing order: 1, 3, 0, 4. Survivor: 2 >>> print(j(41, 3)) Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15. Survivor: 30 >>> </lang>
Racket
<lang Racket>#lang racket (define (josephus n k (m 0))
(for/fold ((m (add1 m))) ((a (in-range (add1 m) (add1 n)))) (remainder (+ m k) a)))
(josephus 41 3) ; ->30</lang>
REXX
version 1
<lang rexx>/* REXX **************************************************************
- 15.11.2012 Walter Pachl - my own solution
- 16.11.2012 Walter Pachl generalized n prisoners + w killing distance
- and s=number of survivors
- /
dead.=0 /* nobody's dead yet */ n=41 /* number of alive prisoners */ nn=n /* wrap around boundary */ w=3 /* killing count */ s=1 /* nuber of survivors */ p=-1 /* start here */ killed= /* output of killings */ Do until n=s /* until one alive prisoner */
found=0 /* start looking */ Do Until found=w /* until we have the third */ p=p+1 /* next position */ If p=nn Then p=0 /* wrap around */ If dead.p=0 Then /* a prisoner who is alive */ found=found+1 /* increment found count */ End dead.p=1 n=n-1 /* shoot the one on this pos. */ killed=killed p /* add to output */ End /* End of main loop */
Say 'killed:'subword(killed,1,20) /* output killing sequence */ Say ' 'subword(killed,21) /* output killing sequence */ Say 'Survivor(s):' /* show */ Do i=0 To 40 /* look for the surviving p's */
If dead.i=0 Then Say i /* found one */ End</lang>
- Output:
killed:2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Survivor(s): 30
version 2
This version allows the user to specify:
- number of prisoners
- the count-off [every Kth prisoner]
- the start count [zero or one]
- the number of survivors
- the solving of the extra credit task requirement of multiple survivors
The output echoes the choices specified and was made "English" readable. This solution is an executor's solution. <lang rexx>/*REXX pgm, Josephus problem: N men standing in a circle, every Kth kilt*/ parse arg N K Z R . /*get optional arguments. */ if N==',' | N== then N = 41 /*no #prisoners? Then use default*/ if K==',' | K== then K = 3 /*no kill count? " " " */ if Z==',' | Z== then Z = 0 /*no initial # ? " " " */ if R==',' | R== then R = 1 /*no remaining#? " " " */ $=; x=; do pop=Z for N; $=$ pop; end /*populate the prisoner's circle.*/ c=0 /*initial prisoner count-off num.*/
do remove=0; p=words($) /*keep removing until R are left.*/ c=c+K /*bump prisoner count-off by K.*/ if c>p then do /* [↓] remove some prisoner(s).*/ do j=1 for words(x); $=delword($,word(x,j)+1-j,1) if words($)==R then leave remove /*slaying done yet?*/ end /*j*/ c=(c//p)//words($); x= /*adjust prisoner count-off &list*/ end if c\==0 then x=x c /*list of prisoners to be removed*/ end /*remove*/ /*remove 'til R prisoners left.*/
say 'removing every ' th(K) " prisoner out of " N ' (starting at' Z") with ",
R ' survivor's(R)"," ; say 'leaving prisoner's(R)':' $
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────subroutines──────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) 's',1) th: arg y; return y||word('th st nd rd', 1+y//10*(y//100%10\==1)*(y//10<4))</lang> output when using the default input
removing every 3rd prisoner out of 41 (starting at 0) with 1 survivor, leaving prisoner: 30
output when using the input of: 41 3 1
removing every 3rd prisoner out of 41 (starting at 1) with 1 survivor, leaving prisoner: 31
output when using the input of: 41 3 1 2
removing every 3rd prisoner out of 41 (starting at 1) with 2 survivors, leaving prisoners: 16 31
output when using the input of: 5 2
removing every 2nd prisoner out of 5 (starting at 0) with 1 survivor, leaving prisoner: 2
Ruby
<lang ruby>def main
n = (ARGV[0] || 41).to_i k = (ARGV[1] || 3).to_i puts josephus(n,k)
end
def josephus(n, k)
prisoners = (0...n).to_a prisoners.rotate!(k-1).shift while prisoners.length > 1 return prisoners.first
end
main</lang>
Scala
Executioner's Solution, not Josephus'
(Prisoners labeled 0 to n-1) <lang scala>def executed( prisonerCount:Int, step:Int ) = {
val prisoners = ((0 until prisonerCount) map (_.toString)).toList
def behead( dead:Seq[String], alive:Seq[String] )(countOff:Int) : (Seq[String], Seq[String]) = { val group = if( alive.size < countOff ) countOff - alive.size else countOff
(dead ++ alive.take(group).drop(group-1), alive.drop(group) ++ alive.take(group-1)) }
def beheadN( dead:Seq[String], alive:Seq[String] ) : (Seq[String], Seq[String]) = behead(dead,alive)(step)
def execute( t:(Seq[String], Seq[String]) ) : (Seq[String], Seq[String]) = t._2 match { case x :: Nil => (t._1, Seq(x)) case x :: xs => execute(beheadN(t._1,t._2)) }
execute((List(),prisoners))
}
val (dead,alive) = executed(41,3)
println( "Prisoners executed in order:" ) print( dead.mkString(" ") )
println( "\n\nJosephus is prisoner " + alive(0) )</lang>
- Output:
Prisoners executed in order: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Josephus is prisoner 30
Seed7
The main task (find one survivor) is a special case of the extra task (find m survivors). The function executeAllButM solves the extra task and is called with m=1 to solve the main task. The function str converts an array of integer elements to a string. The function enable_output uses str to define everything necessary to write an array of integers. This way the main program can write the survivor array. <lang seed7>$ include "seed7_05.s7i";
const func array integer: executeAllButM (in integer: n, in integer: k, in integer: m) is func
result var array integer: prisoners is [0 .. -1] times 0; local var integer: killIdx is 0; var integer: prisonerNum is 0; begin for prisonerNum range 0 to pred(n) do prisoners &:= prisonerNum; end for; writeln("Prisoners executed in order:"); while length(prisoners) > m do killIdx := (killIdx + k - 1) rem length(prisoners); write(prisoners[killIdx] <& " "); ignore(remove(prisoners, killIdx)); end while; writeln; end func;
const func string: str (in array integer: intArr) is func
result var string: stri is ""; local var integer: index is 0; begin for key index range intArr do if index <> minIdx(intArr) then stri &:= ", "; end if; stri &:= str(intArr[index]); end for; end func;
enable_output(array integer);
const proc: main is func
begin writeln("Survivor: " <& executeAllButM(41, 3, 1)); writeln("Survivors: " <& executeAllButM(41, 3, 3)); end func;</lang>
- Output:
Prisoners executed in order: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 Survivor: 30 Prisoners executed in order: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 Survivors: 15, 30, 34
Tcl
<lang tcl>proc josephus {number step {survivors 1}} {
for {set i 0} {$i<$number} {incr i} {lappend l $i} for {set i 1} {[llength $l]} {incr i} {
# If the element is to be killed, append to the kill sequence if {$i%$step == 0} { lappend killseq [lindex $l 0] set l [lrange $l 1 end] } else { # Roll the list set l [concat [lrange $l 1 end] [list [lindex $l 0]]] }
} return [lrange $killseq end-[expr {$survivors-1}] end]
}</lang> Demonstrating: <lang tcl>puts "remaining: [josephus 41 3]" puts "remaining 4: [join [josephus 41 3 4] ,]"</lang>
- Output:
remaining: 30 remaining 4: 3,34,15,30
Vedit macro language
This macro first creates a list of prisoners in an edit buffer.
Then the prisoners are deleted in loop until specified number of survivors are left.
When the macro finishes, you can see the list of survivors in the edit buffer.
<lang vedit>#1 = 41 // number of prisoners
- 2 = 3 // step size
- 3 = 1 // number of survivors
Buf_Switch(Buf_Free) for (#5=0; #5<#1; #5++) {
Ins_Text("prisoner ") Num_Ins(#5, LEFT)
}
BOF
- 4=1
while (#1 > #3) {
if (#4++ % #2 == 0) {
Del_Line(1)
#1-- } else {
Line(1)
} if (At_EOF) { BOF }
}</lang>
Output:
prisoner 30
Output when the number of survivors is set to 3:
prisoner 15 prisoner 30 prisoner 34
XPL0
<lang XPL0>include c:\cxpl\codes;
func Prisoner(N, K); \Return final surviving prisoner int N, K; \number of prisoners, number to skip int I, J; char A; [A:= Reserve(N); for I:= 0 to N-1 do A(I):= I; I:= 0; repeat I:= I+K-1; \skip to next prisoner
I:= rem(I/N); \wrap to start if necessary IntOut(0, A(I)); ChOut(0, ^ ); \show killed prisoner for J:= I to N-2 do A(J):= A(J+1); \shift survivors down N:= N-1; \one less prisoner
until N=1; return A(0); ];
[IntOut(0, Prisoner(5, 2)); CrLf(0);
IntOut(0, Prisoner(41, 3)); CrLf(0);
]</lang>
- Output:
1 3 0 4 2 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30