Here's a challenge inspired by Programming Praxis:


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:


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.

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

6 Answers 6


Python 2 (85 Bytes):

Thanks to bitpwner we have this solution:

def j(m,n):
    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):
    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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – Sirac
    Aug 2, 2014 at 18:58
  • \$\begingroup\$ 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)) \$\endgroup\$
    – Vectorized
    Aug 2, 2014 at 18:59
  • \$\begingroup\$ @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. \$\endgroup\$
    – Sirac
    Aug 2, 2014 at 19:12
  • \$\begingroup\$ 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. :) \$\endgroup\$
    – Emil
    Aug 2, 2014 at 19:15
  • \$\begingroup\$ @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 :). \$\endgroup\$
    – Sirac
    Aug 2, 2014 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.

->: ?!\:1
1)?!/$}1- >:


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

  • \$\begingroup\$ printing the list okay if you can't return it :) good job! \$\endgroup\$
    – xem
    Aug 4, 2014 at 6:48
  • \$\begingroup\$ Does ><> have any problem with the 'duplicate' puzzle, just returning the last person standing? \$\endgroup\$ Aug 5, 2014 at 7:01
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 5, 2014 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


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)
  • \$\begingroup\$ You can replace True by 0<1 and instead of using where make the program more than one line \$\endgroup\$ Aug 3, 2014 at 17:08
  • \$\begingroup\$ @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! \$\endgroup\$ Aug 3, 2014 at 17:30
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 3, 2014 at 17:33
  • \$\begingroup\$ 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? \$\endgroup\$ Aug 3, 2014 at 17:36
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 3, 2014 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@_}

Python 2, 96 95 bytes

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

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)

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

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