Josephus problem: Difference between revisions
Keithpinson (talk | contribs) Prisoners now labeled 0 to n-1 |
→{{header|REXX}}: added a 2nd version. -- ~~~~ |
||
Line 358: | Line 358: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
|||
<lang rexx>/* REXX ************************************************************** |
<lang rexx>/* REXX ************************************************************** |
||
* 15.11.2012 Walter Pachl - my own solution |
* 15.11.2012 Walter Pachl - my own solution |
||
Line 394: | Line 395: | ||
Survivor(s): |
Survivor(s): |
||
30 |
30 |
||
</pre> |
|||
===version 2=== |
|||
This version allows the user to specify: |
|||
* number of prisoners |
|||
* the count-off [every K<sup>th</sup> prisoner] |
|||
* the start count [zero or one] |
|||
* the number of survivors |
|||
=={{header|REXX}}== |
|||
<lang rexx>/*REXX program solves Josephus' problem: N prisoners which are standing*/ |
|||
/*──────────── in a circle, every K-th prisoner is killed (or removed).*/ |
|||
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.*/ |
|||
i=0 /*the initial prisoner count-off.*/ |
|||
do until words($)==r; w=words($) /*keep removing until R are left.*/ |
|||
w=words($) /*handy counter to have around. */ |
|||
i=i+k /*bump prisoner count-off by K*/ |
|||
if i>w then do /* [↓] remove some prisoner(s).*/ |
|||
do j=1 for words(x); $=delword($,word(x,j),1); end |
|||
i=(i//w)//words($); x= /*adjust prisoner count-off &list*/ |
|||
end |
|||
if x\==0 then x=i x /*list of prisoners to be removed*/ |
|||
end /*until*/ /*keep going 'til 1 prisoner 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:parse 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 |
|||
<pre style="overflow:scroll"> |
|||
removing every 3rd prisoner out of 41 (starting at 0) with 1 survivor, |
|||
leaving prisoner: 30 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> 41 3 1 </tt> |
|||
<pre style="overflow:scroll"> |
|||
removing every 3rd prisoner out of 41 (starting at 1) with 1 survivor, |
|||
leaving prisoner: 31 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> 41 3 1 2 </tt> |
|||
<pre style="overflow:scroll"> |
|||
removing every 3rd prisoner out of 41 (starting at 1) with 2 survivors, |
|||
leaving prisoners: 16 31 |
|||
</pre> |
|||
'''output''' when using the input of: <tt> 5 2 </tt> |
|||
<pre style="overflow:scroll"> |
|||
removing every 2nd prisoner out of 5 (starting at 0) with 1 survivor, |
|||
leaving prisoner: 2 |
|||
</pre> |
</pre> |
||
Revision as of 19:35, 6 January 2013
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.
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
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
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
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
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>
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
REXX
<lang rexx>/*REXX program solves Josephus' problem: N prisoners which are standing*/ /*──────────── in a circle, every K-th prisoner is killed (or removed).*/ 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.*/ i=0 /*the initial prisoner count-off.*/
do until words($)==r; w=words($) /*keep removing until R are left.*/ w=words($) /*handy counter to have around. */ i=i+k /*bump prisoner count-off by K*/ if i>w then do /* [↓] remove some prisoner(s).*/ do j=1 for words(x); $=delword($,word(x,j),1); end i=(i//w)//words($); x= /*adjust prisoner count-off &list*/ end if x\==0 then x=i x /*list of prisoners to be removed*/ end /*until*/ /*keep going 'til 1 prisoner 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:parse 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
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