Gunakan kembali kode Anda!

23

Dalam tantangan ini kami mencoba menyelesaikan dua masalah penting sekaligus. Mereka:

  1. Diberikan bilangan bulat a dan b , beri tahu apakah b -1 adalah bilangan prima.
  2. Dengan bilangan bulat a dan b , kembalikan nCr (a, b).

Secara khusus, Anda harus menulis dua program, satu yang melakukan tugas pertama dan satu yang melakukan yang lain. Karena kami ingin menyelesaikan kedua masalah sekaligus, disarankan untuk menggunakan kode yang sama di kedua program.

Mencetak gol

Skor jawaban adalah jarak Levenshtein antara kedua program. Skor yang lebih rendah lebih baik. Dalam hal seri, jawaban dengan kode gabungan terpendek dari kedua program akan menang. Anda dapat menggunakan skrip ini untuk menghitung skor solusi Anda.

Aturan

  1. Anda harus menulis dua program dalam bahasa yang sama yang menyelesaikan tugas yang dijelaskan di atas. Anda dapat menggunakan metode I / O yang Anda inginkan. Untuk tugas 1, Anda dapat mengembalikan nilai kebenaran / kepalsuan atau memilih dua nilai yang berarti benar dan salah dan mengembalikannya sesuai. Misalnya. Anda dapat memilih itu "prime"berarti benar dan"not prime" berarti salah.
  2. Algoritma yang Anda gunakan harus bekerja untuk semua input yang mungkin, tetapi tidak apa-apa jika kode gagal untuk angka besar karena keterbatasan tipe nomor yang digunakan. Anda dapat mengasumsikan bahwa input tersebut valid.
  3. Tidak ada subset dari program yang harus menyelesaikan masalah, yaitu. kode tidak boleh berfungsi jika ada karakter yang dihapus. Misalnya, kode berikut ini tidak valid, karena dimungkinkan untuk menghapus blok-blok yang tidak digunakan tanpa merusak program:

    if (1) { /* change to 0 to get the second program*/
        ...
    } else {
        ...
    }
    
  4. Tidak ada celah standar.

Uji kasus

a b -1 adalah 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
sumber
1
Ini mungkin berguna untuk menghitung jarak Levenshtein
Luis Mendo
3
Idenya bagus, tapi saya pikir Anda masih akan mendapatkan solusi dengan Levenshtein jarak 1 yang berhasil mencegah modifikasi ke bagian yang tidak digunakan dengan satu cara atau yang lain dan kemudian secara efektif menghasilkan struktur yang ingin Anda larang.
Martin Ender
6
@LuisMendo Masalahnya adalah banyak dari solusi tersebut sangat lambat. Anda dapat menggunakan skrip Matematika ini sebagai gantinya.
Martin Ender
3
Saya pikir metrik yang lebih baik adalah jarak Levenshtein dibagi dengan total panjang kedua program.
Greg Martin
1
@ GregMartin Bukankah itu menghasilkan kode bowling? Dimungkinkan untuk membuat program secara lebih besar dan masih mengklaim bahwa mereka tidak memiliki kode yang tidak perlu.
fergusq

Jawaban:

7

MATLAB, jarak 10

Primality:

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

nCr:

function x=f(a,b);x=nchoosek(a,b);
Steadybox
sumber
4
Itu built-in yang saya cari!
Kritixi Lithos
7

PHP, jarak 29

a^b-1 mencetak 0 untuk true dan semua nilai integer> 0 untuk 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, jarak 36

a^b-1 mencetak 1 untuk true nothing for false

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

Ruby, Jarak 1, Panjang Gabungan 194

Cek perdana:

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

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

Cobalah online!

Seperti yang diperkirakan dalam komentar, beberapa brengsek selalu harus melawan semangat masalah. Sungguh menyenangkan menemukan cara untuk mengatasinya! Begini cara kerjanya: Kami memiliki dua solusi terpisah untuk masalah tersebut. Kami menjalankan keduanya, memasukkannya ke dalam array, dan kemudian memilih elemen ke-0 atau ke-1, untuk jarak sunting 1. Ini biasanya ilegal, karena Anda bisa menghapus semuanya kecuali perhitungan yang Anda inginkan dan masih berfungsi . Namun, setiap potongan kode ditulis mengandalkan pemuatan perpustakaan standar yang sama, 'mathn':

  • Yang pertama menggunakan builtin-nya prime?
  • Yang kedua bergantung pada mathnmengubah cara kerja divisi - sebelum memuatnya, 3/4mengevaluasi 0, sementara kemudian mengevaluasi ke fraksi (3/4). Karena hasil antara (a+1-i)/itidak selalu angka keseluruhan, hasil keseluruhan salah tanpa perpustakaan.

Sekarang kita hanya perlu membuat memuat pustaka bergantung pada sisa kode yang tidak dimodifikasi. Kami melakukan ini dengan menghasilkan nama mathn menggunakan panjang karakter dari sisa kode utama: perhitungan gabungan memiliki panjang 55, yang dua kali lipat menjadi 110 adalah nilai ASCII dari 'n'. Jadi menggabungkan ini ke string 'matematika' memberikan perpustakaan yang diinginkan.

Sebagai bonus, memperkenalkan dependensi perpustakaan juga membuat kode berjalan dalam jumlah waktu yang wajar. Secara khusus, pendekatan naif terhadap nCr tidak akan menghasilkan hasil antara fraksional.

histokrat
sumber
4

Ditumpuk , jarak 13

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

Cobalah online! Yang pertama menghitung nCr, keutamaan kedua, menggunakan teorema Wilson.

(f g h) fork!muncul Nargumen dari stack (panggil mereka a0 ... aN) dan berlaku a0 ... aN f a0 ... aN h g.

Untuk program pertama:

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

Dan untuk yang kedua:

[^#-:([]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
sumber
4

Python 2 , jarak 15 , panjang 172

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

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

Cobalah online!

Dennis
sumber
3

Mathematica, jarak 10

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

Tugas 2: Binomial[#2,#]&

Kedua fungsi mengambil input dalam urutan b,a.

Greg Martin
sumber
3

Javascript ES7, jarak 14

Terima kasih @Conor O'Brien untuk mengurangi jarak sebesar 7

Primality:

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

Mengembalikan 1 jika prime mengembalikan 0 jika tidak prime.

Pemeriksaan prima yang sangat tidak efisien, memeriksa modulo setiap nomor lebih kecil dari itu dan lebih besar dari ...

nCr:

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

Kalikan 1 dengan setiap angka dari y + 1 hingga x dan bagilah dengan setiap angka dari 1 hingga xy (x! / Y!) / (Xy)!

fəˈnɛtɪk
sumber
Mengubah program kedua untuk f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}memberi jarak sunting 14. Coba online!
Conor O'Brien
2

Oktaf, jarak 17 16 15

nCr

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

Cobalah online!

isprime(a^b-1)

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

Cobalah online!

Saya tidak terlalu lancar menggunakan Octave, jadi saya tidak tahu apakah ada builtin untuk menghitung nCr.

Kritixi Lithos
sumber
1

MATL , jarak 4, panjang 6

Katakan apakah a^b-1prima:

^qZq

Cobalah online!

Hitung nCr(a,b):

Xn

Cobalah online!

Bagaimana itu bekerja

Katakan apakah a^b-1prima:

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

Hitung nCr(a,b):

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

Pyth, jarak 4, total panjang 8

Primality dari a^b-1

P_t^F

Cobalah online!

nCr (a, b)

.cF

Cobalah online!

Keduanya mengambil input sebagai tupel / daftar bilangan bulat (misalnya (1,2)).

notjagan
sumber
1

PHP, jarak 14

Menulis program dengan dua fungsi dan hanya memanggil salah satu dari mereka akan mengarah ke jarak 1, tetapi terlalu timpang.

Tes Perdana, 100 byte:

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

[,$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
sumber
0

Jelly , jarak 4, panjang 5

Tugas 1

*’ÆP

Tugas 2

c

Cobalah online!

Bagaimana itu bekerja

Tugas 1

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

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

Tugas 2

c     nCr atom
Dennis
sumber
0

JavaScript, Nilai: 1, Panjang: 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])}

fungsi (a, b) {s = "a = Math.pow (a, b) -s.length + 79; untuk (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

Kedua subrutin menggunakan panjang yang lain untuk menghitung konstanta sendiri, sehingga tidak ada char yang dapat dihapus

l4m2
sumber