[Question]
  [
[There's a question on this site](https://codegolf.stackexchange.com/questions/5891/josephus-problem-counting-out "There's a question on this site that is similar to this one") 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.
  
[Answer]
# Piet, ~~280~~ 273 codels
[![enter image description here](https://i.stack.imgur.com/0CTFk.png)](https://i.stack.imgur.com/0CTFk.png)
**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](http://www.rapapaing.com/blog/?page_id=6) 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
# note: the loop will return to the following codel
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.
          Else, it points straight ahead
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
```
[Answer]
# Pyth, 16 bytes
```
eu.<PGvzh-QvwShQ
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?test_suite=0&input=3%0A20%0A9&input_size=3&code=eu.%3CPGvzh-QvwShQ&test_suite_input=3%0A20%0A9%0A3%0A4%0A1%0A9%0A100%0A12) or [Test Suite](http://pyth.herokuapp.com/?test_suite=1&input=3%0A20%0A9&input_size=3&code=eu.%3CPGvzh-QvwShQ&test_suite_input=3%0A20%0A9%0A3%0A4%0A1%0A9%0A100%0A12)
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  
```
[Answer]
# CJam, ~~22~~ ~~20~~ 19 bytes
```
q~_,@a@*{m<)\}%\~=)
```
This reads the input as `q k n`. Try it online in the [CJam interpreter](http://cjam.aditsu.net/#code=q~_%2C%40a%40*%7Bm%3C)%5C%7D%25%5C~%3D)&input=1%203%207).
### 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.
```
[Answer]
# JavaScript (ES6), 56 bytes
```
(n,k,q)=>{r=(k-1)%q;for(i=q;i<n;r=(r+k)%++i);return r+1}
```
## Ungolfed
Basically a JavaScript adaptation of [@Sherlock9](https://codegolf.stackexchange.com/users/47581/sherlock9)'s Python answer.
```
(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>
```
[Answer]
## Golfscript, ~~58~~ ~~56~~ ~~55~~ ~~35~~ ~~31~~ 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$+\%}%\)])\;
```
[Answer]
# C, ~~81~~ 73 bytes
Based off [@user81655](https://codegolf.stackexchange.com/users/46855/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;
}
```
[Answer]
## Python 3, ~~72~~ ~~66~~ 62 bytes
A dynamic programming function in 62 bytes. Adapted from [the algorithm on Wikipedia.](https://en.wikipedia.org/wiki/Josephus_problem) 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
```
[Answer]
# Mathematica, 50 bytes
```
<<Combinatorica`
Tr@Position[Josephus@##2,1+#2-#]&
```
An anonymous function. Takes inputs in the order `q,n,k`.
[Answer]
## 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;}
```
[Answer]
# Haskell, ~~48~~ ~~47~~ 43 bytes
```
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
```
Based on a Haskell algorithm on [the Rosetta Code page](http://rosettacode.org/wiki/Josephus_problem#Haskell) of the Josephus function with two inputs. Golfing suggestions are welcome.
**Edit:** My thanks to [nimi](https://codegolf.stackexchange.com/users/34531/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](https://codegolf.stackexchange.com/a/64668/47581) 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) 
```
[Answer]
# GameMaker Language (GML), 88 bytes
Based on @user81655's answer
```
r=argument0
k=argument1
q=argument2
r=(k-1)mod q;for(i=q;i<n;r=(r+k)mod ++i){}return r+1
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~14~~ 13 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Rµṙ⁴ṖµL>⁵µ¿⁴ị
```
**[TryItOnline!](http://jelly.tryitonline.net/#code=UsK14bmZ4oG04bmWwrVMPuKBtcK1wr_igbThu4s&input=&args=MTAw+OQ+MTI)**
### How?
```
Rµṙ⁴ṖµL>⁵µ¿⁴ị - Main link: n, k, q
 µ            - monadic chain separation
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
```
[Answer]
# 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
```
]