Josephus problem: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,849:
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>-->
<lang Phix>function skipping(sequence prisoners, integer step, survivors=1)
<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>
integer n = length(prisoners), nn = n, p = 0
<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>
while n>survivors do
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">survivors</span> <span style="color: #008080;">do</span>
integer found = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
while found<step do
<span style="color: #008080;">while</span> <span style="color: #000000;">found</span><span style="color: #0000FF;"><</span><span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
p = iff(p=nn?1:p+1)
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
found += prisoners[p]!=-1
<span style="color: #000000;">found</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">prisoners</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]!=-</span><span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
prisoners[p] = -1
<span style="color: #000000;">prisoners</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return remove_all(-1,prisoners)
<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>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
--?skipping({"Joe","Jack","William","John","James"},2,1) --> {"William"}</lang>
<span style="color: #000080;font-style:italic;">--?skipping({"Joe","Jack","William","John","James"},2,1) --&gt; {"William"}</span>
<!--</lang>-->
 
===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.
<!--<lang Phix>-->
<lang Phix>function linked_list(sequence prisoners, integer step, survivors)
<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>
integer n = length(prisoners)
<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>
sequence links = tagset(n,2)&1
<span style="color: #004080;">sequence</span> <span style="color: #000000;">links</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><span style="color: #000000;">2</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">1</span>
integer p = n, prvp
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">prvp</span>
while n>survivors do
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">survivors</span> <span style="color: #008080;">do</span>
for i=1 to step do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
prvp = p
<span style="color: #000000;">prvp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
p = links[p]
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
prisoners[p] = -1
<span style="color: #000000;">prisoners</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
links[prvp] = links[p]
<span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prvp</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return remove_all(-1,prisoners)
<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>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</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>-->
<lang Phix>function sliding_queue(sequence prisoners, integer step, survivors)
<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>
integer n = length(prisoners)
<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>
while n>survivors do
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">survivors</span> <span style="color: #008080;">do</span>
integer k = remainder(step-1,n)+1 -- (mostly k==step)
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">step</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</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: #000080;font-style:italic;">-- (mostly k==step)</span>
prisoners = prisoners[k+1..$]&prisoners[1..k-1] -- rotate, dropping one.
<span style="color: #000000;">prisoners</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prisoners</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;">prisoners</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;">1</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- rotate, dropping one.</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return prisoners
<span style="color: #008080;">return</span> <span style="color: #000000;">prisoners</span>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
 
===contractacycle===
Line 2,900 ⟶ 2,906:
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>-->
<lang Phix>function contractacycle(integer n, integer k, s)
<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>
sequence living = tagset(n)
<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>
integer startPosition = k, i, lasti
<span style="color: #004080;">integer</span> <span style="color: #000000;">startPosition</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lasti</span>
while n!=s do -- Keep going round the circle until only s prisoners remain.
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">s</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- Keep going round the circle until only s prisoners remain.</span>
integer circleSize = n
<span style="color: #004080;">integer</span> <span style="color: #000000;">circleSize</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
if (n < k) then
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</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;">then</span>
i = mod(startPosition-1,circleSize) + 1
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">startPosition</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">circleSize</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
living = living[1..i-1]&living[i+1..$]
<span style="color: #000000;">living</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">living</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">living</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
lasti = i
<span style="color: #000000;">lasti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
else
<span style="color: #008080;">else</span>
for i=startPosition to circleSize by k do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">startPosition</span> <span style="color: #008080;">to</span> <span style="color: #000000;">circleSize</span> <span style="color: #008080;">by</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
living[i] = -1
<span style="color: #000000;">living</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
if (n = s) then exit end if -- Not Groovy, see note
<span style="color: #008080;">if</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: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- Not Groovy, see note</span>
lasti = i
<span style="color: #000000;">lasti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
living = remove_all(-1,living)
<span style="color: #000000;">living</span> <span style="color: #0000FF;">=</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;">living</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
startPosition = lasti + k - circleSize
<span style="color: #000000;">startPosition</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lasti</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">circleSize</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return living
<span style="color: #008080;">return</span> <span style="color: #000000;">living</span>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
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.
Line 2,930 ⟶ 2,938:
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.
<!--<lang Phix>-->
<lang Phix>function contractalot(integer n, integer k, s)
<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>
sequence list = tagset(n)
<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>
integer i = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
while n>s do
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">s</span> <span style="color: #008080;">do</span>
i += k - 1
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span>
if (i > n) then i := mod(i-1, n)+1 end if
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</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: #008080;">end</span> <span style="color: #008080;">if</span>
list [i..i] = {}
<span style="color: #000000;">list</span> <span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
n -= 1
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return list
<span style="color: #008080;">return</span> <span style="color: #000000;">list</span>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</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) -->
<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>
return iff(n=1?1:1+mod(k-1+(recursive(n-1, k)),n))
<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>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</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 recursive, it can also deliver >1 survivor, one at a time.
<!--<lang Phix>function iterative(integer n, k, m=0)-->
<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>
-- Return m-th on the reversed kill list; m=0 is final survivor.
<span style="color: #000080;font-style:italic;">-- Return m-th on the reversed kill list; m=0 is final survivor.</span>
for a = m+1 to n do
<span style="color: #008080;">for</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
m = mod(m+k, a)
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return m + 1 -- (make result 1-based)
<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>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
 
===iterative2===
Icon[2]<br>
Method: more iterative maths madness
<!--<lang Phix>function iterative2(integer n,k,s)-->
<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>
integer a = k*(n-s) + 1,
<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>
olda = a
<span style="color: #000000;">olda</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
atom q = k/(k-1),
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</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>
nk = n*k
<span style="color: #000000;">nk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span>
while a <= nk do
<span style="color: #008080;">while</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">nk</span> <span style="color: #008080;">do</span>
olda = a
<span style="color: #000000;">olda</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
a = ceil(a*q)
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return nk - olda + 1 -- (make result 1-based)
<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>
end function</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</lang>-->
 
===test driver===
<!--<lang Phix>(phixonline)--demo/rosetta/Josephus.exw>
<span style="color: #000080;font-style:italic;">--demo/rosetta/Josephus.exw</span>
constant show_all = true,
<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>
show_slow = true,
<span style="color: #000000;">show_slow</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_skipping = false,
<span style="color: #000000;">show_skipping</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_linkedlist = false,
<span style="color: #000000;">show_linkedlist</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_sliding_queue = false,
<span style="color: #000000;">show_sliding_queue</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_contractacycle = false,
<span style="color: #000000;">show_contractacycle</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_contractalot = false,
<span style="color: #000000;">show_contractalot</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_recursive = false,
<span style="color: #000000;">show_recursive</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_iterative = false,
<span style="color: #000000;">show_iterative</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
show_iterative2 = true
<span style="color: #000000;">show_iterative2</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
 
constant TAGSET = #01,
<span style="color: #008080;">constant</span> <span style="color: #000000;">TAGSET</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#01</span><span style="color: #0000FF;">,</span>
ITER = #02,
<span style="color: #000000;">ITER</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#02</span><span style="color: #0000FF;">,</span>
ITER2 = #04,
<span style="color: #000000;">ITER2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#04</span><span style="color: #0000FF;">,</span>
SLOW = #08,
<span style="color: #000000;">SLOW</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#08</span><span style="color: #0000FF;">,</span>
ONES = #10
<span style="color: #000000;">ONES</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#10</span>
 
constant tests = {{41,3,1,false},
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">41</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{41,3,3,false},
<span style="color: #0000FF;">{</span><span style="color: #000000;">41</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{5,2,1,false},
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{5,4,1,false},
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{50,2,1,false},
<span style="color: #0000FF;">{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{60,3,1,false},
<span style="color: #0000FF;">{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">},</span>
{23482,3343,3,true},
<span style="color: #0000FF;">{</span><span style="color: #000000;">23482</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3343</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">},</span>
{23482,3343,1,true},
<span style="color: #0000FF;">{</span><span style="color: #000000;">23482</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3343</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">},</span>
{41,3,6,false}}
<span style="color: #0000FF;">{</span><span style="color: #000000;">41</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}}</span>
 
procedure test(string name, integer flags)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">flags</span><span style="color: #0000FF;">)</span>
atom t0 = time()
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
integer rid = routine_id(name)
<span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #000000;">name</span><span style="color: #0000FF;">)</span>
for i=1 to length(tests) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer {prisoners, step, survivors, slow} = tests[i]
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</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;">slow</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
if (not and_bits(flags,ONES) or survivors=1)
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #008080;">not</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #000000;">survivors</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
and (not slow or show_slow or not and_bits(flags,SLOW)) then
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #008080;">not</span> <span style="color: #000000;">slow</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_slow</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">SLOW</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
sequence res
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span>
if and_bits(flags,ONES) then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
-- (recursive does not take a 3rd param)
<span style="color: #000080;font-style:italic;">-- (recursive does not take a 3rd param)</span>
res = {rid(prisoners,step)}
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">)}</span>
elsif and_bits(flags,TAGSET) then
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">TAGSET</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
res = rid(tagset(prisoners),step,survivors)
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">),</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">survivors</span><span style="color: #0000FF;">)</span>
elsif and_bits(flags,ITER) then
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ITER</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
res = {}
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for s=0 to survivors-1 do
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">survivors</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
res &= rid(prisoners,step,s)
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
elsif and_bits(flags,ITER2) then
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flags</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ITER2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
res = {}
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for s=prisoners-survivors+1 to prisoners do
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">prisoners</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: #008080;">to</span> <span style="color: #000000;">prisoners</span> <span style="color: #008080;">do</span>
res &= rid(prisoners,step,s)
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
else
<span res style="color: rid(prisoners,step,survivors)#008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">survivors</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1,"%s(%d,%d,%d) = %v\n",{name,prisoners,step,survivors,res})
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s(%d,%d,%d) = %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prisoners</span><span style="color: #0000FF;">,</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;">res</span><span style="color: #0000FF;">})</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?elapsed(time()-t0)
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
if show_all or show_skipping then test("skipping",TAGSET+SLOW) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_skipping</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"skipping"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">TAGSET</span><span style="color: #0000FF;">+</span><span style="color: #000000;">SLOW</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_linkedlist then test("linked_list",TAGSET+SLOW) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_linkedlist</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"linked_list"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">TAGSET</span><span style="color: #0000FF;">+</span><span style="color: #000000;">SLOW</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_sliding_queue then test("sliding_queue",TAGSET+SLOW) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_sliding_queue</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"sliding_queue"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">TAGSET</span><span style="color: #0000FF;">+</span><span style="color: #000000;">SLOW</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_contractacycle then test("contractacycle",NULL) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_contractacycle</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"contractacycle"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">SLOW</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_contractalot then test("contractalot",NULL) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_contractalot</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"contractalot"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_recursive then test("recursive",ONES) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">show_all</span> <span style="color: #008080;">or</span> <span style="color: #000000;">show_recursive</span> <span style="color: #008080;">then</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"recursive"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if show_all or show_iterative then test("iterative",ITER) end if
<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>
if show_all or show_iterative2 then test("iterative2",ITER2) end if</lang>
<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>
<!--</lang>-->
{{out}}
As shown for sliding_queue, some of the result sets are in a slightly different order, sometimes, otherwise matching output replaced by "...".
Retrieved from "https://rosettacode.org/wiki/Josephus_problem"