# Josephus problem with three inputs

There's a question on this site that is similar to this question, but I have added a twist.

You have three inputs, the number of people in the circle n, the k-th person counted out at each step, and the q-th person that survives. The people in the circle are numbered 1 to n.

For example, in a circle of 20 people, the 20th person to survive is the very first person removed, the 19th survivor is the second person removed and so on. Normally, the Josephus problem is to determine the last person removed, here called the first survivor.

Write the shortest program or function that, with those three inputs, returns the number of the q-th person to survive.

If there are any issues with clarity, please let me know.

Some examples:

>>> josephus(20, 3, 9)
4
>>> josephus(4, 3, 1)
1
>>> josephus(100, 9, 12)
46


Edit: Assume all inputs are valid. That is no one will ask for 0 or any negative numbers and no one will ask for the 20th survivor in a circle of 5 people (that is, 1 ≤ q ≤ n)

Edit: I'll accept an answer at midnight UTC+7 at the start of December 2.

• Got it. Sorry about that Nov 24, 2015 at 17:02
• For clarification, if q=1 this is exactly the same as the linked Josephus question, right? Nov 24, 2015 at 17:10
• @TimmyD Exactly Nov 24, 2015 at 17:12

# Piet, 280 273 codels Edit: I have golfed this down some more, and I think I can golf it down even further, but that is still to come. For now, I'm just glad it works, and that I had room to sign it in the bottom left-hand corner. Two ideas I have to save more codels are a) to change the end instructions be pop, push 1, add, out num (pop n, output r+1) and b) to duplicate again at the bottom left corner to save codels in stack manipulation later on in the loop.

The picture above is my code at 8 pixels per codel. In general, it's the same algorithm as my Python answer, but with the inputs in the order of k, q, n. In practice, there is a also a great deal of stack manipulation. You can try it here by opening the image there and running the code with it.

Explanation

This is a step-by-step ungolfing of the solution.

in num    get k
dup       Stack: k k
push 1
subtract  Stack: k k-1
in num    get q
dup       Stack: k k-1 q q
dup       Stack: k k-1 q q q
push 4
push 2
roll      Stack: k q q k-1 q
mod       Stack: k q q r
in num    get n
dup       Stack: k q q r n n
push 4
push 3
roll      Stack: k q r n n q
greater   1 or 0
pointer   Here the loop begins. If q>n, the pointer moves clockwise.

LOOP:     Stack: k i r n (i=q at the start of the loop)
push 4
push 2
roll      Stack: r n k i
push 1
add       Stack: r n k i=i+1
push 2
push 1
roll      Stack: r n i k
dup       Stack: r n i k k
push 5
push 4
roll      Stack: n i k k r
add       Stack: n i k m=r+k
push 3
push 2
roll      Stack: n k m i
dup       Stack: n k m i i
push 3
# here it turns the corner
push 1
roll      Stack: n k i m i
mod       Stack: n k i r=m%i
push 4
# here it turns the corner and avoids the black codels
push 1
roll      Stack: r n k i
dup       Stack: r n k i i
push 5
push 3
roll      Stack: k i i r n
dup       Stack: k i i r n n
# and we meet up with the dark green codel once more
push 4
push 3
roll      Stack: k i r n n i
greater   Stack: k i r n (0 or 1)
pointer   if else again

# else    Stack: k i r n
push 2
push 1
roll      Stack: k i n r
# and turn the corner
push 1
add       Stack: k i n r+1
out num   print r+1
# turn the corner into the end pattern (the shape with the black edges)
END

• You aren't counting empty space? Is there a meta post somewhere about how to score Piet? There probably should be. Nov 29, 2016 at 19:39
• @Sparr, I am counting empty space. That is a 21 codel by 13 codel image, so the score is 273 codels. Nov 30, 2016 at 1:10
• Ahh, I miscounted. Sorry. Nov 30, 2016 at 1:18

# Pyth, 16 bytes

eu.<PGvzh-QvwShQ


Try it online: Demonstration or Test Suite

Input is of the form k<newline>n<newline>q.

### Explanation:

eu.<PGvzh-QvwShQ   implicit: z = first input line (string)
Q = second input line (integer)
hQ   Q + 1
S     the range [1, 2, ..., Q+1]
u      h-Qvw      apply the following statement (Q-input()+1) times to G=^
PG                remove the last number of G
.<  vz              and rotate eval(z) to the left
e                  print the last number of the resulting list


# CJam, 2220 19 bytes

q~_,@a@*{m<)\}%\~=)


This reads the input as q k n. Try it online in the CJam interpreter.

### How it works

q~                   Read and evaluate all input. This pushes q, k, and n.
_,                 Push A := [0 ... n-1].
@a               Rotate on top of the stack and wrap it in an array.
@*             Rotate the original n on top and repeat [k] n times.
{    }%      For each of the n k's:
m<            Rotate A k units to the left.
)\          Pop the last element and swap it with A.
\~    Swap the resulting array with q and apply bitwise NOT.
=)  Select the corresponding element and add 1 to it.


## Golfscript, 5856553531 30 bytes

Assuming the three inputs are already in the stack, in the order n, k, q

~1$(1$%3$),@),-{\2$+\%}%\)])\;


That solution assumes I need to get rid of everything but the final answer.

### How it works

See j(n,k,q) in my Python 3 solution for more detail.

~                                   Read the inputs n, k, q
1$( Duplicate k, decrement 1$                              Duplicate q
%                             (k-1)%q
3$), Create array [0..n+1] @), Create array [0..q+1] - Subtract the second array from the first, leaving only [q+1..n+1] { }% Map the following statement onto [q+1..n+1]. The numbers from this array will be denoted i. \ Swap i and r 2$+                Duplicate k, add to r
\               Swap r and i
%              r mod i
\)          Swap the leftover array from map with r, increment
]         Put the whole stack into an array
)        Remove the last member of the array, r
\;      Pop the array, leaving only the result


Edit 1: Used @Doorknob's suggestion (Added a + to get all the inputs into the array)

Formerly,

\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)\;\;\;\;


Edit 2: Added ~, per the rules of the wiki, and shortened the code. Thanks @Dennis

Formerly,

[\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)]+)\;


Edit 3: Implemented a shorter algorithm.

Formerly,

~\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)]-1=


Edit 4: Figured out that I could use % as map.

Formerly,

~1$(1$%{1$4$<}{\)\2$+1$%}while)])\;


Edit 5: Minor edit. Changed 2$ to @ to make [0..q-1] and 3$ to 2$ to retrieve k. Saved a bite Formerly, ~1$(1$%3$),2$),-{\3$+\%}%\)])\;

• \;\;\;\; can be replaced with ])\; (wrap in array, right-uncons, swap, and pop). Nov 24, 2015 at 17:14
• Edited my code for clarity @Dennis. Nov 24, 2015 at 17:28
• Alright @Dennis. Added the ~ and edited the question to allow only programs and functions. Do you have any other suggestions? Nov 24, 2015 at 17:41
• No, all good. :) Nov 24, 2015 at 17:45

# JavaScript (ES6), 56 bytes

(n,k,q)=>{r=(k-1)%q;for(i=q;i<n;r=(r+k)%++i);return r+1}


## Ungolfed

(n,k,q)=>{
r=(k-1)%q;
for(i=q;i<n;r=(r+k)%++i);
return r+1
}


## Test

n = <input type="number" id="N" value="100" /><br />
k = <input type="number" id="K" value="9" /><br />
q = <input type="number" id="Q" value="12" /><br />
<button onclick="result.innerHTML=(

(n,k,q)=>{r=(k-1)%q;for(i=q;i<n;r=(r+k)%++i);return r+1}

)(+N.value,+K.value,+Q.value)">Go</button><br />
<pre id="result"></pre>

• I wouldn't call your ungolfed version ungolfed :P
– Nic
Apr 20, 2016 at 12:15

# Mathematica, 50 bytes

<<Combinatorica
Tr@Position[Josephus@##2,1+#2-#]&


An anonymous function. Takes inputs in the order q,n,k.

# C, 81 73 bytes

Based off @user81655's Javascript implementation of my Python answer.

Edit: Removed i

int j(int n,int k,int q){int r=(k-1)%q;for(;q<n;r=(r+k)%++q);return r+1;}


### Test

#include <stdio.h>
int j(int n,int k,int q){int r=(k-1)%q;for(;q<n;r=(r+k)%++q);return r+1;}
int main()
{
printf("%d\n", j(20,3,9));
return 0;
}

• In some versions of C, you can drop the int before the parameter names.
– Nic
Apr 20, 2016 at 12:11

## Python 3, 7266 62 bytes

A dynamic programming function in 62 bytes. Adapted from the algorithm on Wikipedia. There used to be a direct implementation of this algorithm when q=1 (i.e. i=1, r=0) on that page, but I see that has been removed now.

Edit 1: I removed i to save 4 bytes. Explanation remains unchanged.

Edit 2: Miscalculation in byte count. I was using \r\n for EOL and didn't notice when that added 3 bytes. I have lowered my byte count accordingly.

def j(n,k,q):
r=(k-1)%q
while q<n:q+=1;r=(r+k)%q
return r+1


### How this works

def j(n,k,q):
i=q;r=(k-1)%q              We start with the smallest possible circle to have a q-th
survivor, a circle of q people.
while i<n:i+=1;            Iterate from q to n
r=(r+k)%i   Every time you add people to the circle, r increases by k,
modulo the current size of the circle i.
return r+1                 Return the result.


Thanks to @Dennis for reminding me that I should explain my code (if only implicitly, because he included one in his answer). If anything is unclear, please let me know.

### Edit:

Formerly,

An iterative function that is adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer, it is faster for large n and small k.

def t(n,k,q):
m=k-1;z=q*k-m%q
while z<=n*m:z=-(-z*k//m)
return n*k-z+1

• It looks like you cut something off in copying-pasting, there's a hanging +.
– xnor
Nov 25, 2015 at 4:43

## PHP, 71 bytes

Based off of @Sherlock9's answers. See his Python answer for the algorithm.

function a($n,$k,$q){for($r=($k-1)%$q;$q<$n;$r=($r+$k)%++$q);echo$r+1;}  Alternatively, here is my original naive approach without the algorithm. This uses an array to mark which people are found. 91 bytes function a($n,$k,$q){for($r=--$i;$q<=$n;++$i%$k||$c[$r]=$q++)while($c[$r=++$r%$n]);echo$r;}


(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]


Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)


A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]


Second algorithm

jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)

• So did you pick this question to learn new languages with? 6/10 of the answers are yours :P
– user45941
Apr 19, 2016 at 10:06
• @Mego I mentioned this in chat :D I asked if I should post it anyway and they said go ahead. Also, yes. My friends have told me that this is my "Hello, World!" for new languages :D Apr 19, 2016 at 10:32
• I'm not saying this is a bad thing. I'm just amused, that's all.
– user45941
Apr 19, 2016 at 18:54
• @Sherlock9: you can use until for a (more or less) direct translation of the Python version of the 2nd algorithm: (n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q).
– nimi
Apr 20, 2016 at 15:11
• God bless you, @nimi :D I was banging my head on that problem for ages, trying foldl and infinite lists and all sorts of stuff. Thanks for your help! Apr 20, 2016 at 15:21

# GameMaker Language (GML), 88 bytes

r=argument0
k=argument1
q=argument2
r=(k-1)mod q;for(i=q;i<n;r=(r+k)mod ++i){}return r+1


# Jelly, 14 13 bytes

Rµṙ⁴ṖµL>⁵µ¿⁴ị


TryItOnline!

### How?

Rµṙ⁴ṖµL>⁵µ¿⁴ị - Main link: n, k, q
R             - range(n): [1,2,3,...,n] - the circle of people
µ   µ¿   - while
L       -     length
>      -     greater than
⁵     -     5th program argument (3rd input), i.e. q
ṙ           -         rotate left by
⁴          -         4th program argument (2nd input) i.e. k
Ṗ         -         pop - remove the rightmost person
ị - get index
⁴  - 4th program argument (2nd input), i.e. k


# Ruby, 53 48 bytes

A lambda.

->n,k,q{r=(k-1)%q;(q+=1;r=(r+k)%q)while q<n;r+1}


### How it works

def j(n,k,q)
r=(k-1)%q   # r starts at j[q,k,q]
while q<n
q+=1
r=(r+k)%q # Every time you add people to the circle, r increases by k,
# modulo the current size of the circle q.
end
r+1         # Return the result.
end
`