21
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please post your own solutions as answers instead of including them in the question. \$\endgroup\$ – Doorknob Nov 24 '15 at 17:02
  • \$\begingroup\$ Got it. Sorry about that \$\endgroup\$ – Sherlock9 Nov 24 '15 at 17:02
  • 1
    \$\begingroup\$ For clarification, if q=1 this is exactly the same as the linked Josephus question, right? \$\endgroup\$ – AdmBorkBork Nov 24 '15 at 17:10
  • \$\begingroup\$ @TimmyD Exactly \$\endgroup\$ – Sherlock9 Nov 24 '15 at 17:12

13 Answers 13

5
\$\begingroup\$

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  
\$\endgroup\$
7
\$\begingroup\$

Piet, 280 273 codels

enter image description here

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
\$\endgroup\$
  • \$\begingroup\$ You aren't counting empty space? Is there a meta post somewhere about how to score Piet? There probably should be. \$\endgroup\$ – Sparr Nov 29 '16 at 19:39
  • \$\begingroup\$ @Sparr, I am counting empty space. That is a 21 codel by 13 codel image, so the score is 273 codels. \$\endgroup\$ – Sherlock9 Nov 30 '16 at 1:10
  • \$\begingroup\$ Ahh, I miscounted. Sorry. \$\endgroup\$ – Sparr Nov 30 '16 at 1:18
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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$+\%}%\)])\;
\$\endgroup\$
  • 1
    \$\begingroup\$ \;\;\;\; can be replaced with ])\; (wrap in array, right-uncons, swap, and pop). \$\endgroup\$ – Doorknob Nov 24 '15 at 17:14
  • \$\begingroup\$ Edited my code for clarity @Dennis. \$\endgroup\$ – Sherlock9 Nov 24 '15 at 17:28
  • \$\begingroup\$ Alright @Dennis. Added the ~ and edited the question to allow only programs and functions. Do you have any other suggestions? \$\endgroup\$ – Sherlock9 Nov 24 '15 at 17:41
  • \$\begingroup\$ No, all good. :) \$\endgroup\$ – Dennis Nov 24 '15 at 17:45
2
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ I wouldn't call your ungolfed version ungolfed :P \$\endgroup\$ – Nic Hartley Apr 20 '16 at 12:15
1
\$\begingroup\$

Mathematica, 50 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ In some versions of C, you can drop the int before the parameter names. \$\endgroup\$ – Nic Hartley Apr 20 '16 at 12:11
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ It looks like you cut something off in copying-pasting, there's a hanging +. \$\endgroup\$ – xnor Nov 25 '15 at 4:43
1
\$\begingroup\$

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;}
\$\endgroup\$
1
\$\begingroup\$

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) 
\$\endgroup\$
  • \$\begingroup\$ So did you pick this question to learn new languages with? 6/10 of the answers are yours :P \$\endgroup\$ – Mego Apr 19 '16 at 10:06
  • \$\begingroup\$ @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 \$\endgroup\$ – Sherlock9 Apr 19 '16 at 10:32
  • \$\begingroup\$ I'm not saying this is a bad thing. I'm just amused, that's all. \$\endgroup\$ – Mego Apr 19 '16 at 18:54
  • \$\begingroup\$ @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). \$\endgroup\$ – nimi Apr 20 '16 at 15:11
  • \$\begingroup\$ 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! \$\endgroup\$ – Sherlock9 Apr 20 '16 at 15:21
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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