Josephus problem: Difference between revisions

{{trans|Python}}

 

V p = Array(0 .< n)

V i = 0

 

print(j(5, 2))

 

{{out}}

{{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

DEAD DS 256X n max

YREGS

{{out}}

<pre>

=={{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

JMP FIND

RETURN: TXA ; a <- index of survivor

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program josephus64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<pre>

=={{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

end loop;

end loop;

{{out}}

<pre>$ ./josephus

=={{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

printf (($"n = ", g(0), ", k = ", g(0), ", final survivor: ", g(0)l$,

n, k, josephus (n, k, 0)))

{{out}}

<pre>n = 41, k = 3, final survivor: 30</pre>

=={{header|ANSI Standard BASIC}}==

Translated from ALGOL 68

110 ! Return m-th on the reversed kill list; m=0 is final survivor.

120 LET lm = m ! Local copy OF m

200 PRINT "n =";n, "k =";k,"final survivor =";josephus(n, k, 0)

210 END

 

=={{header|AppleScript}}==

{{trans|BBC BASIC}}

 

set m to 0

repeat with i from 2 to n

end josephus

 

 

Or with an option to specify the number of survivors:

 

script o

property living : {}

 

josephus(41, 3, 1) --> {31}

 

===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

set my text item delimiters to dlm

str

{{Out}}

<pre>Josephus survivor -> 30

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* ARM assembly Raspberry PI */

/***************************************************/

.include "../affichage.inc"

<pre>

pi@raspberrypi:~/asm32/rosetta32/ass6 $ josephus 41 3

=={{header|Arturo}}==

 

p: new 0..n-1

i: 0

 

print "josephus 41 3 =>"

 

{{out}}

 

=={{header|AutoHotkey}}==

nPrisoners := 41

kth := 3

}

Until (nPrisoners = 1)

{{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 := []

}

Until (list.MaxIndex() = 1)

 

=={{header|AWK}}==

# syntax: GAWK -f JOSEPHUS_PROBLEM.AWK

# converted from PL/I

return(1)

}

{{out}}

<pre>

=={{header|BASIC}}==

Unstructured implementation: see solutions listed under specific BASIC dialects for structured versions.

20 K=3

30 M=0

50 M=INT(I*((M+K)/I-INT((M+K)/I))+0.5)

60 NEXT I

{{out}}

<pre>Survivor is number 30</pre>

==={{header|Applesoft BASIC}}===

Translated from the BASIC implementation above and the ANSI Standard BASIC.

10 DEF FN MOD(X) = X - INT (X / A) * A

20 LM = 0: INPUT "GIVE N AND K (N,K): ";N,K

40 FOR A = 1 TO N: LM = FN MOD(LM + K): NEXT A

50 PRINT "N = ";N;", K = ";K;", SURVIVOR: ";LM

{{out}}

<pre>GIVE N AND K (N,K): 41,3

 

==={{header|IS-BASIC}}===

110 INPUT PROMPT "Number of prisoners: ":NP

120 INPUT PROMPT "Execution step: ":EX

210 NEXT

220 LET JOSEPHUS=M

 

=={{header|Batch File}}==

Uses C's <code>jos()</code> function.

{{trans|C}}

setlocal enabledelayedexpansion

 

)

echo !surv_list!

{{Out}}

<pre>30

 

=={{header|BBC BASIC}}==

PRINT "Survivor is number "; FNjosephus(41, 3, 0)

END

m% = (m% + k%) MOD i%

NEXT

{{out}}

<pre>Survivor is number 30</pre>

The number of prisoners and step size are read from stdin.

 

v0p01<&_,#!>#:<"Step size: "<

>1+:20p00g`!#v_0" :rovivru"v

 

{{out}}

 

=={{header|C}}==

 

// m-th on the reversed kill list; m = 0 is final survivor

 

return 0;

{{out}}

<pre>

 

=={{header|C sharp|C#}}==

namespace Josephus

{

}

}

 

=={{header|C++}}==

#include <iostream>

#include <vector>

}

//--------------------------------------------------------------------------------------------------

{{out}}

<pre>

 

=={{header|Clojure}}==

 

(defn josephus [n k]

", an executioner moving around the"))

(println (str "circle " k " at a time will leave prisoner number "

 

{{Output}}

=={{header|Common Lisp}}==

Using a loop:

(loop for a from (1+ m) upto n do

(setf m (mod (+ m k) a)))

Using a circular list.

(let* ((list (loop for i below n

collect i))

(move-forward)

(kill-item))

{{out|Example}}

CL-USER > (kill 41 3)

=={{header|Crystal}}==

{{trans|Ruby}}

k = ARGV.fetch(1, 3).to_i # k default is 3 or ARGV[1]

 

while prisoners.size > 1; prisoners.rotate!(k-1).shift end

puts "From #{n} prisoners, eliminating each prisoner #{k} leaves prisoner #{prisoners.first}."

{{out}}

<pre>

=={{header|D}}==

{{trans|Python}}

 

T pop(T)(ref T[] items, in size_t i) pure /*nothrow*/ @safe /*@nogc*/ {

writeln;

josephus(41, 3).writeln;

{{out}}

<pre>Prisoner killing order:

 

{{trans|Javascript}}

int[][] Josephus(in int n, int k, int s=1) {

Josephus(41, 3);

Josephus(23482, 3343, 3);

{{out}}

<pre>Josephus(5,1,1) -> 2 / 1 3 0 4

=={{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)

(else (mark lst '😥 ) ;; relieved face

(kill (cdr lst ) (1- skip))))) ;; skip 1 and goto next

{{out}}

;; kill N-1

(for ((i (1- N) )) (set! last-one (kill last-one (1- K))))

🔫 33 😥 34 🔫 35 🔫 36 🔫 37 🔫 38 🔫 39 🔫 40 🔫 0 🔫 1 🔫 0 … ∞)

 

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

 

{{out}}

 

=={{header|Elixir}}==

defmodule Josephus do

def find(n,k) do

 

Josephus.find(41,3)

 

{{out}}

 

=={{header|Emacs Lisp}}==

(if (= 1 n)

1

 

(message "%d" (jo 50 2))

 

{{out}}

 

=={{header|Erlang}}==

-module( josephus_problem ).

 

kill_few( Kill, Prisoners ) ->

lists:split( Kill - 1, Prisoners ).

 

{{out}}

 

=={{header|ERRE}}==

PROGRAM JOSEPHUS

 

MAIN(41,3,3->ERRORS)

END PROGRAM

Note: Adapted from AWK version! Output is the same.

 

=={{header|Factor}}==

IN: josephus

 

:: josephus ( k n -- m )

<pre>IN: scratchpad 3 41 josephus .

30

 

=={{header|Forth}}==

<pre>josephus .

30

=={{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

print *, "Alive", p

deallocate(next)

 

=={{header|FreeBASIC}}==

Function Josephus (n As Integer, k As Integer, m As Integer) As Integer

Dim As Integer lm = m

 

Print "n ="; n, "k ="; k, "superviviente = "; Josephus(n, k, 0)

{{out}}

<pre>

 

=={{header|friendly interactive shell}}==

# If the list is empty, don't do anything.

test (count $argv) -ge 2; or return

end

 

{{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] :=

{

 

println[killingCycle[41,3]] // Enter in total number of prisoners and the number to skip each cycle

 

{{out}}

 

=={{header|Go}}==

 

import "fmt"

fmt.Printf("%5d%10d\n", i, position(41, 3, i))

}

{{out}}

<pre>

 

=={{header|Groovy}}==

// init user pool

def users = new int[size];

 

println "4 safe spots for n = 10201 and k = 17: " + Josephus(10201,17,4);

{{out}}

<pre>

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)

 

(counter (read k)) (read m)

_ -> print $ snd $ killRecursive (prisoners 41) (counter 3) 1

 

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

main = do

print $ jseq 41 3

 

=={{header|Icon}} and {{header|Unicon}}==

The following works in both languages.

 

m := integer(A[1]) | 41

c := integer(A[2]) | 3

procedure j(m,c)

return if m==1 then 0 else (j(m-1,c)+c)%m

 

{{out}}

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

n ?:= integer(tab(upto('.'))) + 1

return n

 

Sample run:

=== Tacit version ===

 

Structured derivation of the fixed tacit code

MoreThanOne=. 1 < #@]

WhileMoreThanOne=. (^:MoreThanOne f.) (^:_)

[ DropNext WhileMoreThanOne prisoners f.

 

=== Explicit version ===

NB. use: SKIP josephus NUMBER_OF_PRISONERS

N =: y

3 Josephus 41

 

 

=== Explicit version 2 ===

Josephus2 =: 4 : '(| x&+)/i. - 1+y'

 

3 Josephus2 41

 

=={{header|Java}}==

{{works with|Java|1.5+}}

 

public class Josephus {

System.out.println("Survivors: " + executeAllButM(41, 3, 3));

}

{{out}}

<pre>Prisoners executed in order:

 

{{trans|Javascript}}

import java.util.List;

 

return s.substring(1, s.length()-1) + dot;

}

{{out}}

<pre>Josephus(5,1,1) -> 2 / 1, 3, 0, 4

=={{header|JavaScript}}==

Labels are 1-based, executioner's solution:

init: function(n) {

this.head = {};

return current.label;

}

{{out}}

<pre>

 

With Array methods:

s = s | 1

for (var ps=[], i=n; i--; ) ps[i]=i

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>

 

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):

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] )

'''Examples''':

"Survivors for n=\(n), k=\(k), m=\(m): \( josephus(n;k;m) )";

 

task(41;3;1),

{{out}}

$ jq -M -r -n -f josephus.jq

 

'''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)

 

{{out}}

 

'''Iterative''':

p, i, seq = collect(0:n-1), 0, Vector{typeof(n)}(0)

while length(p) > m

 

seq, surv = josephus(41, 3, 3)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun josephus(n: Int, k: Int, m: Int): Pair<List<Int>, List<Int>> {

println()

}

 

{{out}}

=={{header|Lua}}==

Lua indexes tables starting at 1. Positions are stored from 0,n-1.

local positions={}

for i=1,n do

end

josephus(41,3, 1)

{{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.

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{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]

 

end

 

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

ReadChar

 

=={{header|Nanoquery}}==

{{trans|Python}}

p = list(range(0, n-1))

i = 0

println j(5,2)

println

 

{{out}}

{{trans|REXX}}

Hardly any changes at all...

options replace format comments java crossref symbols nobinary

 

Loop i = 0 To 40 /* look for the surviving p's */

If dead[i] = 0 Then Say i /* found one */

{{out}}

<pre>

{{trans|Python}}

 

 

proc j(n, k: int): string =

 

echo j(5,2)

{{out}}

<pre>Prisoner killing order: 1, 3, 0, 4, 2.

 

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.

 

echo "Survivor: ", prisonerPos(5, 2)

 

{{out}}

 

=={{header|Objeck}}==

function : Execute(n : Int, k : Int) ~ Int {

killIdx := 0;

}

}

 

=={{header|Oforth}}==

Oforth lists are 1-based : prisoners are numbered from 1 to n.

 

| prisoners killed i |

n seq asListBuffer ->prisoners

System.Out "Killed : " << killed << "\nSurvivor : " << prisoners << cr

;

 

{{out}}

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

result(survivor: Last-1 killed: {Reverse @Killed})

end

 

{{Out}}

 

=={{header|PARI/GP}}==

 

=={{header|Perl}}==

{{trans|Raku}}

my $k = 3;

until (@prisoner == 1) {

}

 

{{Out}}

<pre>Prisoner 30 survived.</pre>

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>

<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) --&gt; {"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>

<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>

<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===

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>

<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.

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.

<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>

<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, 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.

<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>

<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>

<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>

<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 "...".

 

=={{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

}

echo '<pre>'.print_r(Jotapata(41,3,5),true).'<pre>';

 

=={{header|PicoLisp}}==

The counting starts from one instead of zero. The last remaining person is returned.

#general solution

(de jo (N K)

(print (survivor 5 2))

(print (survivor 41 3))

{{out}}

<pre>

 

=={{header|PL/I}}==

joseph: Proc Options(main);

/* REXX **************************************************************

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

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.

function Get-JosephusPrisoners ( [int]$N, [int]$K )

{

return $Prisoners

}

# Get the prisoner order for a circle of 41 prisoners, selecting every third

$Prisoners = Get-JosephusPrisoners -N 41 -K 3

$S = 3

"Last $S remaining: " + $Prisoners[-$S..-1]

{{out}}

<pre>

=={{header|Processing}}==

Translation of Java example.

println("Survivor: " + execute(41, 3));

println("Survivors: " + executeAllButM(41, 3, 3));

println();

return prisoners;

 

=={{header|PureBasic}}==

 

Procedure f2l(List p.i())

Next

ForEver

{{out}}

<pre>Josephus problem - input prisoners : 5

 

=={{header|Python}}==

p, i, seq = list(range(n)), 0, []

while p:

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):

>>> print(josephus(41, 3))

Survivor: 30

 

===Alternate solution with a circular linked list===

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

 

josephus(41, 3)[-1]

 

===learning iter in python===

def josephus(prisoner, kill, surviver):

p = range(prisoner)

The surviver is: [2]

The kill sequence is [1, 3, 0, 4]

 

=={{header|Quackery}}==

Not the fastest method, but illustrates use of ancillary stacks, and using nests as queues.

 

 

[ stack ] is prisoners ( --> s )

survivors release

executioner-actions release

 

'''Testing in Quackery shell:'''

=={{header|R}}==

===Growing circle solution===

y <- 0:(r-1)

for (i in (r+1):n)

}

> jose(3,1,41) # r is the number of remained prisoner.

===Iterative solution===

I hope to be proven wrong, but R seems to be the wrong tool for this problem:

*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 for a few tricks for this).

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)

print(paste0("Execution order: ", paste0(dead, collapse = ", "), "."))

paste0("Survivors: ", paste0(prisoners, collapse = ", "), ".")

{{out}}

<pre>> josephusProblem(5, 2, 1)

 

=={{header|Racket}}==

(define (josephus n k (m 0))

(for/fold ((m (add1 m)))

(remainder (+ m k) a)))

 

 

=={{header|Raku}}==

{{Works with|rakudo|2015-11-12}}

Straightforward implementation of the executioner's algorithm:

until @prisoner == 1 {

@prisoner.=rotate($k - 1);

my @dalton = <Joe Jack William Averell Rantanplan>;

Execute @dalton, 2;

 

{{out}}

=={{header|REBOL}}==

Works in Rebol 2 or 3

 

execute: func [death-list [block!] kill [integer!]] [

prisoner: [] for n 0 40 1 [append prisoner n]

execute prisoner 3

{{out}}

<pre>Prisoner 30 survived</pre>

And any kind of list will do:

execute for-the-chop 2

{{out}}

<pre>William survived</pre>

=={{header|REXX}}==

===version 1===

* 15.11.2012 Walter Pachl - my own solution

* 16.11.2012 Walter Pachl generalized n prisoners + w killing distance

If dead.i=0 Then s=s i /* found one */

End

 

{{out}}

 

This solution is an &nbsp; ''executor's'' &nbsp; solution.

parse arg N K Z R . /*obtain optional arguments from the CL*/

if N=='' | N=="," then N= 41 /* men not specified? Use default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*plurals*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

n = 41

k=3

josephus = lm

return josephus

Output:

<pre>

 

=={{header|Ruby}}==

k = (ARGV[1] || 3).to_i

 

prisoners = (0...n).to_a

prisoners.rotate!(k-1).shift while prisoners.length > 1

 

=={{header|Rust}}==

const K: usize = 3;

const M: usize = 3;

println!("Executed position number {}: {}", POSITION, executed[POSITION - 1]);

println!("Survivors: {:?}", prisoners);

{{out}}

<pre>

(Prisoners labeled 0 to n-1)

 

val prisoners = ((0 until prisonerCount) map (_.toString)).toList

print( dead.mkString(" ") )

{{out}}

<pre>Prisoners executed in order:

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

writeln("Survivor: " <& executeAllButM(41, 3, 1));

writeln("Survivors: " <& executeAllButM(41, 3, 3));

 

{{out}}

=={{header|SequenceL}}==

{{trans|Python}}

josephus(n, k) := josephusHelper(n, k, 1, 0);

r when i > n

else

 

{{out}}

=={{header|Sidef}}==

Iterative:

var prisoners = @^n

while (prisoners.len > 1) {

}

return prisoners[0]

 

Recursive:

n == 1 ? 0 : ((__FUNC__(n-1, k) + k) % n)

 

Calling the function:

{{out}}

<pre>Prisoner 30 survived.</pre>

 

=={{header|Swift}}==

class func lineUp(#numberOfPeople:Int) -> [Int] {

println("Josephus is number: \(Josephus.execute(numberOfPeople: 41, spacing: 3))")

println()

{{out}}

<pre>

 

=={{header|TypeScript}}==

if (!n) {

return 1;

 

return ((josephus(n - 1, k) + k - 1) % n) + 1;

{{out}}

<pre>

 

=={{header|Tcl}}==

for {set i 0} {$i<$number} {incr i} {lappend l $i}

for {set i 1} {[llength $l]} {incr i} {

}

return [lrange $killseq end-[expr {$survivors-1}] end]

Demonstrating:

{{out}}

<pre>

 

=={{header|VBScript}}==

Function josephus(n,k,s)

Set prisoner = CreateObject("System.Collections.ArrayList")

WScript.StdOut.WriteLine josephus(41,3,1)

WScript.StdOut.WriteLine josephus(41,3,3)

 

{{Out}}

When the macro finishes, you can see the list of survivors in the edit buffer.

 

#2 = 3 // step size

#3 = 1 // number of survivors

}

if (At_EOF) { BOF }

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|D}}

 

'Determines the killing order numbering prisoners 1 to n

End Sub

 

{{out}}

<pre>Prisoner killing order: 2 4 1 5

=={{header|Vlang}}==

{{trans|Go}}

fn final_survivor(n int, kk int) int {

// argument validation omitted

}

}

 

{{out}}

=={{header|Wren}}==

{{trans|Kotlin}}

if (k <= 0 || m <= 0 || n <= k || n <= m) Fiber.abort("One or more parameters are invalid.")

var killed = []

System.print("Kill order : %(sk[1])")

System.print()

 

{{out}}

 

=={{header|XPL0}}==

 

func Prisoner(N, K); \Return final surviving prisoner

[IntOut(0, Prisoner(5, 2)); CrLf(0);

IntOut(0, Prisoner(41, 3)); CrLf(0);

{{out}}

<pre>

=={{header|zkl}}==

{{trans|Julia}}

reg p=[0..n-1].walk().copy(), i=0, seq=L();

while(p){

"Prisoner killing order: %s.\nSurvivor: %d"

.fmt(seq[0,-1].concat(","),seq[-1]);

{{out}}

<pre>

Survivor: 30

</pre>

reg p=[0..n-1].walk().copy(), i=0, seq=L();

while(p.len()>m){

"Prisoner killing order: %s.\nSurvivors: [%s]"

.fmt(seq.concat(","),p.concat(","))

{{out}}

<pre>

=={{header|ZX Spectrum Basic}}==

{{trans|ANSI Standard BASIC}}

20 GO SUB 100

30 PRINT "n= ";n;TAB (7);"k= ";k;TAB (13);"final survivor= ";lm

160 RETURN

200 DEF FN m(x,y)=x-INT (x/y)*y: REM MOD function

 

{{omit from|GUISS}}