Josephus problem with three inputs

Question

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.

Answer 1

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
# 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 2

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  

Answer 3

CJam, 22 20 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.

Answer 4

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 5

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'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 6

Mathematica, 50 bytes

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

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

Answer 7

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;
}

Answer 8

Python 3, 72 66 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

Answer 9

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 10

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

Answer 11

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 12

Jelly, 14 13 bytes

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

TryItOnline!

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 13

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