Programming Praxis - Survive like Flavius Josephus [duplicate]

Question

This question already has answers here:

Josephus problem (counting out) (31 answers)

Closed 11 years ago.

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.

• xem: Oops, it's similar indeed. The output is different though. This implies different code-golf tricks!
• flawr: Please reopen, it is similar but not a duplicate! This time you have to create a list which is not the same task as finding the last person.
• flawr: @ Howard, James_pic, Kyle Kanos, user80551, Ouros: Please explain why you AGAIN closed it even though it got reopened? Please leave comments!

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.

• Sirac: Let's keep my solution, but put yours on top, since it's both python. Also, I think I can help you save some bytes.
• Vectorized: Opps. For python 3, you'll need to cast the range to list. Normally, just choose the version that works the best. def j(m,n,b=0,c=[]): a=list(range(m)) while a:b=(b+n-1)%len(a);c+=[a.pop(b)] return c print(j(41,3))
• Sirac: @bitpwner I edited the post and added your solution, change the post if you like. I don't like using another's code in my answer, but I'll keep that if you're ok with that.
• Emil: I just started to write my own very straight forward Python program and without looking here before it turned out to be a nearly bit-perfect copy of @bitpwner's suggestion. Strange. :)
• Sirac: @Emil I had the same idea, but my didn't work, because I wanted to save bytes and applied the modulo in the index, not in the calculation of b. Anyway, we all had the same thoughts, but bitpwner was first :).

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.

• xem: printing the list okay if you can't return it :) good job!
• comperendinous: Does ><> have any problem with the 'duplicate' puzzle, just returning the last person standing?
• Mike Precup: Depends on what you call returning. The function paradigm in ><> is more about receiving args on the stack, and returning by leaving the result at the top of the stack, so that'd be fine. The main issue here is that you can only store numbers, there's no other type, including arrays.

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)

• proud haskeller: You can replace True by 0<1 and instead of using where make the program more than one line
• comperendinous: @proudhaskeller I'd interpreted "[t]he function can't leak on the global scope", probably over-conservatively, as meaning it had to be self-contained. I thought about how to golf True but forgot all about comparisons - D'oh!
• proud haskeller: But haskell doesn't have a global scope in that sense. I think the meaning was that the code can't assume the input was already in a certain variable.
• proud haskeller: But note that now the variable m needs to be explicitly inputted to f, as it is out of scope. Also, why is there that dollar sign on the first row?
• comperendinous: @proudhaskeller I think the $ was a remnant of an earlier idea that had composition. Of course, you're right about m too. I remember now that I had included it at one point, but "where " beats 5 " m"s. Still, thanks for helping lower the score.

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