W tym wyzwaniu staramy się rozwiązać dwa ważne problemy jednocześnie. Oni są:

1. Podane liczby całkowite i b , stwierdzić, czy ^b -1 jest liczbą pierwszą.
2. Podane liczby całkowite i b , powrót NCR (a, b).

W szczególności musisz napisać dwa programy, jeden, który wykonuje pierwsze zadanie, a drugi, który wykonuje drugie. Ponieważ chcemy rozwiązać oba problemy jednocześnie, zaleca się użycie tego samego fragmentu kodu w obu programach.

Punktacja

Wynik odpowiedzi to odległość Levenshteina między dwoma programami. Niższy wynik jest lepszy. W przypadku remisu wygrywa odpowiedź z najkrótszym połączonym kodem dwóch programów. Możesz użyć tego skryptu, aby obliczyć wynik swojego rozwiązania.

Zasady

1. Musisz napisać dwa programy w tym samym języku, które rozwiązują zadania opisane powyżej. Możesz użyć dowolnej metody we / wy. W przypadku zadania 1 możesz zwrócić wartość prawda / fałsz lub wybrać dwie wartości oznaczające prawda i fałsz i odpowiednio je zwrócić. Na przykład. możesz wybrać, co "prime"oznacza prawda, a "not prime"fałsz.
2. Algorytmy, których używasz, muszą działać dla wszystkich możliwych danych wejściowych, ale jest to OK, jeśli kod zawiedzie w przypadku dużych liczb z powodu ograniczeń używanego typu liczb. Możesz założyć, że dane wejściowe są prawidłowe.

3. Żaden podzbiór programu nie może rozwiązać problemu, tj. kod nie może działać, jeśli zostaną usunięte jakiekolwiek znaki. Na przykład poniższy kod jest niepoprawny, ponieważ możliwe jest usunięcie nieużywanego bloku else bez uszkodzenia programu:

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

4. Standardowe luki są niedozwolone.

Przypadki testowe

a ^b -1 jest liczbą pierwszą?

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, odległość 10

Pierwotność:

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

nCr:

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

PHP, odległość 29

a^b-1 wypisuje 0 dla wartości true i dowolną wartość całkowitą> 0 dla wartości false

[,$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, odległość 36

a^b-1 drukuje 1 za prawdę, nic za fałsz

[,$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;

Rubin, Odległość 1, Łączna długość 194

Kontrola wstępna:

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

Wypróbuj 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}

Wypróbuj online!

Jak przewidziano w komentarzach, jakiś szarpnięcie zawsze musi być sprzeczne z duchem problemu. Fajnie było znaleźć sposób na obejście tego! Oto jak to działa: Mamy dwa osobne rozwiązania problemów. Uruchamiamy oba, umieszczamy je w tablicy, a następnie albo wybieramy 0-ty element, albo 1-ty, dla odległości edycji wynoszącej 1. Zwykle byłoby to nielegalne, ponieważ można było po prostu usunąć wszystko oprócz żądanych obliczeń i nadal działałoby . Jednak każdy fragment kodu jest pisany w taki sposób, aby polegał na ładowaniu tej samej biblioteki standardowej 'mathn':

• Pierwszy używa wbudowanego prime?
• Drugi polega na mathnzmianie sposobu działania podziału - przed załadowaniem 3/4ocenia na 0, a następnie na ułamek (3/4). Ponieważ pośredni wynik (a+1-i)/inie zawsze jest liczbą całkowitą, ogólny wynik jest niepoprawny bez biblioteki.

Teraz musimy tylko uzależnić ładowanie biblioteki od niezmodyfikowania reszty kodu. Robimy to, generując nazwę mathn przy użyciu długości znaków reszty głównego kodu: połączone obliczenia mają długość 55, która podwojona do 110 jest wartością ASCII „n”. Tak więc powiązanie tego z ciągiem „matematyka” daje pożądaną bibliotekę.

Jako bonus, wprowadzenie zależności biblioteki sprawia, że ​​kod działa w rozsądnym czasie. W szczególności naiwne podejście do nCr nie wygenerowałoby ułamkowych wyników pośrednich.

05AB1E , odległość 3

nCr

sc

Wypróbuj online!

isPrime (a ^ b-1)

m<p

Wypróbuj online!

Ułożone , odległość 13

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

Wypróbuj online! Pierwszy oblicza nCr, drugi pierwszeństwo, używając twierdzenia Wilsona.

(f g h) fork!wyrzuca Nargumenty ze stosu (wywołuje je a0 ... aN) i stosuje a0 ... aN f a0 ... aN h g.

Dla pierwszego programu:

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

A po drugie:

[^#-:([]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 , dystans 15 , długość 172

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

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

Wypróbuj online!

Matematyka, odległość 10

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

Zadanie 2: Binomial[#2,#]&

Obie funkcje przyjmują dane wejściowe w kolejności b,a.

JavaScript ES7, odległość 14

Dzięki @Conor O'Brien za zmniejszenie odległości o 7

Pierwotność:

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

Zwraca 1, jeśli liczba pierwsza zwraca 0, jeśli nie liczba pierwsza.

Niesamowicie nieefektywna kontrola pierwsza, sprawdza liczbę modulo każdej liczby mniejszej od niej i większej niż 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}

Mnoży 1 przez każdą liczbę od y + 1 do x i dzieli przez każdą liczbę od 1 do xy (x! / Y!) / (Xy)!

Oktawa, dystans 17 16 15

nCr

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

Wypróbuj online!

isprime(a^b-1)

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

Wypróbuj online!

Nie jestem zbyt biegły w Octave, więc nie wiem, czy jest wbudowane narzędzie do obliczania nCr.

MATL , dystans 4, długość 6

Powiedz, czy a^b-1jest liczbą pierwszą:

^qZq

Wypróbuj online!

Oblicz nCr(a,b):

Xn

Wypróbuj online!

Jak to działa

Powiedz, czy a^b-1jest liczbą pierwszą:

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

Oblicz nCr(a,b):

Xn     % nchoosek with implicit inputs. Implicit display

Pyth, odległość 4, całkowita długość 8

Pierwszeństwo a^b-1

P_t^F

Wypróbuj online!

nCr (a, b)

.cF

Wypróbuj online!

Oba przyjmują dane wejściowe jako krotki / listy liczb całkowitych (np (1,2).).

PHP, odległość 14

Napisanie programu z dwiema funkcjami i wywołanie tylko jednej z nich doprowadziłoby do odległości 1, ale byłoby zbyt kiepskie.

Test wstępny, 100 bajtów:

[,$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 bajtów:

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

Galaretka , odległość 4, długość 5

Zadanie 1

*’ÆP

Zadanie 2

c

Wypróbuj online!

Jak to działa

Zadanie 1

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

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

Zadanie 2

c     nCr atom

JavaScript, wynik: 1, długość: 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])}

funkcja (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

Oba podprogramy używają długości drugiego do obliczania własnej stałej, więc nie można usunąć znaku