Josephus problem: Difference between revisions
Content added Content deleted
m (→version 2: added whitespace, changed a DO label comment.) |
|||
Line 2,728: | Line 2,728: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
I managed to identify nine algorihms in use on this page, so I translated all of them. Kill ordering lists omitted for sanity.<br> |
|||
Note indexes and results are 1-based. Prisoners do not have to be numbers. Based on AWK, but replacing killed prisoners in-situ. |
|||
Unclassified: Haskell, Python[4 aka learning iter in python], REXX[version 2] (plus Befunge, J, and Mathematica, which I'm happy to ignore)<br> |
|||
<lang Phix>function Josephus(sequence prisoners, integer step, survivors) |
|||
Note all indexes and results are 1-based. For skipping/linked_list/sliding_queue, prisoners do not have to be numbers, the |
|||
integer n = length(prisoners), nn = n |
|||
same would be true for contractacycle and contractalot with the tiniest of tweaks. |
|||
integer p = 0 |
|||
=== skipping === |
|||
360 assembly, 6502 Assembly, AWK, EchoLisp, ERRE, MATLAB, NetRexx, Phix, PHP, PL/I, REXX[version 1].<br> |
|||
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) |
|||
<lang Phix>function skipping(sequence prisoners, integer step, survivors=1) |
|||
integer n = length(prisoners), nn = n, p = 0 |
|||
while n>survivors do |
while n>survivors do |
||
integer found = 0 |
integer found = 0 |
||
while found |
while found<step do |
||
p = iff(p=nn?1:p+1) |
p = iff(p=nn?1:p+1) |
||
found += prisoners[p]!=-1 |
found += prisoners[p]!=-1 |
||
end while |
end while |
||
-- (if you want a kill list, build it here!) |
|||
prisoners[p] = -1 |
prisoners[p] = -1 |
||
n -= 1 |
n -= 1 |
||
Line 2,744: | Line 2,749: | ||
return remove_all(-1,prisoners) |
return remove_all(-1,prisoners) |
||
end function |
end function |
||
--?skipping({"Joe","Jack","William","John","James"},2,1) --> {"William"}</lang> |
|||
===linked list=== |
|||
?Josephus(tagset(5),2,1) |
|||
AArch64 Assembly, Ada, ARM Assembly, Common Lisp[2, probably], Fortran, JavaScript[1] (albeit dbl-lnk), Python[3].<br> |
|||
?Josephus(tagset(41),3,1) |
|||
Method: like skipping, all prisoners stay where they are, but the executioner uses the links to speed things up a bit. |
|||
?Josephus(tagset(41),3,3) |
|||
<lang Phix>function linked_list(sequence prisoners, integer step, survivors) |
|||
?Josephus({"Joe","Jack","William","John","James"},2,1)</lang> |
|||
integer n = length(prisoners) |
|||
sequence links = tagset(n,2)&1 |
|||
integer p = n, prvp |
|||
while n>survivors do |
|||
for i=1 to step do |
|||
prvp = p |
|||
p = links[p] |
|||
end for |
|||
prisoners[p] = -1 |
|||
links[prvp] = links[p] |
|||
n -= 1 |
|||
end while |
|||
return remove_all(-1,prisoners) |
|||
end function</lang> |
|||
===sliding queue=== |
|||
Clojure, Crystal, D (both), Eiffel, Elixir, Erlang, friendly interactive shell, Go, jq, Perl, PowerShell, PureBasic (albeit one at a time), Raku, REBOL, Ruby, Scala, Sidef[1], Tcl.<br> |
|||
Method: all skipped prisoners rejoin the end of the queue which sidles left, executioner stays put until the queue gets too short. |
|||
<lang Phix>function sliding_queue(sequence prisoners, integer step, survivors) |
|||
integer n = length(prisoners) |
|||
while n>survivors do |
|||
integer k = remainder(step-1,n)+1 -- (mostly k==step) |
|||
prisoners = prisoners[k+1..$]&prisoners[1..k-1] -- rotate, dropping one. |
|||
n -= 1 |
|||
end while |
|||
return prisoners |
|||
end function</lang> |
|||
===contractacycle=== |
|||
AppleScript[2], Groovy<br> |
|||
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) |
|||
<lang Phix>function contractacycle(integer n, integer k, s) |
|||
sequence living = tagset(n) |
|||
integer startPosition = k, i, lasti |
|||
while n!=s do -- Keep going round the circle until only s prisoners remain. |
|||
integer circleSize = n |
|||
if (n < k) then |
|||
i = mod(startPosition-1,circleSize) + 1 |
|||
living = living[1..i-1]&living[i+1..$] |
|||
n -= 1 |
|||
lasti = i |
|||
else |
|||
for i=startPosition to circleSize by k do |
|||
living[i] = -1 |
|||
n -= 1 |
|||
if (n = s) then exit end if -- Not Groovy, see note |
|||
lasti = i |
|||
end for |
|||
living = remove_all(-1,living) |
|||
end if |
|||
startPosition = lasti + k - circleSize |
|||
end while |
|||
return living |
|||
end function</lang> |
|||
Groovy does not have a n=s test, it probably is entirely unnecessary. The Grovy 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=== |
|||
AutoHotkey, C#, C++, Frink, Formulae, Java (both), JavaScript[2], Julia[2], Kotlin, Lua, NanoQuery, Nim, Objeck, |
|||
Oforth, Processing, Python[1], Rust, Seed7, Swift, VBScript, Vedit, VisualBasic.NET, XPL0, zkl. <br> |
|||
Method: executioner walks round and round, queue contracts after every kill. |
|||
<lang Phix>function contractalot(integer n, integer k, s) |
|||
sequence list = tagset(n) |
|||
integer i = 1 |
|||
while n>s do |
|||
i += k - 1 |
|||
if (i > n) then i := mod(i-1, n)+1 end if |
|||
list [i..i] = {} |
|||
n -= 1 |
|||
end while |
|||
return list |
|||
end function</lang> |
|||
===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. |
|||
<lang Phix>function recursive(integer n, k) |
|||
return iff(n=1?1:1+mod(k-1+(recursive(n-1, k)),n)) |
|||
end function</lang> |
|||
===iterative=== |
|||
ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC, Batch File, C (but not ULL), Common Lisp[1], Factor, Forth, FreeBASIC, 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 functional, it can also deliver >1 survivor, one at a time. |
|||
<lang Phix>function iterative(integer n, k, m=0) |
|||
-- Return m-th on the reversed kill list; m=0 is final survivor. |
|||
for a = m+1 to n do |
|||
m = mod(m+k, a) |
|||
end for |
|||
return m + 1 -- (make result 1-based) |
|||
end function</lang> |
|||
===iterative2=== |
|||
Icon[2]<br> |
|||
Method: more iterative mod maths madness |
|||
<lang Phix>function iterative2(integer n,k,s) |
|||
integer a = k*(n-s) + 1, |
|||
olda = a |
|||
atom q = k/(k-1), |
|||
nk = n*k |
|||
while a <= nk do |
|||
olda = a |
|||
a = ceil(a*q) |
|||
end while |
|||
return nk - olda + 1 -- (make result 1-based) |
|||
end function</lang> |
|||
===test driver=== |
|||
<lang Phix>--demo/rosetta/Josephus.exw |
|||
constant show_all = true, |
|||
show_slow = true, |
|||
show_skipping = false, |
|||
show_linkedlist = false, |
|||
show_sliding_queue = false, |
|||
show_contractacycle = false, |
|||
show_contractalot = false, |
|||
show_recursive = false, |
|||
show_iterative = false, |
|||
show_iterative2 = true |
|||
constant TAGSET = #01, |
|||
ITER = #02, |
|||
ITER2 = #04, |
|||
SLOW = #08, |
|||
ONES = #10 |
|||
constant tests = {{41,3,1,false}, |
|||
{41,3,3,false}, |
|||
{5,2,1,false}, |
|||
{5,4,1,false}, |
|||
{50,2,1,false}, |
|||
{60,3,1,false}, |
|||
{23482,3343,3,true}, |
|||
{23482,3343,1,true}, |
|||
{41,3,6,false}} |
|||
procedure test(string name, integer flags) |
|||
atom t0 = time() |
|||
integer rid = routine_id(name) |
|||
for i=1 to length(tests) do |
|||
integer {prisoners, step, survivors, slow} = tests[i] |
|||
if (not and_bits(flags,ONES) or survivors=1) |
|||
and (not slow or show_slow or not and_bits(flags,SLOW)) then |
|||
sequence res |
|||
if and_bits(flags,ONES) then |
|||
-- (recursive does not take a 3rd param) |
|||
res = {rid(prisoners,step)} |
|||
elsif and_bits(flags,TAGSET) then |
|||
res = rid(tagset(prisoners),step,survivors) |
|||
elsif and_bits(flags,ITER) then |
|||
res = {} |
|||
for s=0 to survivors-1 do |
|||
res &= rid(prisoners,step,s) |
|||
end for |
|||
elsif and_bits(flags,ITER2) then |
|||
res = {} |
|||
for s=prisoners-survivors+1 to prisoners do |
|||
res &= rid(prisoners,step,s) |
|||
end for |
|||
else |
|||
res = rid(prisoners,step,survivors) |
|||
end if |
|||
printf(1,"%s(%d,%d,%d) = %v\n",{name,prisoners,step,survivors,res}) |
|||
end if |
|||
end for |
|||
?elapsed(time()-t0) |
|||
end procedure |
|||
if show_all or show_skipping then test("skipping",TAGSET+SLOW) end if |
|||
if show_all or show_linkedlist then test("linked_list",TAGSET+SLOW) end if |
|||
if show_all or show_sliding_queue then test("sliding_queue",TAGSET+SLOW) end if |
|||
if show_all or show_contractacycle then test("contractacycle",NULL) end if |
|||
if show_all or show_contractalot then test("contractalot",NULL) end if |
|||
if show_all or show_recursive then test("recursive",ONES) end if |
|||
if show_all or show_iterative then test("iterative",ITER) end if |
|||
if show_all or show_iterative2 then test("iterative2",ITER2) end if</lang> |
|||
{{out}} |
{{out}} |
||
As shown for sliding_queue, some of the result sets are in a slightly different order, sometimes, otherwise matching output replaced by "...". |
|||
<pre> |
<pre> |
||
skipping(41,3,1) = {31} |
|||
{3} |
|||
skipping(41,3,3) = {16,31,35} |
|||
{31} |
|||
skipping(5,2,1) = {3} |
|||
{16,31,35} |
|||
skipping(5,4,1) = {1} |
|||
{"William"} |
|||
skipping(50,2,1) = {37} |
|||
skipping(60,3,1) = {41} |
|||
skipping(23482,3343,3) = {1088,1336,13318} |
|||
skipping(23482,3343,1) = {1336} |
|||
skipping(41,3,6) = {2,4,16,22,31,35} |
|||
"17s" |
|||
linked_list(41,3,1) = {31}... |
|||
"0.6s" |
|||
sliding_queue(41,3,1) = {31}... |
|||
sliding_queue(23482,3343,3) = {13318,1088,1336} |
|||
sliding_queue(41,3,6) = {31,35,2,4,16,22} |
|||
"1.0s" |
|||
contractacycle(41,3,1) = {31}... |
|||
"1.5s" |
|||
contractalot(41,3,1) = {31}... |
|||
"0.9s" |
|||
recursive(41,3,1) = {31}... |
|||
"0.0s" |
|||
iterative(41,3,1) = {31}... |
|||
"0.0s" |
|||
iterative2(41,3,1) = {31}... |
|||
"0.0s" |
|||
</pre> |
</pre> |
||