Programming Praxis - Survive like Flavius Josephus [duplicate]

Question

Here's a challenge inspired by Programming Praxis:

http://programmingpraxis.com/2009/02/19/flavius-josephus/

Write a function josephus(n,m) that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list.

Example output:

josephus(41,3)

2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30

The function can't leak on the global scope, and must return a list or an array.

If your language can't return an array, it is allowed to just print the list.

Shortest answer (in bytes) wins.

Answer 1

Python 2 (85 Bytes):

Thanks to bitpwner we have this solution:

def j(m,n):
    a,b,c=range(m),0,[]
    while a:b=(b+n-1)%len(a);c+=[a.pop(b)]
    return c

To use this in Python 3 you have to cast a to a list, this comes with the cost of another 6 bytes.

Python 3 (114 bytes):

This was my first thought, but I think this is a good but no perfect solution:

def j(m,n):
    a,b=__import__("collections").deque(range(m)),[]
    while a:a.rotate(-n);b.append(a.pop())
    return b

I was not happy with the use of the deque, but I couldn't think of any other solution. At least I could save 5 bytes with __import__.

This function works as described above, a are the people and b is the execution order. As long as there are still people left (while a:), it rotates the deque/the people by n and appends the current man (a.pop()) to the execution list.

Answer 2

><> - 46

Really wanted to ><> a shot on this one, but unfortunately ><> has no concept of returning an array, so I simply printed it instead.

|v-1&
->: ?!\:1
>?!;ao>&:&\
^ln~\
1)?!/$}1- >:

Explanation:

|v-1& loads the second argument into the register and subtracts 1 from the first argument

->: ?!\:1 unrolls the second argument so the stack has every value between it and 0 (so 5 becomes 5, 4, 3, 2, 1, 0)

>?!;ao>&:&\ ^ln~\ has two distinct parts. &:&\ clones the value in the register onto the top of the stack, and the rest simply prints the top value on the stack, and ends the program if there's nothing left.

)?!/$}1- >: rotates the whole stack as many times as the top value, which is what we copied from the register earlier.

Answer 3

Haskell, 79 83 characters

I still think mutable state could triumph if this is reopened, but recursion holds its own for now.

Edit: Following proud haskeller's suggestions shaves off another 4 characters.

j n m=f[0..n-1][]1where f[]k _=k;f(a:b)k t|m==t=f b(k++[a])1|0<1=f(b++[a])k$t+1

Pre-suggestions:

j n m=f[][0..n-1]$1 where f k[]_=k;f k(a:b)t|m==t=f(k++[a])b 1|0<1=f k(b++[a])(t+1)

Haskell, 111 characters

First attempt:

j n m=reverse.snd.foldl f(0,[]).take(n*n).cycle$[0..n-1]where f a@(t,d)x|x`elem`d=a|t+1==m=(0,x:d)|True=(t+1,d)

Answer 4

Perl - 94 Bytes

sub j{my$a=pop;my@c=((my$i=0)..pop()-1);while(@c){push@_,splice(@c,$i=($i+$a-1)%@c,1)}return@_}

Answer 5

Python 2, 96 95 bytes

Since the obvious way to do it in Python was already taken, I had to do it recursively. :)

r=range
x=lambda o,l,m:l and x(o+l[:1],l[m:]+l[1:m],m)or o
j=lambda n,m:x([],r(m-1,n)+r(m-1),m)

Answer 6

Matlab (90)

function l=j(n,m)
a=0:n-1;l=[];j=m;for i=a;l=[l,a(j)];a(j)=[];j=mod(j+m-2,length(a))+1;end