Verwenden Sie Ihren Code erneut!

23

Bei dieser Herausforderung versuchen wir, zwei wichtige Probleme gleichzeitig zu lösen. Sie sind:

  1. Sagen Sie bei gegebenen ganzen Zahlen a und b , ob a b -1 eine Primzahl ist.
  2. Gegeben ganze Zahlen a und b , Rückkehr nCr (a, b).

Insbesondere müssen Sie zwei Programme schreiben, eines für die erste und eines für die andere Aufgabe. Da wir beide Probleme gleichzeitig lösen möchten, wird empfohlen, in beiden Programmen denselben Code zu verwenden.

Wertung

Die Punktzahl einer Antwort ist der Levenshtein-Abstand zwischen den beiden Programmen. Niedrigere Punktzahl ist besser. Bei einem Unentschieden gewinnt die Antwort mit dem kürzesten kombinierten Code der beiden Programme. Mit diesem Skript können Sie die Bewertung Ihrer Lösung berechnen.

Regeln

  1. Sie müssen zwei Programme in derselben Sprache schreiben, die die oben beschriebenen Aufgaben lösen. Sie können beliebige E / A-Methoden verwenden. Für Aufgabe 1 können Sie einen Wahrheits- / Falschwert zurückgeben oder zwei Werte auswählen, die "wahr" und "falsch" bedeuten, und sie entsprechend zurückgeben. Z.B. Sie können wählen, dass "prime"dies wahr und "not prime"falsch bedeutet.
  2. Die von Ihnen verwendeten Algorithmen müssen für alle möglichen Eingaben funktionieren, es ist jedoch in Ordnung, wenn der Code aufgrund der Einschränkungen des verwendeten Nummerntyps für große Nummern fehlschlägt. Sie können davon ausgehen, dass die Eingabe gültig ist.
  3. Keine Untermenge des Programms darf das Problem lösen, dh. Der Code darf nicht funktionieren, wenn Zeichen entfernt werden. Der folgende Code ist zum Beispiel ungültig, da es möglich ist, den nicht verwendeten else-Block zu entfernen, ohne das Programm zu unterbrechen:

    if (1) { /* change to 0 to get the second program*/
        ...
    } else {
        ...
    }
    
  4. Standardlücken sind nicht erlaubt.

Testfälle

a b -1 ist prime?

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
fergusq
quelle
1
Dies kann nützlich sein, um die Entfernung von Levenshtein zu berechnen
Luis Mendo
3
Die Idee ist schön, aber ich denke, Sie werden mit Levenshtein distance 1 immer noch Lösungen erhalten, die es schaffen, Änderungen an nicht verwendeten Teilen auf die eine oder andere Weise zu verhindern und dann effektiv die Struktur zu erhalten, die Sie verbieten möchten.
Martin Ender
6
@ LuisMendo Das Problem ist, dass viele dieser Lösungen sehr langsam sind. Sie können stattdessen dieses Mathics-Skript verwenden.
Martin Ender
3
Ich denke, eine bessere Metrik wäre die Levenshtein-Distanz geteilt durch die Gesamtlänge der beiden Programme gewesen.
Greg Martin
1
@ GregMartin Würde das nicht zu Code Bowling führen? Es ist möglich, Programme künstlich zu vergrößern und dennoch zu behaupten, dass sie keinen unnötigen Code enthalten.
Fergusq

Antworten:

7

MATLAB, Abstand 10

Primalität:

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

nCr:

function x=f(a,b);x=nchoosek(a,b);
Steadybox
quelle
4
Das ist das, wonach ich gesucht habe!
Kritixi Lithos
7

PHP, Abstand 29

a^b-1 Gibt 0 für wahr und einen beliebigen ganzzahligen Wert> 0 für falsch aus

[,$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, Abstand 36

a^b-1 druckt 1 für wahr, nichts für falsch

[,$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;
Jörg Hülsermann
quelle
7

Ruby, Distance 1, kombinierte Länge 194

Prime Check:

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

Probieren Sie es online!

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}

Probieren Sie es online!

Wie in den Kommentaren vorhergesagt, muss ein Ruck immer gegen den Geist des Problems gehen. Es hat Spaß gemacht, einen Weg zu finden, um das Problem zu umgehen! So funktioniert es: Wir haben zwei separate Lösungen für die Probleme. Wir führen beide aus, fügen sie in ein Array ein und wählen dann entweder das 0. Element oder das 1. Element für einen Bearbeitungsabstand von 1. Dies wäre normalerweise unzulässig, da Sie nur alles löschen könnten, außer der von Ihnen gewünschten Berechnung, und es würde immer noch funktionieren . Jedes Codefragment ist jedoch so geschrieben, dass es vom Laden derselben Standardbibliothek abhängt 'mathn':

  • Der erste nutzt seine eingebauten prime?
  • Die zweite besteht mathndarin, 3/4die Funktionsweise der Division zu ändern - vor dem Laden wird eine Bewertung in vorgenommen 0, während anschließend eine Bewertung in Form eines Bruchs erfolgt (3/4). Da das Zwischenergebnis von (a+1-i)/inicht immer eine ganze Zahl ist, ist das Gesamtergebnis ohne die Bibliothek falsch.

Jetzt müssen wir nur das Laden der Bibliothek davon abhängig machen, dass der Rest des Codes unverändert bleibt. Wir erzeugen dazu den Namen mathn mit der Zeichenlänge des restlichen Hauptcodes: Die kombinierte Berechnung hat die Länge 55, die auf 110 verdoppelt wird, was dem ASCII-Wert von 'n' entspricht. Wenn Sie dies also auf die Zeichenfolge 'math' verketten, erhalten Sie die gewünschte Bibliothek.

Als Bonus sorgt die Einführung der Bibliotheksabhängigkeiten dafür, dass der Code in angemessener Zeit ausgeführt wird. Insbesondere würde die naive Herangehensweise an nCr keine gebrochenen Zwischenergebnisse erzeugen.

Histokrat
quelle
4

Gestapelt , Abstand 13

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

Probieren Sie es online! Der erste berechnet nCr, die zweite Primalität, unter Verwendung des Wilson-Theorems.

(f g h) fork!Knallt NArgumente vom Stapel (ruft sie auf a0 ... aN) und wendet sie an a0 ... aN f a0 ... aN h g.

Für das erste Programm:

[([@.!]$/{%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)!
                 *              *

Und zum zweiten:

[^#-:([]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
Conor O'Brien
quelle
4

Python 2 , Abstand 15 , Länge 172

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

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

Probieren Sie es online!

Dennis
quelle
3

Mathematica, Abstand 10

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

Schritt 2: Binomial[#2,#]&

Beide Funktionen übernehmen die Eingaben in der Reihenfolge b,a.

Greg Martin
quelle
3

Javascript ES7, Abstand 14

Vielen Dank an @Conor O'Brien für die Reduzierung der Distanz um 7

Primalität:

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

Gibt 1 zurück, wenn prime 0 zurückgibt, wenn prime nicht.

Unglaublich ineffiziente Primcheck, prüft die Zahl modulo jede Zahl kleiner als es und größer als 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}

Multipliziert 1 mit jeder Zahl von y + 1 bis x und dividiert durch jede Zahl von 1 bis xy (x! / Y!) / (Xy)!

fəˈnəˈtɛk
quelle
Ändern des zweiten Programms auf f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}Bearbeitungsentfernung 14. Probieren Sie es online aus!
Conor O'Brien
2

Oktave, Entfernung 17 16 15

nCr

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

Probieren Sie es online!

isprime(a^b-1)

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

Probieren Sie es online!

Ich beherrsche Octave nicht sehr fließend, daher weiß ich nicht, ob es eine integrierte Funktion zur Berechnung von nCr gibt.

Kritixi Lithos
quelle
1

MATL , Abstand 4, Länge 6

Sagen Sie, ob a^b-1Prime ist:

^qZq

Probieren Sie es online!

Berechnen nCr(a,b):

Xn

Probieren Sie es online!

Wie es funktioniert

Sagen Sie, ob a^b-1Prime ist:

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

Berechnen nCr(a,b):

Xn     % nchoosek with implicit inputs. Implicit display
Luis Mendo
quelle
1

PHP, Abstand 14

Ein Programm mit zwei Funktionen zu schreiben und nur eine davon aufzurufen, würde zu einem Abstand von 1 führen, aber es wäre zu lahm.

Prime Test, 100 Bytes:

[,$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 Bytes:

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

Gelee , Abstand 4, Länge 5

Aufgabe 1

*’ÆP

Aufgabe 2

c

Probieren Sie es online!

Wie es funktioniert

Aufgabe 1

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

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

Aufgabe 2

c     nCr atom
Dennis
quelle
0

JavaScript, Punktzahl: 1, Länge: 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])}

Funktion (a, b) {s = "a = Math.pow (a, b) -sLänge + 79; für (b = 2; a% b ++;); b> a1für (t = sLänge-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

Beide Unterprogramme verwenden die Länge des anderen zur Berechnung ihrer eigenen Konstante, sodass kein Zeichen entfernt werden kann

l4m2
quelle