Le défi

Écrivez une fonction qui prend deux entiers positifs n et k comme arguments et retourne le numéro de la dernière personne restante sur n après avoir compté chaque k -ième personne.

C'est un défi de code-golf, donc le code le plus court l'emporte.

Le problème

n personnes (numérotées de 1 à n ) sont debout dans un cercle et chaque k - ième est compté jusqu'à ce qu'une seule personne est disponible (voir le correspondant article wikipedia ). Déterminez le nombre de cette dernière personne.

Par exemple, pour k = 3, deux personnes seront ignorées et la troisième sera décomptée. C'est-à-dire que pour n = 7, les nombres seront comptés dans l'ordre 3 6 2 7 5 1 (en détail 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 ) et donc la réponse est 4 .

Exemples

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

GolfScript, 17 octets

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

Prend n kla pile et laisse le résultat sur la pile.

Dissection

Cela utilise la récurrence g(n,k) = (g(n-1,k) + k) % navec g(1, k) = 0(comme décrit dans l'article Wikipedia) avec la récursivité remplacée par un pli.

{          # 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;

Minsky Register Machine (25 états sans interruption)

Pas techniquement une fonction, mais c'est dans un paradigme informatique qui n'a pas de fonctions en soi ...

Il s'agit d'une légère variation par rapport au scénario de test principal de mon premier défi d'interprétation MRM :

Entrée dans les registres net k; sortie dans le registre r; on suppose que r=i=t=0lors de l'entrée. Les deux premières instructions d'arrêt sont des cas d'erreur.

Python, 36

J'ai également utilisé la formule de wikipedia:

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

Exemples:

>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21

Mathematica, 38 36 octets

Même formule Wikipédia:

1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]

C, 40 caractères

C'est à peu près la formule que l'article wikipedia lié ci-dessus donne:

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

Pour plus de variété, voici une implémentation qui exécute réellement la simulation (99 caractères):

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

dc, 27 octets

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

Utilise la récurrence de l'article Wikipedia. Explication:

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

J, 45 caractères

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

Exécute la simulation.

Alternativement, en utilisant la formule (31 caractères):

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

J'espère que cela ne dérange pas Howard d'avoir ajusté légèrement le format d'entrée pour l'adapter à un verbe dyadique en J.

Usage:

   7 j 3
4
   123 j 12
21

GolfScript, 32 24 octets

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

Utilisation: attend les deux paramètres n et k dans la pile et laisse la valeur de sortie.

(merci à Peter Taylor d'avoir suggéré une approche itérative et de nombreux autres conseils)

L'ancienne approche (récursive) de 32 caractères:

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

Ceci est mon premier GolfScript, alors faites-moi part de vos critiques.

R, 48

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

Version en cours d'exécution avec des exemples: http://ideone.com/i7wae

Groovy, 36 octets

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

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

Fait la simulation réelle. Manifestation:

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

Scala, 53 octets

def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1

C, 88 caractères

Fait la simulation, ne calcule pas la formule.
Beaucoup plus longue que la formule, mais plus courte que l'autre simulation C.

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

Remarques:
1. Alloue de la mémoire et ne libère jamais.
2. Alloue n*8au lieu de n*4, car j'utilise p[n]. Pourrait allouer (n+1)*4, mais c'est plus de caractères.

C ++, 166 octets

Golfé:

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

Non golfé:

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

J, 8 octets

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)

Rubis, 39 octets

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

Version en cours d'exécution avec cas de test: http://ideone.com/pXOUc

Q, 34 octets

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

Rubis, 34 octets

J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}

Haskell, 29

En utilisant la formule de wikipedia.

1#_=1
n#k=mod((n-1)#k+k-1)n+1

JavaScript (ECMAScript 5), 48 octets

Utilisation d'ECMAScript 5 car il s'agissait de la dernière version de JavaScript au moment où cette question a été posée.

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

Version ES6 (non concurrente), 33 octets

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

Explication

Pas grand chose à dire ici. J'implémente juste la fonction que l'article Wikipedia me donne.

05AB1E , 11 octets

L[Dg#²<FÀ}¦

Essayez-le en ligne!

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

8ème , 82 octets

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) est:n k -- m

Utilisation et explication

L'algorithme utilise un tableau d'entiers comme celui-ci: si la valeur des personnes est 5 alors le tableau sera [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

J , 24 octets

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

Essayez-le en ligne!

Une approche itérative basée sur la solution de programmation dynamique.

Explication

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

J , 19 octets

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

Essayez-le en ligne!

Comment ça marche

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

Fléchette , 33 octets

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

Essayez-le en ligne!

Japt , 15 octets

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

Essayez-le en ligne!

Un octet pourrait être enregistré par l' indexation 0 k , mais ce n'est pas un index, j'ai donc décidé de ne pas le faire.

Explication:

         [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

Japt -h, 10 octets

õ
£=éVn1¹v

Essayez-le

Powershell, 56 octets

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

Important! Le script s'appelle récursivement. Enregistrez donc le script en tant que f.ps1fichier dans le répertoire courant. Vous pouvez également appeler une variable de bloc de script à la place d'un fichier de script (voir le script de test ci-dessous). Ces appels ont la même durée.

Script de test:

$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"
}

Sortie:

True: 7
True: 7
True: 4
True: 1
True: 1
True: 21