30
\$\begingroup\$

The challenge

Write a function that takes two positive integers \$n\$ and \$k\$ as arguments and returns the number of the last person remaining out of \$n\$ after counting out each \$k\$-th person.

This is a code-golf challenge, so the shortest code wins.

The problem

\$n\$ people (numbered from \$1\$ to \$n\$) are standing in a circle and each \$k\$-th is counted out until a single person is remaining (see the corresponding wikipedia article). Determine the number of this last person.

E.g. for \$k=3\$ two people will be skipped and the third will be counted out. I.e. for \$n=7\$ the numbers will be counted out in the order \$3 \, 6 \, 2 \, 7 \, 5 \, 1\$ (in detail \$\require{cancel}1 \, 2 \, \cancel{3} \, 4 \, 5 \, \cancel{6} \, 7 \, 1 \, \cancel{2} \, 4 \, 5 \, \cancel{7} \, 1 \, 4 \, \cancel{5} \, 1 \, 4 \, \cancel{1} \, 4\$) and thus the answer is \$4\$.

Examples

J(7,1) = 7      // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7      // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4      // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21
Improve this question
\$\endgroup\$

30 Answers 30

Active Oldest Votes
14
\$\begingroup\$

Minsky Register Machine (25 non-halt states)

Not technically a function, but it's in a computing paradigm which doesn't have functions per se...

This is a slight variation on the main test case of my first MRM interpretation challenge: Josephus problem as Minsky register machine

Input in registers n and k; output in register r; it is assumed that r=i=t=0 on entry. The first two halt instructions are error cases.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ I think you have to adjust your machine slightly. If I read it correctly the output is zero-indexed, isn't it? \$\endgroup\$
    – Howard
    May 21 '12 at 13:45
  • \$\begingroup\$ I was thinking the other way: if k=1 then r=0. Hmm, I have to think about this one again... \$\endgroup\$
    – Howard
    May 21 '12 at 14:40
  • \$\begingroup\$ As I read your diagram, i is simply counting from 2 to n while r is the register which accumulates the result. \$\endgroup\$
    – Howard
    May 21 '12 at 15:39
  • \$\begingroup\$ @Howard, I looked up the comments I made when I first wrote this and you're right. Whoops. Now corrected (I believe - will test more thoroughly later). \$\endgroup\$
    – Peter Taylor
    May 21 '12 at 16:19
7
\$\begingroup\$

Python, 36

I also used the formula from wikipedia:

J=lambda n,k:n<2or(J(n-1,k)+k-1)%n+1

Examples:

>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Mathematica, 38 36 bytes

Same Wikipedia formula:

1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]& \$\endgroup\$
    – alephalpha
    May 7 '15 at 5:27
5
\$\begingroup\$

GolfScript, 17 bytes

{{@+\)%}+\,*)}:f;

Takes n k on the stack, and leaves the result on the stack.

Dissection

This uses the recurrence g(n,k) = (g(n-1,k) + k) % n with g(1, k) = 0 (as described in the Wikipedia article) with the recursion replaced by a fold.

{          # Function declaration
           # Stack: n k
  {        # Stack: g(i-1,k) i-1 k
    @+\)%  # Stack: g(i,k)
  }+       # Add, giving stack: n {k block}
  \,*      # Fold {k block} over [0 1 ... n-1]
  )        # Increment to move from 0-based to 1-based indexing
}:f;
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ Can you add an explanation, please? \$\endgroup\$
    – Sherlock9
    Nov 26 '15 at 18:49
  • \$\begingroup\$ @Sherlock9, I managed to figure out what I was doing despite almost 3.5 years having passed. Who says that GolfScript is read-only? ;) \$\endgroup\$
    – Peter Taylor
    Nov 26 '15 at 21:45
  • \$\begingroup\$ Ahem. s/read/write/ \$\endgroup\$
    – Peter Taylor
    Nov 26 '15 at 22:40
  • \$\begingroup\$ Sorry. I've only started learning Golfscript two or three days ago and I every time I read your code, I kept thinking I'd missed something. ... Ok, I'm still missing something, how does folding {k block} over [0..n-1] get you g(0,k) 0 k to start with? Sorry, if I'm posting these questions in the wrong place. \$\endgroup\$
    – Sherlock9
    Nov 27 '15 at 5:30
  • \$\begingroup\$ @Sherlock9, fold works pairwise, so the first thing it does is evaluate 0 1 block. Very conveniently, that happens to be g(1, k) (2-1) block. So it's starting at g(1,k) 1 rather than g(0,k) 0. Then after executing the block, it pushes the next item from the array (2) and executes the block again, etc. \$\endgroup\$
    – Peter Taylor
    Nov 27 '15 at 6:47
5
\$\begingroup\$

C, 40 chars

This is pretty much just the formula that the above-linked wikipedia article gives:

j(n,k){return n>1?(j(n-1,k)+k-1)%n+1:1;}

For variety, here's an implementation that actually runs the simulation (99 chars):

j(n,k,c,i,r){char o[999];memset(o,1,n);for(c=k,i=0;r;++i)(c-=o[i%=n])||(o[i]=!r--,c=k);
return i;}
Improve this answer
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Save a character: j(n,k){return--n?(j(n,k)+k-1)%-~n+1:1;}. \$\endgroup\$
    – ugoren
    May 20 '12 at 10:06
5
\$\begingroup\$

dc, 27 bytes

[d1-d1<glk+r%1+]dsg?1-skrxp

Uses the recurrence from the Wikipedia article. Explanation: 

# comment shows what is on the stack and any other effect the instructions have
[   # n
d   # n, n
1-  # n-1, n
d   # n-1, n-1, n
1<g # g(n-1), n ; g is executed only if n > 1, conveniently g(1) = 1
lk+ # g(n-1)+(k-1), n; remember, k register holds k-1
r%  # g(n-1)+(k-1) mod n
1+  # (g(n-1)+(k-1) mod n)+1
]
dsg # code for g; code also stored in g
?   # read user input => k, n, code for g
1-  # k-1, n, code for g
sk  # n, code for g; k-1 stored in register k
r   # code for g, n
x   # g(n)
p   # prints g(n)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

J, 45 characters

j=.[:{.@{:]([:}.]|.~<:@[|~#@])^:(<:@#)>:@i.@[

Runs the simulation.

Alternatively, using the formula (31 characters):

j=.1:`(1+[|1-~]+<:@[$:])@.(1<[)

I hope Howard doesn't mind that I've adjusted the input format slightly to suit a dyadic verb in J.

Usage:

   7 j 3
4
   123 j 12
21
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

GolfScript, 32 24 bytes

:k;0:^;(,{))^k+\%:^;}/^)

Usage: Expects the two parameters n and k to be in the stack and leaves the output value.

(thanks to Peter Taylor for suggesting an iterative approach and many other tips)

The old (recursive) approach of 32 chars:

{1$1>{1$(1$^1$(+2$%)}1if@@;;}:^;

This is my first GolfScript, so please let me know your criticisms.

Improve this answer
\$\endgroup\$
14
  • 1
    \$\begingroup\$ 1- has special opcode (. Similarly 1+ is ). You don't have to use alphabetic characters for storage, so you could use e.g. ^ instead of J and not need a space after it. You have far more $s than are usual in a well-golfed program: consider whether you can reduce them using some combination of \@.. \$\endgroup\$
    – Peter Taylor
    May 21 '12 at 7:27
  • \$\begingroup\$ @PeterTaylor Thanks a lot for these great tips! It's pretty hard to grasp all the Golfscript operators and I overlooked these two very straightforward one. Only by applying the first two suggestions I manage to shorten the code by 5 chars. I'll also try to remove the $ references. \$\endgroup\$
    – Cristian Lupascu
    May 21 '12 at 8:23
  • 1
    \$\begingroup\$ Also, recursion isn't really GolfScript's thing. Try flipping it round and doing a loop. I can get it down to 19 chars (albeit untested code) that way. Hint: unroll the function g from the Wikipedia article, and use , and /. \$\endgroup\$
    – Peter Taylor
    May 21 '12 at 9:21
  • 1
    \$\begingroup\$ {,{\2$+\)%}*)\;}:f; Make sure you understand why it works ;) \$\endgroup\$
    – Peter Taylor
    May 21 '12 at 17:12
  • 1
    \$\begingroup\$ One final trick: rather than using 2 characters to access k inside the loop and then 2 more to discard it at the end, we can pull it inside using + to get down to 17 characters: {{@+\)%}+\,*)}:f; I doubt that can be improved. \$\endgroup\$
    – Peter Taylor
    May 21 '12 at 18:13
3
\$\begingroup\$

R, 48

J=function(n,k)ifelse(n<2,1,(J(n-1,k)+k-1)%%n+1)

Running Version with examples: http://ideone.com/i7wae

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Groovy, 36 bytes

def j(n,k){n>1?(j(n-1,k)+k-1)%n+1:1}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Haskell, 68

j n=q$cycle[0..n]
q l@(i:h:_)k|h/=i=q(drop(k-1)$filter(/=i)l)k|1>0=i

Does the actual simulation. Demonstration:

GHCi> j 7 1
7
GHCi> j 7 2
7
GHCi> j 7 3
4
GHCi> j 7 11
1
GHCi> j 77 8
1
GHCi> j 123 12
21

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Scala, 53 bytes

def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C, 88 chars

Does the simulation, doesn't calculate the formula.
Much longer than the formula, but shorter than the other C simulation.

j(n,k){
    int i=0,c=k,r=n,*p=calloc(n,8);
    for(;p[i=i%n+1]||--c?1:--r?p[i]=c=k:0;);
    return i;
}

Notes:
1. Allocates memory and never releases.
2. Allocates n*8 instead of n*4, because I use p[n]. Could allocate (n+1)*4, but it's more characters.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C++, 166 bytes

Golfed:

#include<iostream>
#include <list>
int j(int n,int k){if(n>1){return(j(n-1,k)+k-1)%n+1;}else{return 1;}}
int main(){intn,k;std::cin>>n>>k;std::cout<<j(n,k);return 0;}

Ungolfed:

#include<iostream>
#include <list>
int j(int n,int k){
    if (n > 1){
        return (j(n-1,k)+k-1)%n+1;
    } else {
        return 1;
    }
}
int main()
{
    int n, k;
    std::cin>>n>>k;
    std::cout<<j(n,k);
    return 0;
}
Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ You could save bytes on the J function, by using the ternary operator. \$\endgroup\$
    – Yytsi
    Jun 26 '16 at 9:52
  • \$\begingroup\$ intn in your golfed version won't compile \$\endgroup\$
    – Felipe Nardi Batista
    Oct 24 '17 at 10:56
  • \$\begingroup\$ you can remove space in #include <list> \$\endgroup\$
    – Felipe Nardi Batista
    Oct 24 '17 at 10:56
1
\$\begingroup\$

Ruby, 39 bytes

def J(n,k)
n<2?1:(J(n-1,k)+k-1)%n+1
end

Running version with test cases: http://ideone.com/pXOUc

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Q, 34 bytes

f:{$[x=1;1;1+mod[;x]f[x-1;y]+y-1]}

Usage:

q)f .'(7 1;7 2;7 3;7 11;77 8;123 12)
7 7 4 1 1 21
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 34 bytes

J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell, 29

Using the formula from wikipedia.

1#_=1
n#k=mod((n-1)#k+k-1)n+1
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ECMAScript 5), 48 bytes

Using ECMAScript 5 since that was the latest version of JavaScript at the time this question was asked.

function f(a,b){return a<2?1:(f(a-1,b)+b-1)%a+1}

ES6 version (non-competing), 33 bytes

f=(a,b)=>a<2?1:(f(a-1,b)+b-1)%a+1

Explanation

Not much to say here. I'm just implementing the function the Wikipedia article gives me.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 11 bytes

L[Dg#²<FÀ}¦

Try it online!

L           # Range 1 .. n
 [Dg#       # Until the array has a length of 1:
     ²<F }  #   k - 1 times do:
        À   #     Rotate the array
          ¦ #   remove the first element
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

8th, 82 bytes

Code

: j >r >r a:new ( a:push ) 1 r> loop ( r@ n:+ swap n:mod ) 0 a:reduce n:1+ rdrop ;

SED (Stack Effect Diagram) is: n k -- m

Usage and explanation

The algorithm uses an array of integers like this: if people value is 5 then the array will be [1,2,3,4,5]

: j \ n k -- m
    >r                               \ save k
    >r a:new ( a:push ) 1 r> loop    \ make array[1:n]
    ( r@ n:+ swap n:mod ) 0 a:reduce \ translation of recursive formula with folding using an array with values ranging from 1 to n
    n:1+                             \ increment to move from 0-based to 1-based indexing
    rdrop                            \ clean r-stack
;

ok> 7 1 j . cr
7
ok> 7 2 j . cr
7
ok> 7 3 j . cr
4
ok> 7 11 j . cr
1
ok> 77 8 j . cr
1
ok> 123 12 j . cr
21
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

J, 24 bytes

1+1{1([:|/\+)/@,.1|.!.0#

Try it online!

An iterative approach based on the dynamic programming solution.

Explanation

1+1{1([:|/\+)/@,.1|.!.0#  Input: n (LHS), k (RHS)
                       #  Make n copies of k
                 1|.!.0   Shift left by 1 and fill with zero
    1          ,.         Interleave with 1
             /@           Reduce using
           +                Addition
        |/\                 Cumulative reduce using modulo
  1{                      Select value at index 1
1+                        Add 1
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

J, 19 bytes

1+(}:@|.^:({:@])i.)

Try it online!

How it works

1+(}:@|.^:({:@])i.)   Left: k, Right: n
                i.    Generate [0..n-1]
        ^:            Repeat:
   }:@|.                Rotate left k items, and remove the last item
          ({:@])        n-1 (tail of [0..n-1]) times
1+                    Add one to make the result one-based
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Dart, 33 bytes

f(n,k)=>n<2?1:(f(n-1,k)+k-1)%n+1;

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Japt, 15 bytes

_é1-V Å}h[Uõ] Ì

Try it online!

A byte could be saved by 0-indexing k, but it isn't actually an index so I decided against that.

Explanation:

         [Uõ]      :Starting with the array [1...n]
_      }h          :Repeat n-1 times:
 é1-V              : Rotate the array right 1-k times (i.e. rotate left k-1 times)
      Å            : Remove the new first element
              Ì    :Get the last value remaining
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Japt -h, 10 bytes

õ
£=éVn1¹v

Try it

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Powershell, 56 bytes

param($n,$k)if($n-lt2){1}else{((.\f($n-1)$k)+$k-1)%$n+1}

Important! The script calls itself recursively. So save the script as f.ps1 file in the current directory. Also you can call a script block variable instead script file (see the test script below). That calls has same length.

Test script:

$f = {

param($n,$k)if($n-lt2){1}else{((&$f($n-1)$k)+$k-1)%$n+1}

}

@(
    ,(7, 1, 7)
    ,(7, 2, 7)
    ,(7, 3, 4)
    ,(7, 11, 1)
    ,(77, 8, 1)
    ,(123,12, 21)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$($result-eq$expected): $result"
}

Output:

True: 7
True: 7
True: 4
True: 1
True: 1
True: 21
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 17 bytes

{¯1↓⍺⌽⍵}⍣{1=≢⍺}∘⍳

Try it online!

Takes input as k f n.

Explanation

{¯1↓⍺⌽⍵}⍣{2=≢⍵}∘⍳
               ∘⍳ list from 1..n
        ⍣         (f⍣g) → apply f repeatedly till g is true
{¯1↓⍺⌽⍵}          f: rotate list through k elements, drop last
         {1=≢⍺}   g: is the length = 1, for the previous iteration?

APL (Dyalog Unicode), 36 bytes

1+{⍺>1:⍺|⍵+⍵∇⍨⍺-1⋄0}

Try it online!

Recursive function.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Jelly, 7 bytes

RṙṖ¥ƬṖṪ

Try it online!

How it works

RṙṖ¥ƬṖṪ - Main link. Takes n on the left and k on the right
R       - Range; Yield [1, 2, ..., n]
   ¥Ƭ   - Do the following to a fixed point and collect intermediate steps:
 ṙ      -   Rotate k steps to the left
  Ṗ     -   Remove the last element
     Ṗ  - Remove the empty list (the fixed point)
      Ṫ - Return the single element left over
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Husk, 11 8 bytes

Ωεȯtṙ←⁰ḣ

Try it online!

Algorithm from Kamil Drakari's answer.

Improve this answer
\$\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.