Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by Howard, James_pic, Kyle Kanos, user80551, Ourous Aug 4 at 1:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
Oops, it's similar indeed. The output is different though. This implies different code-golf tricks! –  xem Aug 2 at 18:07
3  
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 Aug 2 at 21:44
1  
@ Howard, James_pic, Kyle Kanos, user80551, Ouros: Please explain why you AGAIN closed it even though it got reopened? Please leave comments! –  flawr Aug 4 at 13:20

6 Answers 6

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.

share|improve this answer
    
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. –  Sirac Aug 2 at 18:58
    
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)) –  bitpwner Aug 2 at 18:59
    
@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. –  Sirac Aug 2 at 19:12
    
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. :) –  Emil Aug 2 at 19:15
    
@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 :). –  Sirac Aug 2 at 19:19

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

share|improve this answer
    
printing the list okay if you can't return it :) good job! –  xem Aug 4 at 6:48
    
Does ><> have any problem with the 'duplicate' puzzle, just returning the last person standing? –  comperendinous Aug 5 at 7:01
    
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. –  Mike Precup Aug 5 at 14:18

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)
share|improve this answer
    
You can replace True by 0<1 and instead of using where make the program more than one line –  proud haskeller Aug 3 at 17:08
    
@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! –  comperendinous Aug 3 at 17:30
    
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 Aug 3 at 17:33
    
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? –  proud haskeller Aug 3 at 17:36
    
@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. –  comperendinous Aug 3 at 18:32

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@_}
share|improve this answer

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)
share|improve this answer

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
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.