29
\$\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 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 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\$

28 Answers 28

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\$
  • \$\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
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\$
  • \$\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
    \$\begingroup\$ If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]& \$\endgroup\$ – alephalpha May 7 '15 at 5:27
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\$
  • 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\$
  • 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\$
  • 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\$

J, 8 bytes

1&|.&.#:

       1&|.&.#: 10
    5

       1&|.&.#: 69
    11

        1&|.&.#: 123456
    115841

        1&|.&.#: 123245678901234567890x NB. x keeps input integral
    98917405212792722853

All credit to Roger Hui, co-inventor of J and all-round uber-genius
www.jsoftware.com for free j software across many platforms

Explanation
    (J works right-to-left)
     #:       convert input to binary
     &.       a&.b <=> perform b, perform a, perform reverse of b
     1&|.     rotate bitwise one bit left

So
    1&|.&.#: 10

    a. #:            convert input (10) TO binary -> 1 0 1 0
    b. 1&|.          rotate result 1 bit left -> 0 1 0 1
    c. due to the &. perform convert FROM binary -> 5 (answer)
|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Isn't it supposed to take two inputs? \$\endgroup\$ – Erik the Outgolfer Sep 28 '17 at 16:45
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\$

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.