Josephus problem: Difference between revisions
m
→{{header|Fōrmulæ}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
| (44 intermediate revisions by 18 users not shown) | |||
Line 36:
{{trans|Python}}
<
V p = Array(0 .< n)
V i = 0
Line 46:
print(j(5, 2))
print(j(41, 3))</
{{out}}
Line 59:
{{trans|REXX}}
The program uses two ASSIST macros (XDECO,XPRNT) to keep the code as short as possible.
<
JOSEPH CSECT
USING JOSEPH,R13 base register
Line 140:
DEAD DS 256X n max
YREGS
END JOSEPH</
{{out}}
<pre>
Line 151:
=={{header|6502 Assembly}}==
This subroutine expects to be called with the value of <i>n</i> in the accumulator and the value of <i>k</i> in index register <tt>X</tt>. It returns with the index of the survivor in the accumulator, and also leaves an array beginning at address 1000 hex giving the order in which the prisoners died. For example, in the case where <i>n</i> = 5 and <i>k</i> = 2, the values stored in the array are 2, 0, 4, 1, 3. From this we see that prisoner 1 was the first to die, then prisoner 3, and so on. (Note that prisoner 2 in this instance is the survivor.)
<
STX $D1 ; k
LDA #$FF
Line 184:
JMP FIND
RETURN: TXA ; a <- index of survivor
RTS</
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program josephus64.s */
Line 378:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{Output}}
<pre>
Line 392:
=={{header|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.
<
procedure Josephus is
Line 434:
end loop;
end loop;
end Josephus;</
{{out}}
<pre>$ ./josephus
Line 448:
=={{header|ALGOL 68}}==
Translated from the C
<
PROC josephus = (INT n, k, m) INT :
CO Return m-th on the reversed kill list; m=0 is final survivor. CO
Line 459:
printf (($"n = ", g(0), ", k = ", g(0), ", final survivor: ", g(0)l$,
n, k, josephus (n, k, 0)))
END</
{{out}}
<pre>n = 41, k = 3, final survivor: 30</pre>
=={{header|AppleScript}}==
Line 487 ⟶ 471:
{{trans|BBC BASIC}}
<
set m to 0
repeat with i from 2 to n
Line 496 ⟶ 480:
end josephus
josephus(41, 3) --> 31</
Or with an option to specify the number of survivors:
<
script o
property living : {}
Line 531 ⟶ 515:
josephus(41, 3, 1) --> {31}
josephus(41, 3, 6) --> {2, 4, 16, 22, 31, 35}</
===Composition of pure functions===
Composing a solution from generic and reusable (pure) functions, and using the zero-based notation of the problem statement:
<
on josephusSurvivor(n, k)
script go
Line 677 ⟶ 661:
set my text item delimiters to dlm
str
end unlines</
{{Out}}
<pre>Josephus survivor -> 30
Line 685 ⟶ 669:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* ARM assembly Raspberry PI */
Line 884 ⟶ 868:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
pi@raspberrypi:~/asm32/rosetta32/ass6 $ josephus 41 3
Line 894 ⟶ 878:
=={{header|Arturo}}==
<
p: new 0..n-1
i: 0
Line 913 ⟶ 897:
print "josephus 41 3 =>"
josephus 41 3</
{{out}}
Line 922 ⟶ 906:
josephus 41 3 =>
Prisoner killing order: [
Survivor: 30</pre>
=={{header|AutoHotkey}}==
<
nPrisoners := 41
kth := 3
Line 949 ⟶ 933:
}
Until (nPrisoners = 1)
MsgBox % RegExReplace(list, "\|") ; remove the final separator</
{{out}}
<pre>31</pre>
Note that since this is one-based, the answer is correct, though it differs with many other examples.
===Using Objects===
<
kth := 3
list := []
Line 973 ⟶ 957:
}
Until (list.MaxIndex() = 1)
MsgBox % list.1 ; there is only 1 element left</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f JOSEPHUS_PROBLEM.AWK
# converted from PL/I
Line 1,014 ⟶ 998:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,032 ⟶ 1,016:
=={{header|BASIC}}==
Unstructured implementation: see solutions listed under specific BASIC dialects for structured versions.
<
20 K=3
30 M=0
Line 1,038 ⟶ 1,022:
50 M=INT(I*((M+K)/I-INT((M+K)/I))+0.5)
60 NEXT I
70 PRINT "Survivor is number";M</
{{out}}
<pre>Survivor is number 30</pre>
==={{header|ANSI BASIC}}===
{{trans|ALGOL 68}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">100 FUNCTION josephus (n, k, m)
110 ! Return m-th on the reversed kill list; m=0 is final survivor.
120 LET lm = m ! Local copy OF m
130 FOR a = m+1 TO n
140 LET lm = MOD(lm+k, a)
150 NEXT a
160 LET josephus = lm
170 END FUNCTION
180 LET n = 41
190 LET k=3
200 PRINT "n =";n, "k =";k,"final survivor =";josephus(n, k, 0)
210 END
</syntaxhighlight>
{{out}}
<pre>
n = 41 k = 3 final survivor = 30
</pre>
==={{header|Applesoft BASIC}}===
Translated from the BASIC implementation above and the ANSI Standard BASIC.
<syntaxhighlight lang="applesoft basic">
10 DEF FN MOD(X) = X - INT (X / A) * A
20 LM = 0: INPUT "GIVE N AND K (N,K): ";N,K
Line 1,050 ⟶ 1,055:
40 FOR A = 1 TO N: LM = FN MOD(LM + K): NEXT A
50 PRINT "N = ";N;", K = ";K;", SURVIVOR: ";LM
</syntaxhighlight>
{{out}}
<pre>GIVE N AND K (N,K): 41,3
N = 41, K = 3, SURVIVOR: 30</pre>
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">n = 41 #prisoners
k = 3 #order of execution
print "n = "; n, "k = "; k, "final survivor = "; Josephus(n, k, 0)
end
function Josephus(n, k, m)
lm = m
for i = m + 1 to n
lm = (lm + k) mod i
next
return lm
end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic">REM >josephus
PRINT "Survivor is number "; FNjosephus(41, 3, 0)
END
:
DEF FNjosephus(n%, k%, m%)
LOCAL i%
FOR i% = m% + 1 TO n%
m% = (m% + k%) MOD i%
NEXT
= m%</syntaxhighlight>
{{out}}
<pre>Survivor is number 30</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">100 n = 41
110 k = 3
120 print "n = ";n,"k = ";k,"final survivor = ";josephus(n,k,0)
130 end
140 function josephus(n,k,m)
150 lm = m
160 for i = m+1 to n
170 lm = (lm+k) mod i
180 next
190 josephus = lm
200 end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">'using 1 to n
define prisoners = 0, step = 0, killcount = 0, survivor = 0
define fn (josephus) as ( survivor + step ) % killcount
do
input "Prisoners", prisoners
input "Step", step
gosub executioner
loop
sub executioner
let killcount = 1
do
let killcount = killcount + 1
let survivor = (josephus)
loop killcount < prisoners
print "survivor = ", survivor
return</syntaxhighlight>
{{out| Output}}<pre>prisoners? 41
step? 3
survivor = 30</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">
Function Josephus (n As Integer, k As Integer, m As Integer) As Integer
Dim As Integer lm = m
For i As Integer = m + 1 To n
lm = (lm + k) Mod i
Next i
Josephus = lm
End Function
Dim As Integer n = 41 'prisioneros
Dim As Integer k = 3 'orden de ejecución
Print "n ="; n, "k ="; k, "superviviente = "; Josephus(n, k, 0)
</syntaxhighlight>
{{out}}
<pre>
n = 41 k = 3 superviviente = 30
</pre>
==={{header|FTCBASIC}}===
<syntaxhighlight lang="basic">define prisoners = 0, step = 0, killcount = 0
define survivor = 0, remainder = 0
do
print "Prisoners: " \
input prisoners
print "Step: " \
input step
gosub executioner
loop
sub executioner
let killcount = 1
do
let killcount = killcount + 1
let survivor = survivor + step
let survivor = survivor / killcount
carry survivor
loop killcount < prisoners
print "survivor = " \
print survivor
return</syntaxhighlight>
==={{header|Gambas}}===
<syntaxhighlight lang="vbnet">Public Sub Main()
Dim n As Integer = 41 'prisoners
Dim k As Integer = 3 'order of execution
Print "n = "; n, "k = "; k, "final survivor = "; Josephus(n, k, 0)
End
Function Josephus(n As Integer, k As Integer, m As Integer) As Integer
Dim lm As Integer = m
For i As Integer = m + 1 To n
lm = (lm + k) Mod i
Next
Return lm
End Function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|GW-BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|PC-BASIC|any}}
{{works with|MSX Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">10 LET N = 41
20 LET K = 3
30 LET M = 0
40 GOSUB 100
50 PRINT "n ="; N, "k ="; K, "final survivor ="; LM
60 END
100 REM Josephus
110 REM Return m-th on the reversed kill list; m=0 is final survivor.
120 LET LM = M : REM Local copy of m
130 FOR A = M+1 TO N
140 LET LM = (LM+K) MOD A: REM MOD function
150 NEXT A
160 RETURN</syntaxhighlight>
==={{header|IS-BASIC}}===
<
110 INPUT PROMPT "Number of prisoners: ":NP
120 INPUT PROMPT "Execution step: ":EX
Line 1,069 ⟶ 1,251:
210 NEXT
220 LET JOSEPHUS=M
230 END DEF</
==={{header|Minimal BASIC}}===
{{works with|QBasic}}
{{works with|QuickBasic}}
{{works with|Applesoft BASIC}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
{{works with|MSX BASIC}}
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
{{works with|Run BASIC}}
<syntaxhighlight lang="qbasic">10 LET N = 41
20 LET K = 3
30 LET M = 0
40 GOSUB 100
50 PRINT "N ="; N, "K ="; K, "FINAL SURVIVOR ="; S
60 GOTO 150
100 LET S = M
110 FOR A = M+1 TO N
120 LET S = INT(A * ((S+K) / A - INT((S+K) / A)) + 0.5)
130 NEXT A
140 RETURN
150 END</syntaxhighlight>
==={{header|MSX Basic}}===
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|Palo Alto Tiny BASIC}}===
{{trans|ANSI BASIC}}
<syntaxhighlight lang="basic">
10 REM JOSEPHUS PROBLEM
20 LET N=41,K=3,M=0
30 GOSUB 100
40 PRINT #1,"N =",N,", K =",K,", FINAL SURVIVOR =",L
50 STOP
90 REM ** JOSEPHUS
100 LET L=M
110 FOR A=M+1 TO N
120 LET L=L+K-((L+K)/A)*A
130 NEXT A
140 RETURN
</syntaxhighlight>
{{out}}
<pre>
N = 41, K = 3, FINAL SURVIVOR = 30
</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">NewList prisoners.i()
Procedure f2l(List p.i())
FirstElement(p()) : tmp.i=p()
DeleteElement(p(),1) : LastElement(p())
AddElement(p()) : p()=tmp
EndProcedure
Procedure l2f(List p.i())
LastElement(p()) : tmp.i=p()
DeleteElement(p()) : FirstElement(p())
InsertElement(p()) : p()=tmp
EndProcedure
OpenConsole()
Repeat
Print(#LF$+#LF$)
Print("Josephus problem - input prisoners : ") : n=Val(Input())
If n=0 : Break : EndIf
Print(" - input steps : ") : k=Val(Input())
Print(" - input survivors : ") : s=Val(Input()) : If s<1 : s=1 : EndIf
ClearList(prisoners()) : For i=0 To n-1 : AddElement(prisoners()) : prisoners()=i : Next
If n<100 : Print("Executed : ") : EndIf
While ListSize(prisoners())>s And n>0 And k>0 And k<n
For j=1 To k : f2l(prisoners()) : Next
l2f(prisoners()) : FirstElement(prisoners()) : If n<100 : Print(Str(prisoners())+Space(2)) : EndIf
DeleteElement(prisoners())
Wend
Print(#LF$+"Surviving: ")
ForEach prisoners()
Print(Str(prisoners())+Space(2))
Next
ForEver
End</syntaxhighlight>
{{out}}
<pre>Josephus problem - input prisoners : 5
- input steps : 2
- input survivors : 1
Executed : 1 3 0 4
Surviving: 2
Josephus problem - input prisoners : 41
- input steps : 3
- input survivors : 1
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 problem - input prisoners : 41
- input steps : 3
- input survivors : 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
Surviving: 15 30 34
Josephus problem - input prisoners : 71
- input steps : 47
- input survivors : 11
Executed : 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
Surviving: 64 14 27 28 29 35 39 41 45 49 58
Josephus problem - input prisoners :</pre>
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">FUNCTION josephus (n, k, m)
lm = m
FOR i = m + 1 TO n
lm = (lm + k) MOD i
NEXT i
josephus = lm
END FUNCTION
n = 41
k = 3
PRINT "n = "; n, "k = "; k, "final survivor = "; josephus(n, k, 0)
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Quite BASIC}}===
<syntaxhighlight lang="qbasic">10 LET N = 41
20 LET K = 3
30 LET M = 0
40 GOSUB 100
50 PRINT "N = " ; N; " K = "; K; " FINAL SURVIVOR ="; S
60 END
100 LET S = M
110 FOR A = M+1 TO N
120 LET S = INT(A * ((S+K) / A - INT((S+K) / A)) + 0.5)
130 NEXT A
140 RETURN</syntaxhighlight>
==={{Header|Tiny BASIC}}===
<syntaxhighlight lang="qbasic"> REM Josephus problem
LET N = 41
LET K = 3
LET M = 0
GOSUB 10
PRINT "N = ", N
PRINT "K = ", K
PRINT "FINAL SURVIVOR = ", S
END
REM ** JOSEPHUS
10 LET S = M
LET I = M + 1
20 IF I = N THEN GOTO 30
LET S = S + K - ((S + K) / I) * I
LET I = I + 1
GOTO 20
30 RETURN
</syntaxhighlight>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION josephus(n, k, m)
LET lm = m
FOR i = m+1 TO n
LET lm = REMAINDER(lm+k,i)
NEXT i
LET josephus = lm
END FUNCTION
LET n = 41
LET k = 3
PRINT "n = "; n, "k = "; k, "final survivor = "; josephus(n, k, 0)
END</syntaxhighlight>
{{out}}
<pre>Same as QBasic entry.</pre>
==={{header|VBScript}}===
<syntaxhighlight lang="vb">
Function josephus(n,k,s)
Set prisoner = CreateObject("System.Collections.ArrayList")
For i = 0 To n - 1
prisoner.Add(i)
Next
index = -1
Do Until prisoner.Count = s
step_count = 0
Do Until step_count = k
If index+1 <= prisoner.Count-1 Then
index = index+1
Else
index = (index+1)-(prisoner.Count)
End If
step_count = step_count+1
Loop
prisoner.RemoveAt(index)
index = index-1
Loop
For j = 0 To prisoner.Count-1
If j < prisoner.Count-1 Then
josephus = josephus & prisoner(j) & ","
Else
josephus = josephus & prisoner(j)
End If
Next
End Function
'testing the function
WScript.StdOut.WriteLine josephus(5,2,1)
WScript.StdOut.WriteLine josephus(41,3,1)
WScript.StdOut.WriteLine josephus(41,3,3)
</syntaxhighlight>
{{Out}}
<pre>
2
30
15,30,34
</pre>
==={{header|Visual Basic .NET}}===
{{trans|D}}
<syntaxhighlight lang="vbnet">Module Module1
'Determines the killing order numbering prisoners 1 to n
Sub Josephus(n As Integer, k As Integer, m As Integer)
Dim p = Enumerable.Range(1, n).ToList()
Dim i = 0
Console.Write("Prisoner killing order:")
While p.Count > 1
i = (i + k - 1) Mod p.Count
Console.Write(" {0}", p(i))
p.RemoveAt(i)
End While
Console.WriteLine()
Console.WriteLine("Survivor: {0}", p(0))
End Sub
Sub Main()
Josephus(5, 2, 1)
Console.WriteLine()
Josephus(41, 3, 1)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>Prisoner killing order: 2 4 1 5
Survivor: 3
Prisoner killing order: 3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
Survivor: 31</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="vb">n = 41 //prisoners
k = 3 //order of execution
print "n = ", n, "\tk = ", k, "\tfinal survivor = ", Josephus(n, k, 0)
end
sub Josephus(n, k, m)
local lm
lm = m
for i = m + 1 to n
lm = mod(lm + k, i)
next
return lm
end sub</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|ZX Spectrum Basic}}===
{{trans|ANSI BASIC}}
<syntaxhighlight lang="zxbasic">10 LET n=41: LET k=3: LET m=0
20 GO SUB 100
30 PRINT "n= ";n;TAB (7);"k= ";k;TAB (13);"final survivor= ";lm
40 STOP
100 REM Josephus
110 REM Return m-th on the reversed kill list; m=0 is final survivor.
120 LET lm=m: REM Local copy of m
130 FOR a=m+1 TO n
140 LET lm=FN m(lm+k,a)
150 NEXT a
160 RETURN
200 DEF FN m(x,y)=x-INT (x/y)*y: REM MOD function
</syntaxhighlight>
=={{header|Batch File}}==
Uses C's <code>jos()</code> function.
{{trans|C}}
<
setlocal enabledelayedexpansion
Line 1,104 ⟶ 1,575:
)
echo !surv_list!
goto :EOF</
{{Out}}
<pre>30
Line 1,110 ⟶ 1,581:
Press any key to continue . . .</pre>
=={{header|Befunge}}==
The number of prisoners and step size are read from stdin.
<
v0p01<&_,#!>#:<"Step size: "<
>1+:20p00g`!#v_0" :rovivru"v
^g02%g02+g01<<@.$_,#!>#:<"S"<</
{{out}}
Line 1,138 ⟶ 1,596:
=={{header|C}}==
<
// m-th on the reversed kill list; m = 0 is final survivor
Line 1,183 ⟶ 1,641:
return 0;
}</
{{out}}
<pre>
Line 1,191 ⟶ 1,649:
=={{header|C sharp|C#}}==
<
namespace Josephus
{
Line 1,272 ⟶ 1,730:
}
}
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <vector>
Line 1,353 ⟶ 1,811:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
{{out}}
<pre>
Line 1,391 ⟶ 1,849:
=={{header|Clojure}}==
<
(defn josephus [n k]
Line 1,403 ⟶ 1,861:
", an executioner moving around the"))
(println (str "circle " k " at a time will leave prisoner number "
(inc (josephus n k)) " as the last survivor.")))</
{{Output}}
Line 1,411 ⟶ 1,869:
=={{header|Common Lisp}}==
Using a loop:
<
(loop for a from (1+ m) upto n do
(setf m (mod (+ m k) a)))
m)</
Using a circular list.
<
(let* ((list (loop for i below n
collect i))
Line 1,437 ⟶ 1,895:
(move-forward)
(kill-item))
(first list))))</
{{out|Example}}
CL-USER > (kill 41 3)
Line 1,444 ⟶ 1,902:
=={{header|Crystal}}==
{{trans|Ruby}}
<
k = ARGV.fetch(1, 3).to_i # k default is 3 or ARGV[1]
Line 1,450 ⟶ 1,908:
while prisoners.size > 1; prisoners.rotate!(k-1).shift end
puts "From #{n} prisoners, eliminating each prisoner #{k} leaves prisoner #{prisoners.first}."
</syntaxhighlight>
{{out}}
<pre>
Line 1,465 ⟶ 1,923:
=={{header|D}}==
{{trans|Python}}
<
T pop(T)(ref T[] items, in size_t i) pure /*nothrow*/ @safe /*@nogc*/ {
Line 1,491 ⟶ 1,949:
writeln;
josephus(41, 3).writeln;
}</
{{out}}
<pre>Prisoner killing order:
Line 1,502 ⟶ 1,960:
Survivor: 30</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,Classes,StdCtrls,ExtCtrl}}
Uses standard Delphi TList to hold and delete numbers as it analyzes the data.
<syntaxhighlight lang="Delphi">
type TIntArray = array of integer;
procedure GetJosephusSequence(N,K: integer; var IA: TIntArray);
{Analyze sequence of deleting every K of N numbers}
{Retrun result in Integer Array}
var LS: TList;
var I,J: integer;
begin
SetLength(IA,N);
LS:=TList.Create;
try
{Store number 0..N-1 in list}
for I:=0 to N-1 do LS.Add(Pointer(I));
J:=0;
for I:=0 to N-1 do
begin
{Advance J by K-1 because iterms are deleted}
{And wrapping around if it J exceed the count }
J:=(J+K-1) mod LS.Count;
{Caption the sequence}
IA[I]:=Integer(LS[J]);
{Delete (kill) one item}
LS.Delete(J);
end;
finally LS.Free; end;
end;
procedure ShowJosephusProblem(Memo: TMemo; N,K: integer);
{Analyze and display one Josephus Problem}
var IA: TIntArray;
var I: integer;
var S: string;
const CRLF = #$0D#$0A;
begin
GetJosephusSequence(N,K,IA);
S:='';
for I:=0 to High(IA) do
begin
if I>0 then S:=S+',';
if (I mod 12)=11 then S:=S+CRLF+' ';
S:=S+IntToStr(IA[I]);
end;
Memo.Lines.Add('N='+IntToStr(N)+' K='+IntToStr(K));
Memo.Lines.Add('Sequence: ['+S+']');
Memo.Lines.Add('Survivor: '+IntToStr(IA[High(IA)]));
Memo.Lines.Add('');
end;
procedure TestJosephusProblem(Memo: TMemo);
{Test suite of Josephus Problems}
begin
ShowJosephusProblem(Memo,5,2);
ShowJosephusProblem(Memo,41,3);
end;
</syntaxhighlight>
{{out}}
<pre>
N=5 K=2
Sequence: [1,3,0,4,2]
Survivor: 2
N=41 K=3
Sequence: [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]
Survivor: 30
</pre>
{{trans|Javascript}}
<
int[][] Josephus(in int n, int k, int s=1) {
Line 1,520 ⟶ 2,054:
Josephus(41, 3);
Josephus(23482, 3343, 3);
}}</
{{out}}
<pre>Josephus(5,1,1) -> 2 / 1 3 0 4
Josephus(41,2,1) -> 30 / 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(23482,3342,3) -> 1087 1335 13317 / 3342 6685 10028 13371 16714 20057 23400 3261 6605 9949 13293 16637 19981 23325 3187 6532 9877 13222 16567 19912 23257 3120 6466 9812 13158 16504 19850 23196 3060 6407 9754 13101 16448 19795 23142 3007 6355 9703 13051 16399 19747 23095 2961 6310 9659 ...</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
n = 41
k = 3
print "prisoners: " & n
print "step size: " & k
for i = 1 to n
lm = (lm + k) mod i
.
print "final survivor: " & lm
</syntaxhighlight>
=={{header|EchoLisp}}==
We use a circular list and apply the 'process'. Successive rests are marked 🔫 (killed) or 😥 (remaining). NB: the '''(mark)''' function marks lists and sub-lists, not items in lists. The printed mark appears before the first item in the list.
<
;; input
(define N 41)
Line 1,542 ⟶ 2,088:
(else (mark lst '😥 ) ;; relieved face
(kill (cdr lst ) (1- skip))))) ;; skip 1 and goto next
</syntaxhighlight>
{{out}}
<
;; kill N-1
(for ((i (1- N) )) (set! last-one (kill last-one (1- K))))
Line 1,568 ⟶ 2,114:
🔫 33 😥 34 🔫 35 🔫 36 🔫 37 🔫 38 🔫 39 🔫 40 🔫 0 🔫 1 🔫 0 … ∞)
</syntaxhighlight>
=={{header|EDSAC order code}}==
The algorithm is of the "increasing modulus" type. Though written independently of the Ring solution, it seems to be essentially the same. The (n,k) pairs used by the demo program are taken from solutions on this page. Running time totals 1.2 EDSAC minutes for the first eight examples, and 12.5 for the last two.
<syntaxhighlight lang="edsac">
[Jospehus problem - Rosetta Code
EDSAC program (Initial Orders 2)]
[Arrange the storage]
T45K P56F [H parameter: library subroutine R4 to read integer]
T46K P80F [N parameter: subroutine to print 17-bit non-neg integer]
T47K P160F [M parameter: main routine]
T51K P128F [G parameter: subroutine to find last survivor]
[Library subroutine M3, runs at load time and is then overwritten.
Prints header; here, last character sets teleprinter to figures.]
PF GK IF AF RD LF UF OF E@ A6F G@ E8F EZ PF
*!!!!N!!!!!K!!!!SURVIVOR@&#..PZ
[============== G parameter: Subroutine to find last survivor ==============
Input: 4F = n = number of prisoners
5F = k = executioner's step
Output: 0F = 0-based index of last survivor]
[Pascal equivalent:
z := 0; // solution when n = 1
for j := 2 to n do z := (z + k) mod j;
result := z;]
E25K TG GK
A3F T22@ [plant return link as usual]
T23@ [z := 0]
A2F T24@ [j := 2]
E16@ [jump to middle of loop]
[6] TF [clear acc]
A23@ A5F [acc := z + k]
[Get residue modulo j by repeatedly subtracting j.
The number of subtractions is usually small.]
[9] S24@ E9@ [subtract j till result < 0]
A24@ [add back the last j]
T23@ [update z]
A24@ A25@ T24@ [inc(j)]
[16] A4F S24@ [acc := n - j]
E6@ [loop back if j <= n]
TF [done: clear acc]
A23@ TF [return z (last survivor) to caller in 0F]
[22] ZF [(planted) jump back to caller]
[Storage]
[23] PF [Pascal z]
[24] PF [Pascal j]
[25] PD [constant 1]
[====================== M parameter: Main routine ======================]
E25K TM GK
[0] PF [negative data count]
[1] PF [number of prisoners]
[2] PF [executioner's step]
[3] !F [space]
[4] @F [carriage return]
[5] &F [line feed]
[6] K4096F [null character]
[Enter with acc = 0]
[7] A7@ GH [call subroutine R4, sets 0D := count of (n,k) pairs]
SF [acc := count negated; it's assumed that count < 2^16]
E46@ [exit if count = 0]
LD [shift count into address field]
[12] T@ [update negative loop counter]
A13@ GH [call library subroutine R4, 0D := number of prisoners]
AF T1@ [store number of prisoners, assumed < 2^16]
A17@ GH [call library subroutine R4, 0D := executioner's step]
AF T2@ [store executioner's step, assumed < 2^16]
A3@ T1F [to print leading 0's as spaces]
A1@ TF [pass number of prisoners to print subroutine]
A25@ GN O3@ [print number of prisoners, plus space]
A2@ TF [same for executioner's step]
A30@ GN O3@
A1@ T4F [pass number of prisoners to "last survivor" subroutine]
A2@ T5F [same for executioner's step]
A37@ GG [call subroutine, 0F := 0-based index of last survivor]
A39@ GN O4@ O5@ [print last survivor, plus CR,LF]
A@ A2F [increment negative counter]
G12@ [loop back if still negative]
[46] O6@ [print null to flush printer buffer]
ZF [halt the machine]
[The next 3 lines put the entry address into location 50,
so that it can be accessed via the X parameter (see end of program).]
T50K
P7@
T7Z
[================== H parameter: Library subroutine R4 ==================
Input of one signed integer, returned in 0D.
22 locations.]
E25K TH GK
GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF
[============================= N parameter ==============================
Subroutine to print non-negative 17-bit integer.
Input: 0F = integer to be printed (not preserved)
1F = character for leading zero (preserved)
Workspace: 4F..7F, 38 locations]
E25K TN
GKA3FT34@A1FT7FS35@T6FT4#FAFT4FH36@V4FRDA4#FR1024FH37@E23@O7FA2F
T6FT5FV4#FYFL8FT4#FA5FL1024FUFA6FG16@OFTFT7FA6FG17@ZFP4FZ219DTF
[==========================================================================
On the original EDSAC, the following (without the whitespace and comments)
might have been input on a separate tape.]
E25K TX GK
EZ [define entry point]
PF [acc = 0 on entry]
[Count of (n,k) pairs, then the pairs, to be read by library subroutine R4.
Note that sign comes *after* value.]
10+5+2+12+4+41+3+50+2+60+3+71+47+123+3+123+47+10201+17+23482+3343+
</syntaxhighlight>
{{out}}
<pre>
N K SURVIVOR
5 2 2
12 4 0
41 3 30
50 2 36
60 3 40
71 47 29
123 3 54
123 47 101
10201 17 7449
23482 3343 1335
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,624 ⟶ 2,298:
end
</syntaxhighlight>
{{out}}
Line 1,644 ⟶ 2,318:
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">
defmodule Josephus do
def find(n,k) do
Line 1,660 ⟶ 2,334:
Josephus.find(41,3)
</syntaxhighlight>
{{out}}
Line 1,666 ⟶ 2,340:
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">(defun jo (n k)
(
n))))
(message "%d" (jo 50 2))
(message "%d" (jo 60 3))</syntaxhighlight>
{{out}}
37
41
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module( josephus_problem ).
Line 1,705 ⟶ 2,383:
kill_few( Kill, Prisoners ) ->
lists:split( Kill - 1, Prisoners ).
</syntaxhighlight>
{{out}}
Line 1,721 ⟶ 2,399:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM JOSEPHUS
Line 1,775 ⟶ 2,453:
MAIN(41,3,3->ERRORS)
END PROGRAM
</syntaxhighlight>
Note: Adapted from AWK version! Output is the same.
=={{header|Factor}}==
<
IN: josephus
:: josephus ( k n -- m )
n [1,b] 0 [ [ k + ] dip mod ] reduce ;</
<pre>IN: scratchpad 3 41 josephus .
30
Line 1,789 ⟶ 2,467:
=={{header|Forth}}==
<
<pre>josephus .
30
Line 1,796 ⟶ 2,474:
=={{header|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.
<
implicit none
integer :: n, i, k, p
Line 1,817 ⟶ 2,495:
print *, "Alive", p
deallocate(next)
end program</
=={{header|friendly interactive shell}}==
<
# If the list is empty, don't do anything.
test (count $argv) -ge 2; or return
Line 1,858 ⟶ 2,516:
end
echo Prisoner (execute 3 (seq 0 40))[-1] survived.</
{{out}}
<pre>Prisoner 30 survived.</pre>
It's also possible to calculate more than one survivor.
<
{{out}}
<pre>Prisoners 34 15 30 survived.</pre>
Prisoners don't have to be numbers.
<
{{out}}
<pre>Prisoner William survived.</pre>
=={{header|Frink}}==
<
killingCycle[prisonerCount,killStep = 2] :=
{
Line 1,893 ⟶ 2,551:
println[killingCycle[41,3]] // Enter in total number of prisoners and the number to skip each cycle
</syntaxhighlight>
{{out}}
Line 1,903 ⟶ 2,561:
=={{header|Fōrmulæ}}==
'''Solution:'''
We start with two lists. The first one contains initially the prisoners (their number), and the second one contains the kills, and it is initially empty.
On every kill, the number of the killed prisoner is deleted from the first list, and it is (striked out) appended to the second one, in order to show the order of kills.
In order to leave more than one survivor, the cycle is repeated n-s times, where n is the number of prisoners and s is the number of survivors.
At the end, the two lists are retrieved.
Even when Fōrmulæ is 1-based, the list is filled starting with the 0 prisoner, in order to the results can be compared with other languages (mostly 0-based).
[[File:Fōrmulæ - Josephus problem 01.png]]
'''Case 1.''' 5 prisoners, killing every 2:
[[File:Fōrmulæ - Josephus problem 02.png]]
[[File:Fōrmulæ - Josephus problem 03.png]]
'''Case 2.''' 41 prisoners, killing every 3:
[[File:Fōrmulæ - Josephus problem 04.png]]
[[File:Fōrmulæ - Josephus problem 05.png]]
'''Case 3.''' The captors may be especially kind and let m survivors free, and Josephus might just have m - 1 friends to save.:
[[File:Fōrmulæ - Josephus problem 06.png]]
[[File:Fōrmulæ - Josephus problem 07.png]]
'''Case 4. Larger example.''' 23,482 prisoners, killing every 3,343, leaving 3 survivors. Only the survivors are shown (the first element of the resulting list is extracted):
[[File:Fōrmulæ - Josephus problem 08.png]]
[[File:Fōrmulæ - Josephus problem 09.png]]
'''Drawing history'''
The following function creates a raster graphics of size n squares width, and n + 1 squares height, where n is the number of prisoners. The size of the square is defines as pixels.
The horizontal axis (right to left) is the number of the prisoner. The vertical axis (top to bottom) is the number of cycle.
An alive prisoner is drawn as green, a dead one is drawn as black.
[[File:Fōrmulæ - Josephus problem 10.png]]
'''Example 1.''' Drawing for the case 41 prisoners, killing every 3 (cell size is 5x5 pixels)::
[[File:Fōrmulæ - Josephus problem 11.png]]
[[File:Fōrmulæ - Josephus problem 12.png]]
'''Example 2.''' Drawing for the case 500 prisoners, killing every 6 (cell size is 1x1 pixel)::
[[File:Fōrmulæ - Josephus problem 13.png]]
[[File:Fōrmulæ - Josephus problem 14.png]]
=={{header|Go}}==
<
import "fmt"
Line 1,958 ⟶ 2,672:
fmt.Printf("%5d%10d\n", i, position(41, 3, i))
}
}</
{{out}}
<pre>
Line 2,007 ⟶ 2,721:
=={{header|Groovy}}==
<
// init user pool
def users = new int[size];
Line 2,043 ⟶ 2,757:
println "4 safe spots for n = 10201 and k = 17: " + Josephus(10201,17,4);
</syntaxhighlight>
{{out}}
<pre>
Line 2,054 ⟶ 2,768:
The arguments to the "main" function are: n = number of prisoners, k = kill every kth prisoner,
m = show at most m survivors
<
import System.Environment (getArgs)
Line 2,094 ⟶ 2,808:
(counter (read k)) (read m)
_ -> print $ snd $ killRecursive (prisoners 41) (counter 3) 1
</syntaxhighlight>
Using modulo and list split, indices are 1-based. This is much faster than cycled list for larger numbers:
<
jseq n k = f n [1 .. n]
where
Line 2,112 ⟶ 2,826:
main = do
print $ jseq 41 3
print $ jos 10000 100</
=={{header|Icon}} and {{header|Unicon}}==
Line 2,118 ⟶ 2,832:
The following works in both languages.
<
m := integer(A[1]) | 41
c := integer(A[2]) | 3
Line 2,126 ⟶ 2,840:
procedure j(m,c)
return if m==1 then 0 else (j(m-1,c)+c)%m
end</
{{out}}
Line 2,139 ⟶ 2,853:
This is done awkwardly, but I've had this laying around since the late 1980's...
<
n := total := integer(args[1]) | 41 # Number of people
k := count := integer(args[2]) | 3 # Count
Line 2,165 ⟶ 2,879:
n ?:= integer(tab(upto('.'))) + 1
return n
end</
Sample run:
Line 2,183 ⟶ 2,897:
=== Tacit version ===
<
30</
Structured derivation of the fixed tacit code
<
MoreThanOne=. 1 < #@]
WhileMoreThanOne=. (^:MoreThanOne f.) (^:_)
Line 2,192 ⟶ 2,906:
[ DropNext WhileMoreThanOne prisoners f.
[ (1 }. <:@[ |. ])^:(1 < #@])^:_ i.@]</
=== Explicit version ===
<
NB. use: SKIP josephus NUMBER_OF_PRISONERS
N =: y
Line 2,210 ⟶ 2,924:
3 Josephus 41
30</
=== Explicit version 2 ===
<
Josephus2 =: 4 : '(| x&+)/i. - 1+y'
3 Josephus2 41
30</
=={{header|Java}}==
{{works with|Java|1.5+}}
<
public class Josephus {
Line 2,261 ⟶ 2,975:
System.out.println("Survivors: " + executeAllButM(41, 3, 3));
}
}</
{{out}}
<pre>Prisoners executed in order:
Line 2,271 ⟶ 2,985:
{{trans|Javascript}}
<
import java.util.List;
Line 2,307 ⟶ 3,021:
return s.substring(1, s.length()-1) + dot;
}
}</
{{out}}
<pre>Josephus(5,1,1) -> 2 / 1, 3, 0, 4
Line 2,316 ⟶ 3,030:
=={{header|JavaScript}}==
Labels are 1-based, executioner's solution:
<
init: function(n) {
this.head = {};
Line 2,342 ⟶ 3,056:
return current.label;
}
}</
{{out}}
<pre>
Line 2,350 ⟶ 3,064:
With Array methods:
<
s = s | 1
for (var ps=[], i=n; i--; ) ps[i]=i
Line 2,356 ⟶ 3,070:
document.write((arguments.callee+'').split(/\s|\(/)[1], '(', [].slice.call(arguments, 0), ') -> ', ps, ' / ', ks.length<45?ks:ks.slice(0,45)+',...' , '<br>')
return [ps, ks]
}</
{{out}}
<pre>
Line 2,370 ⟶ 3,084:
The prisoners are numbered from 0 to (n-1) in keeping with jq's array index origin of 0, but the nature of their labeling is immaterial to the algorithm.
<
# as soon as "condition" is true, then emit . and stop:
def do_until(condition; next):
Line 2,381 ⟶ 3,095:
reduce range(0;n) as $i ([]; . + [$i]) # Number the prisoners from 0 to (n-1)
| do_until( length < k or length <= m; .[k:] + .[0:k-1] )
| do_until( length <= m; (k % length) as $i | .[$i:] + .[0:$i-1] );</
'''Examples''':
<
"Survivors for n=\(n), k=\(k), m=\(m): \( josephus(n;k;m) )";
task(41;3;1),
task(23482; 3343; 3)</
{{out}}
$ jq -M -r -n -f josephus.jq
Line 2,397 ⟶ 3,111:
'''Recursive (with Memoize)''':
<
@memoize josephus(n::Integer, k::Integer, m::Integer=1) = n == m ? collect(0:m .- 1) : mod.(josephus(n - 1, k, m) + k, n)
@show josephus(41, 3)
@show josephus(41, 3, 5)</
{{out}}
Line 2,408 ⟶ 3,122:
'''Iterative''':
<
p, i, seq = collect(0:n-1), 0, Vector{typeof(n)}(0)
while length(p) > m
Line 2,421 ⟶ 3,135:
seq, surv = josephus(41, 3, 3)
println("Prisoner killing in order: $seq\nSurvivor: $surv")</
{{out}}
Line 2,430 ⟶ 3,144:
=={{header|Kotlin}}==
<
fun josephus(n: Int, k: Int, m: Int): Pair<List<Int>, List<Int>> {
Line 2,462 ⟶ 3,176:
println()
}
}</
{{out}}
Line 2,481 ⟶ 3,195:
=={{header|Lua}}==
Lua indexes tables starting at 1. Positions are stored from 0,n-1.
<
local positions={}
for i=1,n do
Line 2,505 ⟶ 3,219:
end
josephus(41,3, 1)
</syntaxhighlight>
{{out}}
<pre>Execution 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.
Line 2,511 ⟶ 3,225:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
survivor[41, 3]</
{{out}}
<pre>{30}</pre>
=={{header|MATLAB}}==
<
% Josephus: Given a circle of numPeople individuals, with a count of count,
% find the index (starting at 1) of the survivor [see Josephus Problem]
Line 2,559 ⟶ 3,271:
end
</syntaxhighlight>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
josephus_list(n,k):=(result:[],pos:1,ref:makelist(i,i,n),while ref#[] do (pos:mod(pos+k-2,length(ref))+1,push(ref[pos],result),ref:delete(ref[pos],ref)),
reverse(result));
/* Example */
/* last_survivor:last(josephus_list(41,3));
31
*/
</syntaxhighlight>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 2,587 ⟶ 3,310:
ReadChar
END Josephus.</
=={{header|Nanoquery}}==
{{trans|Python}}
<
p = list(range(0, n-1))
i = 0
Line 2,606 ⟶ 3,329:
println j(5,2)
println
println j(41,3)</
{{out}}
Line 2,618 ⟶ 3,341:
{{trans|REXX}}
Hardly any changes at all...
<
options replace format comments java crossref symbols nobinary
Line 2,650 ⟶ 3,373:
Loop i = 0 To 40 /* look for the surviving p's */
If dead[i] = 0 Then Say i /* found one */
End</
{{out}}
<pre>
Line 2,665 ⟶ 3,388:
{{trans|Python}}
<
proc j(n, k: int): string =
Line 2,684 ⟶ 3,407:
echo j(5,2)
echo j(41,3)</
{{out}}
<pre>Prisoner killing order: 1, 3, 0, 4, 2.
Line 2,694 ⟶ 3,417:
Another more efficient way but without the killing order:
<
## The result is computed backwards. We start from the winner at
## position 0 on last round and compute its position on previous rounds.
Line 2,703 ⟶ 3,426:
echo "Survivor: ", prisonerPos(5, 2)
echo "Survivor: ", prisonerPos(41, 3)</
{{out}}
Line 2,710 ⟶ 3,433:
=={{header|Objeck}}==
<
function : Execute(n : Int, k : Int) ~ Int {
killIdx := 0;
Line 2,760 ⟶ 3,483:
}
}
</syntaxhighlight>
=={{header|Oforth}}==
Line 2,766 ⟶ 3,489:
Oforth lists are 1-based : prisoners are numbered from 1 to n.
<
| prisoners killed i |
n seq asListBuffer ->prisoners
Line 2,778 ⟶ 3,501:
System.Out "Killed : " << killed << "\nSurvivor : " << prisoners << cr
;
</syntaxhighlight>
{{out}}
Line 2,797 ⟶ 3,520:
It was modified to report indexes from 0 and also report the killed list:
<
fun {Pipe Xs L H F}
if L=<H then {Pipe {F Xs L} L+1 H F} else Xs end
Line 2,819 ⟶ 3,542:
result(survivor: Last-1 killed: {Reverse @Killed})
end
{Show {Josephus 41 3}}</
{{Out}}
Line 2,825 ⟶ 3,548:
=={{header|PARI/GP}}==
<
=={{header|Perl}}==
{{trans|Raku}}
<
my $k = 3;
until (@prisoner == 1) {
Line 2,836 ⟶ 3,559:
}
print "Prisoner @prisoner survived.\n"</
{{Out}}
<pre>Prisoner 30 survived.</pre>
=={{header|Phix}}==
I managed to identify eight
Unclassified: Haskell, Python[4 aka learning iter in python], REXX[version 2], RPL (plus Befunge, J
Note all indexes and results are 1-based. For skipping/linked_list/sliding_queue, prisoners do not have to be numbers, the
same would be true for contractacycle and contractalot with the tiniest of tweaks. For recursive/iterative, prisoners are implicitly numbers, not that it would be difficult to use the result(s) to subscript a list of string names.
Line 2,849 ⟶ 3,572:
Method: all prisoners stay where they are, executioner walks round and round, skipping over ever increasing numbers of dead bodies
(slowest of the lot, by quite some margin)
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">skipping</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">survivors</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">nn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,864 ⟶ 3,587:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">--?skipping({"Joe","Jack","William","John","James"},2,1) --> {"William"}</span>
<!--</
===linked list===
AArch64 Assembly, Ada, ARM Assembly, Common Lisp[2, probably], Fortran, JavaScript[1] (albeit dbl-lnk), Python[3].<br>
Method: like skipping, all prisoners stay where they are, but the executioner uses the links to speed things up a bit.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">linked_list</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">survivors</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">)</span>
Line 2,885 ⟶ 3,608:
<span style="color: #008080;">return</span> <span style="color: #7060A8;">remove_all</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===sliding queue===
Clojure, Crystal, D (both), Eiffel, Elixir, Erlang, friendly interactive shell, Go, jq, Perl, PowerShell, PureBasic (albeit one at a time), Quackery, Raku, REBOL, Ruby, Scala, Sidef[1], Tcl, Vlang.
Method: all skipped prisoners rejoin the end of the queue which sidles left, executioner stays put until the queue gets too short.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">sliding_queue</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">survivors</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">)</span>
Line 2,900 ⟶ 3,623:
<span style="color: #008080;">return</span> <span style="color: #000000;">prisoners</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===contractacycle===
Line 2,906 ⟶ 3,629:
Method: executioner walks along killing every k'th prisoner; while he walks back the queue contracts to remove gaps.
(once the queue gets too small it obviously reverts to one at a time, a bit more like contractalot below)
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">contractacycle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">living</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 2,930 ⟶ 3,653:
<span style="color: #008080;">return</span> <span style="color: #000000;">living</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
Groovy does not have a n=s test, it probably is entirely unnecessary. The Groovy code is also somewhat neater, always using
a loop and remove_all() - while not probihitively expensive, it may check lots of things for -1 that the slicing won't.
===contractalot===
11L, Arturo, AutoHotkey, C#, C++, Delphi, Frink, Formulae, Java (both), JavaScript[2], Julia[2], Kotlin, Lua, NanoQuery, Nim, Objeck,
Oforth, Processing, Python[1], R[2], Rust, Seed7, Swift, VBScript, Vedit, VisualBasic.NET, XPL0, zkl. <br>
Method: executioner walks round and round, queue contracts after every kill. Often implemented as execute all prisoners then release last one killed.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">contractalot</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 2,950 ⟶ 3,673:
<span style="color: #008080;">return</span> <span style="color: #000000;">list</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===recursive===
Emacs Lisp, Icon, Julia[1], PARI/GP, PicoLisp (less the optms.n), Sidef[2]<br>
Method: recursive mod maths madness - only handles the lone survivor case.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">recursive</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">recursive</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===iterative===
ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC(*11), Batch File, C (but not ULL), Common Lisp[1], Craft Basic, Easylang, EDSAC (allegedly), Factor, Forth, FreeBASIC, FTCBASIC, Modula-2, Python[2], R, Racket, Ring, SequenceL, ZX Spectrum Basic<br>
Method: iterative mod maths madness - but hey, it will be extremely fast. Unlike recursive, it can also deliver >1 survivor, one at a time.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">iterative</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Return m-th on the reversed kill list; m=0 is final survivor.</span>
Line 2,972 ⟶ 3,695:
<span style="color: #008080;">return</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- (make result 1-based)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===iterative2===
Icon[2]<br>
Method: more iterative maths madness
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">iterative2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
Line 2,989 ⟶ 3,712:
<span style="color: #008080;">return</span> <span style="color: #000000;">nk</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">olda</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- (make result 1-based)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
===test driver===
<!--<
<span style="color: #000080;font-style:italic;">--demo/rosetta/Josephus.exw</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">show_all</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span>
Line 3,060 ⟶ 3,783:
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_iterative</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"iterative"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ITER</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_iterative2</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"iterative2"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ITER2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
As shown for sliding_queue, some of the result sets are in a slightly different order, sometimes, otherwise matching output replaced by "...".
Line 3,093 ⟶ 3,816:
=={{header|PHP}}==
<
function Jotapata($n=41,$k=3,$m=1){$m--;
$prisoners=array_fill(0,$n,false);//make a circle of n prisoners, store false ie: dead=false
Line 3,113 ⟶ 3,836:
}
echo '<pre>'.print_r(Jotapata(41,3,5),true).'<pre>';
</syntaxhighlight>
=={{header|PicoLisp}}==
The counting starts from one instead of zero. The last remaining person is returned.
<syntaxhighlight lang="picolisp">
#general solution
(de jo (N K)
Line 3,141 ⟶ 3,864:
(print (survivor 5 2))
(print (survivor 41 3))
</syntaxhighlight>
{{out}}
<pre>
Line 3,149 ⟶ 3,872:
=={{header|PL/I}}==
<
joseph: Proc Options(main);
/* REXX **************************************************************
Line 3,211 ⟶ 3,934:
End;
End;</
{{out}}
<pre>killed: 02 05 08 11 14 17 20 23 26 29 32 35 38 00 04 09 13 18 22 27 31
Line 3,230 ⟶ 3,953:
Normally when we present the PowerShell parser with an array within an array, it treats it as a cast, and
we end up with the single array of elements. In those cases where we need an array to be treated as a single element of a parent array, we can use the unary comma to force PowerShell to treat it as an element.
<syntaxhighlight lang="powershell">
function Get-JosephusPrisoners ( [int]$N, [int]$K )
{
Line 3,251 ⟶ 3,974:
return $Prisoners
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
# Get the prisoner order for a circle of 41 prisoners, selecting every third
$Prisoners = Get-JosephusPrisoners -N 41 -K 3
Line 3,265 ⟶ 3,988:
$S = 3
"Last $S remaining: " + $Prisoners[-$S..-1]
</syntaxhighlight>
{{out}}
<pre>
Line 3,275 ⟶ 3,998:
=={{header|Processing}}==
Translation of Java example.
<
println("Survivor: " + execute(41, 3));
println("Survivors: " + executeAllButM(41, 3, 3));
Line 3,310 ⟶ 4,033:
println();
return prisoners;
}</
=={{header|Python}}==
<
p, i, seq = list(range(n)), 0, []
while p:
Line 3,388 ⟶ 4,049:
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
>>> </
===Faster way===
Does not show the killing order.
<
r = 0
for i in xrange(1, n+1):
Line 3,402 ⟶ 4,063:
>>> print(josephus(41, 3))
Survivor: 30
>>> </
===Alternate solution with a circular linked list===
Line 3,409 ⟶ 4,070:
In the program, a[p] is the index of the next living prisoner after 'p'. The program stops when p = a[p], that is, when there remains only one living prisoner.
<
a = list(range(1, n + 1))
a[n - 1] = 0
Line 3,427 ⟶ 4,088:
josephus(41, 3)[-1]
30</
===learning iter in python===
<
def josephus(prisoner, kill, surviver):
p = range(prisoner)
Line 3,463 ⟶ 4,124:
The surviver is: [2]
The kill sequence is [1, 3, 0, 4]
</syntaxhighlight>
=={{header|Quackery}}==
Not the fastest method, but illustrates use of ancillary stacks, and using nests as queues.
<
[ stack ] is prisoners ( --> s )
Line 3,503 ⟶ 4,164:
survivors release
executioner-actions release
prisoners take ] is josephus ( n n n --> n )</
'''Testing in Quackery shell:'''
Line 3,515 ⟶ 4,176:
=={{header|R}}==
===Growing circle solution===
<
y <- 0:(r-1)
for (i in (r+1):n)
Line 3,522 ⟶ 4,183:
}
> jose(3,1,41) # r is the number of remained prisoner.
[1] 30</
===Iterative solution===
I hope to be proven wrong, but R seems to be the wrong tool for this problem:
*It is 1-indexed, meaning that we will have a tough time using most solutions that exploit modular arithmetic.
*It lacks any concept of a linked list, meaning that we can't take a circular list approach.
*The idiomatic way to roll an array in R (e.g. as [[Josephus_problem#Ruby|the Ruby solution]] has) is to exploit the head and tail functions, but those break if we are rolling by more than the length of the array (see https://stackoverflow.com/q/18791212
Regardless, it is still solvable. The following adapts a great deal of [[Josephus_problem#Lua|the Lua solution]]. The arguments n, k, and m are as in the task description.
<
{
prisoners <- 0:(n - 1)
exPos <- countToK <- 1
dead <- integer(0)
while(length(prisoners) > m)
{
if(countToK == k)
{
dead <- c(dead, prisoners[exPos])
prisoners <- prisoners[-exPos]
exPos <- exPos - 1
}
exPos <- exPos + 1
countToK <- countToK + 1
if(exPos > length(prisoners))
if(countToK > k)
}
print(paste0("Execution order: ", paste0(dead, collapse = ", "), "."))
paste0("Survivors: ", paste0(prisoners, collapse = ", "), ".")
}</
{{out}}
<pre>> josephusProblem(5, 2, 1)
[1] "Execution order: 1, 3, 0, 4."
[1] "Survivors: 2."
> josephusProblem(41, 3, 1)
[1] "Execution 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."
[1] "Survivors: 30."
> josephusProblem(41, 3, 3)
[1] "Execution 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."
[1] "Survivors: 15, 30, 34."</pre>
=={{header|Racket}}==
<
(define (josephus n k (m 0))
(for/fold ((m (add1 m)))
Line 3,568 ⟶ 4,229:
(remainder (+ m k) a)))
(josephus 41 3) ; ->30</
=={{header|Raku}}==
Line 3,574 ⟶ 4,235:
{{Works with|rakudo|2015-11-12}}
Straightforward implementation of the executioner's algorithm:
<syntaxhighlight lang="raku"
until @prisoner == 1 {
@prisoner.=rotate($k - 1);
Line 3,589 ⟶ 4,250:
my @dalton = <Joe Jack William Averell Rantanplan>;
Execute @dalton, 2;
say "{@dalton} survived.";</
{{out}}
Line 3,597 ⟶ 4,258:
=={{header|REBOL}}==
Works in Rebol 2 or 3
<
execute: func [death-list [block!] kill [integer!]] [
Line 3,609 ⟶ 4,270:
prisoner: [] for n 0 40 1 [append prisoner n]
execute prisoner 3
print ["Prisoner" prisoner "survived"]</
{{out}}
<pre>Prisoner 30 survived</pre>
And any kind of list will do:
<
execute for-the-chop 2
print [for-the-chop "survived"]</
{{out}}
<pre>William survived</pre>
Line 3,621 ⟶ 4,282:
=={{header|REXX}}==
===version 1===
<
* 15.11.2012 Walter Pachl - my own solution
* 16.11.2012 Walter Pachl generalized n prisoners + w killing distance
Line 3,668 ⟶ 4,329:
If dead.i=0 Then s=s i /* found one */
End
Say 'Survivor(s):'s /* show */</
{{out}}
Line 3,685 ⟶ 4,346:
This solution is an ''executor's'' solution.
<
parse arg N K Z R . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 41 /* men not specified? Use default.*/
Line 3,708 ⟶ 4,369:
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*plurals*/
th: y= arg(1); return y || word('th st nd rd', 1+ y // 10 * (y//100%10\==1) * (y//10<4))</
{{out|output|text= when using the default inputs:}}
<pre>
Line 3,727 ⟶ 4,388:
=={{header|Ring}}==
<
n = 41
k=3
Line 3,739 ⟶ 4,400:
josephus = lm
return josephus
</syntaxhighlight>
Output:
<pre>
n =41 k = 3 final survivor = 30
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.7}}
===Last survivor===
We use here the recursive approach.
≪ IF OVER 1 - THEN LAST OVER JPHUS SWAP + SWAP MOD ELSE DROP2 0 END
≫
'JPHUS' STO
5 2 JPHUS
41 3 JPHUS
{{out}}
<pre>
2: 2
1: 30
</pre>
===m survivors + ordered list of executed prisoners===
Program execution mimics prisoners' execution ;-)
≪ OVER SIZE → list idx len
≪ {}
1 len 1 - FOR j
list
j idx + 1 - len MOD 1 +
GET +
NEXT
≫ ≫
'RnDL' STO
≪ → n k m
≪ {} DUP
1 n FOR j j 1 - + NEXT
m n 1 - START
k 1 - OVER SIZE MOD 1 +
DUP2 GET 4 ROLL SWAP + 3 ROLLD
RnDL
NEXT
≫ ≫
'JPHUL' STO
41 3 2 JPHUL
{{out}}
<pre>
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 }
1: { 15 30 }
</pre>
=={{header|Ruby}}==
<
k = (ARGV[1] || 3).to_i
prisoners = (0...n).to_a
prisoners.rotate!(k-1).shift while prisoners.length > 1
puts prisoners.first</
=={{header|Rust}}==
<
const K: usize = 3;
const M: usize = 3;
Line 3,779 ⟶ 4,485:
println!("Executed position number {}: {}", POSITION, executed[POSITION - 1]);
println!("Survivors: {:?}", prisoners);
}</
{{out}}
<pre>
Line 3,792 ⟶ 4,498:
(Prisoners labeled 0 to n-1)
<
val prisoners = ((0 until prisonerCount) map (_.toString)).toList
Line 3,818 ⟶ 4,524:
print( dead.mkString(" ") )
println( "\n\nJosephus is prisoner " + alive(0) )</
{{out}}
<pre>Prisoners executed in order:
Line 3,832 ⟶ 4,538:
uses ''str'' to define everything necessary to write an array of integers.
This way the main program can write the survivor array.
<
const func array integer: executeAllButM (in integer: n, in integer: k, in integer: m) is func
Line 3,873 ⟶ 4,579:
writeln("Survivor: " <& executeAllButM(41, 3, 1));
writeln("Survivors: " <& executeAllButM(41, 3, 3));
end func;</
{{out}}
Line 3,887 ⟶ 4,593:
=={{header|SequenceL}}==
{{trans|Python}}
<
josephus(n, k) := josephusHelper(n, k, 1, 0);
Line 3,894 ⟶ 4,600:
r when i > n
else
josephusHelper(n, k, i + 1, (r + k) mod i);</
{{out}}
Line 3,903 ⟶ 4,609:
=={{header|Sidef}}==
Iterative:
<
var prisoners = @^n
while (prisoners.len > 1) {
Line 3,909 ⟶ 4,615:
}
return prisoners[0]
}</
Recursive:
<
n == 1 ? 0 : ((__FUNC__(n-1, k) + k) % n)
};</
Calling the function:
<
say "Prisoner #{survivor} survived.";</
{{out}}
<pre>Prisoner 30 survived.</pre>
=={{header|Swift}}==
<
class func lineUp(#numberOfPeople:Int) -> [Int] {
Line 3,967 ⟶ 4,673:
println("Josephus is number: \(Josephus.execute(numberOfPeople: 41, spacing: 3))")
println()
println("Survivors: \(Josephus.execucteAllButM(numberOfPeople: 41, spacing: 3, save: 3))")</
{{out}}
<pre>
Line 3,980 ⟶ 4,686:
=={{header|TypeScript}}==
<
if (!n) {
return 1;
Line 3,986 ⟶ 4,692:
return ((josephus(n - 1, k) + k - 1) % n) + 1;
}</
{{out}}
<pre>
Line 3,994 ⟶ 4,700:
=={{header|Tcl}}==
<
for {set i 0} {$i<$number} {incr i} {lappend l $i}
for {set i 1} {[llength $l]} {incr i} {
Line 4,007 ⟶ 4,713:
}
return [lrange $killseq end-[expr {$survivors-1}] end]
}</
Demonstrating:
<
puts "remaining 4: [join [josephus 41 3 4] ,]"</
{{out}}
<pre>
remaining: 30
remaining 4: 3,34,15,30
</pre>
Line 4,065 ⟶ 4,728:
When the macro finishes, you can see the list of survivors in the edit buffer.
<
#2 = 3 // step size
#3 = 1 // number of survivors
Line 4,084 ⟶ 4,747:
}
if (At_EOF) { BOF }
}</
{{out}}
Line 4,098 ⟶ 4,761:
</pre>
=={{header|
{{trans|
<syntaxhighlight lang="v (vlang)">// basic task fntion
fn final_survivor(n int, kk int) int {
// argument validation omitted
mut circle := []int{len: n, init: it}
k := kk-1
mut ex_pos := 0
for circle.len > 1 {
ex_pos = (ex_pos + k) % circle.len
circle.delete(ex_pos)
}
return circle[0]
}
// extra
fn position(n int, kk int, p int) int {
// argument validation omitted
mut circle := []int{len: n, init: it}
k := kk-1
mut pos := p
mut ex_pos := 0
for circle.len > 1 {
ex_pos = (ex_pos + k) % circle.len
if pos == 0 {
return circle[ex_pos]
}
pos--
circle.delete(ex_pos)
}
return circle[0]
}
fn main() {
// show basic task fntion on given test case
println(final_survivor(41, 3))
// show extra fntion on all positions of given test case
println("Position Prisoner")
for i in 0..41 {
println("${i:5}${position(41, 3, i):10}")
}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<
if (k <= 0 || m <= 0 || n <= k || n <= m) Fiber.abort("One or more parameters are invalid.")
var killed = []
Line 4,165 ⟶ 4,885:
System.print("Kill order : %(sk[1])")
System.print()
}</
{{out}}
Line 4,183 ⟶ 4,903:
=={{header|XPL0}}==
<
func Prisoner(N, K); \Return final surviving prisoner
Line 4,203 ⟶ 4,923:
[IntOut(0, Prisoner(5, 2)); CrLf(0);
IntOut(0, Prisoner(41, 3)); CrLf(0);
]</
{{out}}
<pre>
Line 4,212 ⟶ 4,932:
=={{header|zkl}}==
{{trans|Julia}}
<
reg p=[0..n-1].walk().copy(), i=0, seq=L();
while(p){
Line 4,220 ⟶ 4,940:
"Prisoner killing order: %s.\nSurvivor: %d"
.fmt(seq[0,-1].concat(","),seq[-1]);
}</
{{out}}
<pre>
Line 4,228 ⟶ 4,948:
Survivor: 30
</pre>
<
reg p=[0..n-1].walk().copy(), i=0, seq=L();
while(p.len()>m){
Line 4,236 ⟶ 4,956:
"Prisoner killing order: %s.\nSurvivors: [%s]"
.fmt(seq.concat(","),p.concat(","))
}</
{{out}}
<pre>
Line 4,244 ⟶ 4,964:
Survivors: [15,30,34]
</pre>
{{omit from|GUISS}}
| |||