Test de divisibilité impatiente

Votre tâche consiste à écrire un programme ou une fonction qui détermine si un nombre est divisible par un autre. Le hic, c'est qu'il devrait donner une réponse dès que possible , même si tous les chiffres du numéro n'ont pas été donnés.

Votre programme doit prendre un entier D ≥ 2 puis une série de chiffres en entrée. Ceux-ci représentent les chiffres d'un autre entier N ≥ 1, en commençant par le chiffre le moins significatif. Au premier point que N soit doit ou ne doit pas être divisble par D , votre programme doit générer la réponse appropriée et la sortie. Si la fin de l'entrée est atteinte, il se doit de sortie si la totalité N est divisible par D .

Voici une liste des formats d'entrée acceptables pour N (laissez un commentaire si vous pensez que quelque chose qui n'est pas inclus devrait être autorisé):

Entrée standard : les chiffres sont indiqués sur des lignes distinctes; la fin de l'entrée est EOF ou une valeur spéciale; exit signifie que la fonction revient ou que le programme se ferme.
Entrée analogique : par exemple, par touches ou dix boutons représentant chaque chiffre; la fin de l'entrée est une valeur spéciale; exit signifie que la fonction revient ou que le programme se ferme.
Fonction avec état global : appelée à plusieurs reprises avec des chiffres successifs; la fin de l'entrée est une valeur spéciale; exit signifie que la fonction renvoie une valeur non nulle. Notez que si vous utilisez l'état global, il doit être effacé après qu'une valeur est retournée ou autrement réinitialisé de sorte que la fonction fonctionne plusieurs fois .
Fonction curry : renvoie soit une autre fonction à appeler avec le chiffre suivant, soit une valeur; la fin de l'entrée est une valeur spéciale ou l'appel de la fonction sans argument; exit signifie que la fonction renvoie une réponse plutôt qu'une autre fonction.
Invite GUI ou similaire : affiché à plusieurs reprises; la fin de l'entrée est "annuler" ou équivalent, ou une valeur spéciale; exit signifie que les invites cessent d'apparaître.
Fonction d'itérateur : l'entrée est un objet ou une fonction avec état qui renvoie le chiffre suivant lorsqu'il est appelé, la fin de l'entrée est une exception ou une valeur spéciale; exit signifie que l'itérateur cesse d'être appelé.

L'entrée pour D et la sortie peuvent se faire par n'importe quelle méthode standard acceptable .

Cas de test:

2;   6               => true
5;   6               => false
20;  0 3             => false
20;  0 4             => true
100; 1               => false
100; 0 0             => true
100; 0 2             => false
4;   2 4             => false
4;   2 5             => true
4;   2 [eof]         => false
4;   4 [eof]         => true
625; 5 5             => false
625; 5 7 2           => false
625; 5 7 3 6         => false
625; 5 7 3 4         => true
7;   9 3 4 [eof]     => false
7;   9 3 4 5 [eof]   => true
140; 0 3             => false
140; 0 4 5 [eof]     => false
140; 0 4 5 1 [eof]   => true
14;  4 5 1 4 [eof]   => false
14;  4 5 1 4 1 [eof] => true

code-golf number decision-problem number-theory division Poignée de porte
la source

Je pense que nous devrions supposer qu'un chiffre sera donné à chaque fois que notre solution demandera une contribution, non? Et, ce devrait être un programme complet, car c'est le moyen objectif de s'assurer que l'entrée est donnée chiffre par chiffre, non? (Le défi dit "programme ou fonction", hmm ...)

Erik the Outgolfer

@EriktheOutgolfer Le format d'entrée est expliqué en détail dans la liste à puces de la question.

Poignée de porte

Je pensais juste à quel point ces formats peuvent être objectifs ... Je suppose que je vais juste arrêter de taquiner et commencer à résoudre ce problème . :-)

Erik the Outgolfer

Y a-t-il quelque chose de mal à simplement prendre une liste comme digitsentrée avec une valeur spéciale pour EOF?

Jonathan Allan

@EriktheOutgolfer pas s'il y a une valeur EOF, sauf si j'ai mal compris quelque chose. Par exemple , disons que la valeur entière est 132 et le diviseur potentiel est alors 4 []et [2]quoi que ce soit de retour autre que falseou true(y compris la fonction elle - même , etc ...) tout [2,3], [2,3,1]et [2,3,1,EOF]retour true. Cela me semble aussi proche de l'option de l'État mondial.

Jonathan Allan

Réponses:

JavaScript (ES6), 70 octets

Format d'entrée: fonction Curry

$-1$ $0$ $1$

p=>(q='',g=(d,t=k=z=!~d||(q=d+q,p))=>k--?g(d,t-=(k+q)%p<1):t?t-z&&g:1)

Essayez-le en ligne!

Comment?

$p$ $q$ $n$ $0 \le k < p$

\begin{matrix} (1) & k \times {dix}^{n} + q (\mod p) \end{matrix}

$k\times 10^n+q \pmod p\tag{1}$

$x\ge p$ $m\ge 1$ $0 \le k < p$ $x=mp+k$

X \times {dix}^{n} + q (\mod p) = (m p + k) \times {dix}^{n} + q (\mod p) = (m p \times {dix}^{n} (\mod p)) + (k \times {dix}^{n} + q (\mod p)) (\mod p) = 0 + (k \times {dix}^{n} + q (\mod p)) (\mod p) = k \times {dix}^{n} + q (\mod p)

$x\times 10^n+q \pmod p=\\ (mp+k)\times 10^n+q \pmod p=\\ (mp\times 10^n \pmod p)+ (k\times 10^n+q \pmod p)\pmod p=\\ 0+(k\times 10^n+q \pmod p)\pmod p=\\ k\times 10^n+q \pmod p$

$(1)$ $0$ $0 \le k < p$ $0$ $k \ge p$

$(1)$ $0$ $0 \le k < p$

$(1)$ $q$

Commenté

p => (                       // p = divisor
  q = '',                    // q = dividend stored as a string, initially empty
  g = (                      // g() = curried function taking:
    d,                       //   d = next digit
    t =                      //   t = number of iterations yielding a non-zero value
    k =                      //   k = total number of iterations to process
    z =                      //   z = copy of k
      !~d ||                 //   if d == -1 (meaning EOF), use only 1 iteration
                             //   so that we simply test the current value of q
      (q = d + q, p)         //   otherwise, prepend d to q and use p iterations
  ) =>                       //
    k-- ?                    //   decrement k; if it was not equal to zero:
      g(                     //     do a recursive call to g():
        d,                   //       pass the current value of d (will be ignored anyway)
        t -= (k + q) % p < 1 //       test (k + q) % p and update t accordingly
      )                      //     end of recursive call
    :                        //   else:
      t ?                    //     if t is greater than 0:
        t - z && g           //       return 0 if t == z, or g otherwise
      :                      //     else:
        1                    //       return 1
)                            //

Arnauld
la source

Lot, 177 169 octets

@set n=
@set g=1
:l
@set/ps=
@if %s%==- goto g
@set n=%s%%n%
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g
@if %g% neq %1 if %r%==0 goto l
:g
@cmd/cset/a!(n%%%1)

Prend dcomme paramètre de ligne de commande et lit les chiffres de nsur des lignes séparées avec -comme marqueur EOF. Sorties 1pour divisible, 0sinon. Explication:

@set n=

Initialisez nà la chaîne vide.

@set g=1

g est gcd(d, 10**len(n))

:l

Commencez une lecture en boucle des chiffres.

@set/ps=

Lisez le chiffre suivant.

@if %s%==- goto g

Arrêtez le traitement à l'EOF.

@set n=%s%%n%

Ajoutez le chiffre suivant à n.

@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g

Mise à jour g maintenant ce qui len(n)a augmenté et calculer n%g.

@if %g% neq %1 if %r%==0 goto l

Si rest différent de zéro, alors le dne se divise certainement pas n, car g, un facteur de d, ne le fait pas. Si rest nul alors nous savons seulement sid divise nsi gégal d, donc si ce n'est pas le cas, continuez la boucle.

:g

Sortez de la boucle de lecture des chiffres ici sur EOF.

@cmd/cset/a!(n%%%1)

Calculez et imprimez implicitement le résultat.

Neil
la source