La validation du module

12

Étant donné une liste d'expressions mathématiques qui sont toutes vraies et consistent en des calculs de reste modulo avec deux nombres et un résultat, votre tâche consiste à produire les premiers nnombres qui sont vrais pour toutes les instructions de la liste.

Par exemple:

[m % 3 = 0, m % 4 = 1, m % 5 = 3], où% est l'opérateur modulo.

Pour n= 3, les 3 premiers nombres (en comptant à partir de 0) qui correspondent à la séquence sont 33, 93, 153, donc votre résultat serait que (formatez-vous).

Règles / IO

  1. Vous prenez un nombre positif net une liste de vérités. Bien sûr, les choses dont vous avez besoin ne sont que le RHS de l'opération modulo et le résultat.
  2. net les nombres dans la liste des vérités seront toujours dans la plage 1 -> 2 ^ 31-1 , et les résultats aussi.
  3. Vous prenez l'entrée sous n'importe quelle forme pratique et la sortie sous n'importe quelle forme pratique. Par exemple, l' entrée: 3 [3 0, 4 1, 5 3]et la sortie: 33 93 153.
  4. Il est garanti que la solution est mathématiquement possible.
  5. La source d'entrée peut provenir d'un fichier, des paramètres de fonction, stdin, etc ... Il en va de même pour la sortie.
  6. Pas de failles.
  7. C'est le code-golf, donc le nombre d'octets le plus bas l'emporte.

Cas de test

# Input in the form <n>, <(d r), (d2 r2), ...>
# where <d> = RHS of the modulo expression and <r> the result of the expression. Output in the next line.

5, (3 2), (4 1), (5 3)
53 113 173 233 293

3, (8, 0), (13, 3), (14, 8)
120 848 1576

Implémentation de référence en pseudo-code

n = (an integer from stdin)
truths = (value pairs from stdin)
counter = 0

while n != 0 {
    if matches_criterias(counter, truths) {
        print counter
        n -= 1
    }

    counter += 1
}
Yytsi
la source
Copie
flawr
@flawr EDIT: L'autre question semble interdire beaucoup de choses et n'imprime qu'un seul terme. Je ne sais plus s'il s'agit d'un doublon ....
Yytsi
1
@flawr Ce défi a une limite de temps. Il existe des moyens plus efficaces pour résoudre ce problème qui ne dépendent pas du théorème des restes chinois.
Dennis
Oui, j'en suis conscient, c'est pourquoi je viens de le lier.
flawr
Un 0résultat valide?
Neil

Réponses:

6

Gelée , 7 octets

%⁼⁴
0ç#

Ceci est un programme complet. Les arguments sont les diviseurs, les modules cibles et le nombre de solutions, dans cet ordre.

Essayez-le en ligne!

Comment ça fonctionne

0ç#  Main link.
     Left argument: D (array of divisors)
     Right argument: M (array of target moduli)
     Third argument: n (number of solutions)

0ç#  Execute the helper link with k = 0, 1, 2, ... as left argument and D as the
     right one until n of them return 1. Yield the array of matches.


%⁼⁴  Helper link. Left argument: k. Right argument: D

%    Compute k % d for each d in D.
 ⁼⁴  Compare the result with M.
Dennis
la source
4

Perl 6 , 33 octets

{grep((*X%@^b)eqv@^c,0..*)[^$^a]}

Essayez-le

L'entrée est ( number-of-values, list-of-divisors, list-of-remainders )

Étendu:

{   # bare block lambda with placeholder parameters 「$a」 「@b」 「@c」

  grep(

    # WhateverCode lambda:
    (

      *        # the value being tested

      X%       # cross modulus

      @^b      # with the divisors ( second parameter )

    )

    eqv        # is that list equivalent with

    @^c        # the expected remainders ( third parameter )

    # end of WhateverCode lambda

    ,

    0 .. *     # Range of all Integers starting with 0

  )[ ^$^a ]    # grab up-to 「$a」 values ( first parameter )
               # ( 「^$a」 is the same as 「0 ..^ $a」 )
}
Brad Gilbert b2gills
la source
4

JavaScript (ES6), 71 68 octets

a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]

Une fonction récursive simple. Utilisez en currying dans le tableau premier et ndeuxième, comme ceci:

g=a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]
g([[3, 2], [4, 1], [5, 3]])(5)
ETHproductions
la source
4

JavaScript (ES6), 74 70 69 octets

Prend l'entrée comme un entier net un tableau ade [modulo, remainder]tableaux avec une syntaxe de curry (n)(a).

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

Cas de test

Arnauld
la source
3

Haskell, 47 octets

n#l=take n[i|i<-[0..],all(\(d,r)->mod i d==r)l]

Exemple d'utilisation: 3 # [(8,0),(13,3),(14,8)]-> [120,848,1576].

nimi
la source
3

Python, 67 octets

lambda n,r:[k for k in range(2**32)if all(k%d==m for d,m in r)][:n]
orlp
la source
Vous avez seulement besoin range(2**31). De plus, très agréable. J'ai trouvé cette réponse indépendamment.
mbomb007
3

JavaScript (ES6), 72 70 octets

a=>g=(n,i,r=[],m=a.some(e=>i%e[0]^e[1]))=>n?g(n-!m,-~i,m?r:[...r,i]):r

Curry sur le tableau de conditions en premier et le nombre de résultats en second. Edit: enregistré 2 octets en ne gérant pas le cas zéro.

Neil
la source
2

Mathematica, 42 octets

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&

Fonction sans nom, renvoyant une liste d'entiers positifs et prenant trois entrées: la liste des modules, la liste des restes et le nombre nd'entiers à renvoyer. Par exemple, le deuxième cas de test est invoqué par

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&[{8,13,14},{0,3,8},3]

et retourne {120, 848, 1576}.

Le builtin #2~ChineseRemainder~#donne la plus petite solution non négative; pour obtenir toutes les solutions souhaitées, nous ajoutons ce nombre à Range[0,#3-1]LCM@@#, qui est le premier nmultiple non négatif du multiple le moins commun de tous les modules.

Pour autant que je sache, Mathematica n'a pas de listes infinies évaluées paresseusement, donc cette implémentation était plus courte que tout ce que j'ai trouvé qui testait les entiers non négatifs un par un - même avec la longueur du nom de la fonction ChineseRemainder, et même si un test similaire Mod[k,{8,13,14}]=={0,3,8}fonctionne parfaitement bien.

Greg Martin
la source
2

PHP, 97 octets

réponse la plus longue jusqu'à présent. Mais je suis content d'avoir pu descendre en dessous de 100.

for($a=$argv;++$k;)for($i=$v=2;$m=$a[$i++];$v>$argc/2&&$a[1]-->0?print$k._:0)$v+=$k%$m==$a[$i++];

prend les entrées d'arguments de ligne de commande séparés,
affiche les correspondances séparées et suivies par des traits de soulignement.
La boucle ne se rompt jamais; à peine adapté aux testeurs en ligne.

Courez comme php -r 'code' <n> <modulo1> <result1> <modulo2> <result2> ....

panne

for($a=$argv;++$k;)         // loop $k up from 1
    for($i=$v=2;                // $i = argument index, $v=2+ number of satisfied equations
        $m=$a[$i++];            // loop through modulo/result pairs
        $v>$argc/2                  // 2. if $v>argument-count/2
        &&$a[1]-->0                 // and match count not exhausted
            ?print$k._                  // print match
            :0                          // else do nothing
        )
            $v+=$k%$m==$a[$i++];    // 1. if $k%modulo==result, increment $v

Remarques

$argc==count($argv). Pour trois paires, il y a 8 arguments: le nom de fichier $argv[0], n= $argv[1]et les paires modulo/ resultau-dessus. $v=2incrémenté 3 fois donne 5> $argc/2.

Ajoutez un octet pour une sortie propre: remplacez &&$a[1]-->0?print$k._par ?$a[1]--?print$k._:die.

Titus
la source
1

SmileBASIC, 102 octets

DEF V N,M
FOR K=1TO N@L
T=T+1F=0FOR J=1TO LEN(M)F=F||T MOD M[J-1]-M[J]J=J+1NEXT
ON!F GOTO @L?T
NEXT
END

C'est la première fois que je l'utilise ONdans SB. La raison pour laquelle je l'ai utilisé ici au lieu de IF F GOTO@Lc'était pour que je puisse le mettre ?Tsur la même ligne, en économisant 1 octet.

12Me21
la source
1

Python, 59 octets

lambda n,m:[i for i in range(2**31)if all(map(eval,m))][:n]

m est une liste d'expressions sous forme de chaîne comme ["i % 4 == 1", ...]

Essayez-le en ligne (avec une gamme plus courte, donc il se terminera réellement)

mbomb007
la source
0

PHP, 91 octets

Prendre la liste comme tableau associatif

<?for($t=1;$r<$_GET[1];$i+=$t=!$t?:print+$i._.!++$r)foreach($_GET[0]as$k=>$v)$t*=$i%$k==$v;

Essayez-le en ligne!

Jörg Hülsermann
la source