Dans ce défi, nous essayons de résoudre deux problèmes importants à la fois. Elles sont:

1. Étant donné les entiers a et b , dites si a ^b -1 est un nombre premier.
2. Étant donné les entiers a et b , retournez nCr (a, b).

Plus précisément, vous devez écrire deux programmes, l'un qui effectue la première tâche et l'autre qui effectue l'autre. Comme nous voulons résoudre les deux problèmes en même temps, il est encouragé d'utiliser un même morceau de code dans les deux programmes.

Notation

Le score d'une réponse est la distance Levenshtein entre les deux programmes. Un score plus bas est meilleur. En cas d'égalité, la réponse avec le code combiné le plus court des deux programmes l'emporte. Vous pouvez utiliser ce script pour calculer le score de votre solution.

Règles

1. Vous devez écrire deux programmes dans la même langue pour résoudre les tâches décrites ci-dessus. Vous pouvez utiliser toutes les méthodes d'E / S que vous souhaitez. Pour la tâche 1, vous pouvez renvoyer une valeur vérité / fausse ou choisir deux valeurs pour signifier vrai et faux et les renvoyer en conséquence. Par exemple. vous pouvez choisir cela "prime"signifie vrai et"not prime" faux.
2. Les algorithmes que vous utilisez doivent fonctionner pour toutes les entrées possibles, mais cela ne pose aucun problème si le code échoue pour les grands nombres en raison des limitations du type de numéro utilisé. Vous pouvez supposer que l'entrée est valide.

3. Aucun sous-ensemble du programme ne doit résoudre le problème, c'est-à-dire. le code ne doit pas fonctionner si des caractères sont supprimés. Par exemple, le code suivant n'est pas valide, car il est possible de supprimer le bloc else inutilisé sans interrompre le programme:

   if (1) { /* change to 0 to get the second program*/
       ...
   } else {
       ...
   }
   

4. Les échappatoires standard ne sont pas autorisées.

Cas de test

a ^b -1 est premier?

a b
1 1 false
2 3 true
5 2 false
2 5 true
4 3 false
2 7 true

nCr

a b nCr(a,b)
1 1 1
5 2 10
4 3 4
10 7 120
12 5 792

MATLAB, distance 10

Primalité:

function x=f(a,b);x=isprime(a^b-1);

nCr:

function x=f(a,b);x=nchoosek(a,b);

PHP, distance 29

a^b-1 affiche 0 pour vrai et toute valeur entière> 0 pour faux

[,$a,$b]=$argv;for($c=-$i=1;$i<=$d=$a**$b-1;$d%++$i?:$c++);echo$c;

nCr(a,b)

[,$a,$b]=$argv;for($c=$i=1;$i<=$a;$c*=$i**(1-($i<=$a-$b)-($i<=$b)),$i++);echo$c;

PHP, distance 36

a^b-1 imprime 1 pour vrai rien pour faux

[,$a,$b]=$argv;for($c=-1,$i=1;$i<=$d=-1+$a**$b;)$d%++$i?:$c++;echo$c<1;

nCr(a,b)

[,$a,$b]=$argv;for($c=$d=$i=1;$i<=$a;$c*=$i++)$d*=$i**(($i<=$a-$b)+($i<=$b));echo$c/$d;

Rubis, distance 1, longueur combinée 194

Vérification principale:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][0]';require'math'<<s.size*2;eval s}

Essayez-le en ligne!

nCr:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][1]';require'math'<<s.size*2;eval s}

Essayez-le en ligne!

Comme prévu dans les commentaires, certains crétins doivent toujours aller à l'encontre de l'esprit du problème. C'était amusant de trouver un moyen de contourner cela, cependant! Voici comment cela fonctionne: nous avons deux solutions distinctes aux problèmes. Nous exécutons les deux, les mettons dans un tableau, puis choisissons le 0ème élément ou le 1er, pour une distance d'édition de 1. Ce serait normalement illégal, car vous pouvez simplement tout supprimer, mais le calcul que vous vouliez et cela fonctionnerait toujours . Cependant, chaque extrait de code est écrit pour s'appuyer sur le chargement de la même bibliothèque standard 'mathn':

• Le premier utilise son intégré prime?
• La seconde repose sur la mathnmodification du fonctionnement de la division - avant de la charger, 3/4évalue à 0, puis après, elle évalue à la fraction (3/4). Étant donné que le résultat intermédiaire de (a+1-i)/in'est pas toujours un nombre entier, le résultat global est incorrect sans la bibliothèque.

Il ne nous reste plus qu'à subordonner le chargement de la bibliothèque au reste du code non modifié. Nous faisons cela en générant le nom mathn en utilisant la longueur de caractère du reste du code principal: le calcul combiné a une longueur de 55, qui a doublé pour atteindre 110 est la valeur ASCII de 'n'. Donc concaténer ceci sur la chaîne 'math' donne la bibliothèque désirée.

En prime, l'introduction des dépendances de bibliothèque permet également au code de s'exécuter dans un délai raisonnable. En particulier, l'approche naïve du nCr ne générerait pas de résultats intermédiaires fractionnaires.

05AB1E , distance 3

nCr

sc

Essayez-le en ligne!

isPrime (a ^ b-1)

m<p

Essayez-le en ligne!

Empilé , distance 13

[([@.!]$/{%y!x y-!*})fork!]
[^#-:([]1/$%{!n 1-!})fork!=]

Essayez-le en ligne! La première calcule nCr, la seconde primalité, en utilisant le théorème de Wilson.

(f g h) fork!pops Nargs de la pile (appelez-les a0 ... aN) et applique a0 ... aN f a0 ... aN h g.

Pour le premier programme:

[([@.!]$/{%y!x y-!*})fork!]
[(                  )fork!]  apply the fork of:
  [@.!]                      equiv. { x y : x ! } => `x!`
       $/                    divided by
         {%        }         two-arg function
           y!                y!
             x y-                 (x - y)!
                 *              *

Et pour le second:

[^#-:([]1/$%{!n 1-!})fork!=]  
[^                         ]  exponentiate  (a^b)
  #-                          decrement     (a^b-1)
    :                         duplicate     (a^b-1 a^b-1)
     (              )fork!    apply the fork to:
      []1/                    1-arg identity function
          $%                  modulus by
            {!     }          1-arg with `n`:
              n 1-             (n-1)
                  !                 !
                          =   check for equality

Python 2 , distance 15 , longueur 172

Tache 1

D=lambda k:max(k-1,1)
P=lambda n,k=0:n<k or P(n-1,k)*n/k
lambda a,b:P(a**b-2)**2%D(a**b)

Tâche 2

D=lambda k:max(k-1,1)
P=lambda n,k=1:n<k or P(n-1,D(k))*n/k
lambda a,b:P(a,b)/P(a-b)

Essayez-le en ligne!

Mathematica, distance 10

Tache 1: PrimeQ[#2^#-1]&

Tâche 2: Binomial[#2,#]&

Les deux fonctions prennent les entrées dans l'ordre b,a.

Javascript ES7, distance 14

Merci à @Conor O'Brien d'avoir réduit la distance de 7

Primalité:

f=x=>y=>{t=x**y-1;s=1;for(i=2;i<t;i++){if(!t%i)s=i-i}return s}

Renvoie 1 si premier renvoie 0 sinon premier.

Vérification de prime incroyablement inefficace, vérifie le nombre modulo chaque nombre plus petit que lui et supérieur à 1 ...

nCr:

f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}

Multiplie 1 par chaque nombre de y + 1 à x et divise par chaque nombre de 1 à xy (x! / Y!) / (Xy)!

Octave, distance 17 16 15

nCr

a=input("");b=input("");f=@(x)factorial(x);printf("%d",f(a)/f(b)/f(a-b))

Essayez-le en ligne!

isprime(a^b-1)

a=input("");b=input("");f=@(x)isprime(x);printf("%d",f(a^b-f(8-6)))

Essayez-le en ligne!

Je ne parle pas très bien Octave, donc je ne sais pas s'il y a une fonction intégrée pour calculer nCr.

MATL , distance 4, longueur 6

Dites si a^b-1est premier:

^qZq

Essayez-le en ligne!

Calculer nCr(a,b):

Xn

Essayez-le en ligne!

Comment ça marche

Dites si a^b-1est premier:

^      % Power with implicit inputs
q      % Subtract 1
Zq     % Is prime? Implicit display

Calculer nCr(a,b):

Xn     % nchoosek with implicit inputs. Implicit display

Pyth, distance 4, longueur totale 8

Primality of a^b-1

P_t^F

Essayez-le en ligne!

nCr (a, b)

.cF

Essayez-le en ligne!

Les deux prennent les entrées sous forme de tuples / listes d'entiers (par exemple (1,2)).

PHP, distance 14

Écrire un programme avec deux fonctions et n'en appeler qu'une seule entraînerait une distance de 1, mais ce serait trop boiteux.

Premier test, 100 octets:

[,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n%$i;);return$i==1;}echo f($a**$b*-1)*(1|f($a-$b));

nCr, 98 octets:

[,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n*=$i;);return$n*=1;}echo f($a)/(f($b)*f($a-$b));

Gelée , distance 4, longueur 5

Tache 1

*’ÆP

Tâche 2

c

Essayez-le en ligne!

Comment ça marche

Tache 1

*’ÆP  Main link. Argument: a, b

*     Yield a**b.
 ’    Decrement; yield a**b-1.
  ÆP  Test the result for primality.

Tâche 2

c     nCr atom

JavaScript Score: 1, longueur: 144 142 126 117

function(a,b){s="a=Math.pow(a,b)-t;for(b=2;a%b++;);b>a1for(;b;)t=t*a--/b--";t=s.length-56;return eval(s.split(1)[0])}

fonction (a, b) {s = "a = Math.pow (a, b) -s.length + 79; for (b = 2; a% b ++;); b> a1for (t = s.length-79 ; b;) t = t * a - / b - "; return eval (s.split (1) [1])}

function A(a,b){a=Math.pow(a,b)-(B+0).length+63;for(b=2;a%b++;);return b>a;}
function B(a,b){for(t=(A+0).length-76;b;)t=t*a--/b--;return t;}
F=A

Les deux sous-programmes utilisent la longueur de l'autre pour calculer sa propre constante, donc aucun caractère ne peut être supprimé