Ini adalah tantangan polisi dan perampok . Utas Polisi untuk tantangan ini ada di sini
Pertanyaan menarik untuk dipikirkan adalah sebagai berikut:
Jika saya memiliki urutan angka, berapa banyak dari mereka yang harus saya berikan sebelum jelas urutan apa yang saya bicarakan?
Sebagai contoh jika saya ingin berbicara tentang bilangan bulat positif agar mulai dari , saya dapat mengatakan , tetapi apakah itu benar-benar cukup?1 , 2 , 3 , …
Saya punya satu cara untuk menjawab pertanyaan ini, dan menjadi pegolf-kode Ini melibatkan golf kode. Anda telah memberikan ketentuan urutan yang cukup jika kode terpendek yang menghasilkan istilah tersebut menghasilkan semua ketentuan urutan tersebut. Jika kami memikirkan hal ini dalam hal kode-golf, ini berarti Anda telah memberikan cukup uji kasus sehingga kode terpendek yang lulus uji-kasus melakukan tugas yang diinginkan.
Tantangan
Tantangan ini adalah tantangan polisi dan perampok . Di mana polisi akan mempresentasikan kasus uji dan perampok harus menemukan cara yang lebih pendek untuk menipu kasus uji selain dari urutan yang dimaksud. Polisi akan menyajikan hal-hal berikut:
Sepotong kode yang mengambil integer positif sebagai input dan menghasilkan integer sebagai output. Kode ini bisa nol atau satu diindeks tetapi harus jelas apa pengindeksannya. Kode ini akan menentukan urutan Anda.
Persyaratan platform atau bahasa apa pun yang relevan yang dapat mempengaruhi keluaran, misalnya ukuran longint.
Sejumlah , bersama dengan istilah pertama dari urutan sebagaimana dihitung oleh kode. Ini akan bertindak sebagai "kasus uji".n
Perampok akan menemukan program dalam bahasa yang sama yang lebih pendek dari yang disajikan dan melewati semua kasus uji (menghasilkan output yang sama untuk input pertama sebagai kode polisi). Kode perampok juga harus berbeda dalam output dari program polisi untuk beberapa nomor lebih besar dari .n
Mencetak gol
Perampok akan dinilai dalam jumlah retakan yang mereka temukan dengan lebih banyak retakan yang lebih baik. Sebuah jawaban dapat di-crack kembali dengan menemukan jawaban yang valid lebih pendek dari pada yang asli. Jika jawaban di-crack-kan untuk kedua kalinya, intinya diberikan ke cracker kedua daripada yang pertama.
sumber
Jawaban:
Pertanyaan , jawaban Stephen , 3 byte
Cobalah online!
Bagaimana itu bekerja
Sepertinya urutan harus identik, tetapi ini memberi
12345678910
untukn = 10
sementara"::$
memberi1234567891
.sumber
JavaScript, jawaban fəˈnɛtɪk (17 byte)
Yah itu mudah untuk hardcode untuk mendapatkan skor yang jauh lebih rendah ... Berbeda dari implementasi referensi untuk setiap entri , 0-diindeks. Ini menggunakan trik golf JS yang sangat terkenal: pengindeksan ke dalam urutan dengan bilangan bulat yang melebihi batas mengembalikan nilai falsy ( ), sehingga hanya dapat dipaksa ke nilai default dengan menggunakan logika OR ( ), dalam hal ini kasus , menangani istilah terakhir dari urutan tetapi juga yang mengikuti.x≥6
undefined
||
22
Pengujian
Atau, Coba online!
sumber
Haskell , jawaban Laikoni , 15 byte
Cobalah online!
Saya biasanya akan menunjukkan hal seperti ini dalam komentar, tetapi kemudian saya berpikir, polisi dan perampok sedikit lebih jengkel.
Ini hanya jawaban BMO dikurangi kasus khusus untuk
b 42
. Karena dokumen asli Laikoni menggunakan floating point, itu tidak perlu: cukup temukan angka yang cukup besar untuk memberikan kesalahan pembulatan dalam hal itu tetapi tidak dalamInteger
aritmatika yang tepat . Sebagai contoh:sumber
Python 2 , jawaban xnor , 43 byte
Perbedaan pertama terjadi untuk :n=69
Cobalah online!
Kredit
Banyak penghargaan untuk crack ini harus diberikan kepada @ Mr.Xcoder yang pertama kali memposting komentar tentang kemungkinan serangan menggunakan metode ini, dan ke @PoonLevi yang menemukan solusi 44-byte.
Bagaimana?
Teori
Retak didasarkan pada teorema kecil Fermat yang menyatakan bahwa jika adalah prima dan dan relatif prima, maka:a pp a p
Secara khusus, untuk :a=2
Jadi ada beberapa bilangan bulat positif sehingga:k
Yang mengarah ke:
Rumus terakhir ini adalah salah satu kode Python berasal dan sekarang berlaku untuk , meskipun relatif tidak prima dengan dirinya sendiri.p=2 2
Sekarang, untuk bagian terpenting: kebalikan dari teorema kecil Fermat tidak benar. Kita mungkin memiliki untuk beberapa bilangan komposit . Angka-angka semacam itu disebut pseudoprim Fermat sebagai basis . Fermat pseudoprimes ke basis 2 juga dikenal sebagai nomor Poulet .an−1≡1(modn) n a
Pseudoprime Fermat pertama ke basis (atau nomor Poulet pertama) adalah , yang kita miliki:2 n=341=11×31
2 341 - 1 ≡ 1
Ini berarti bahwa algoritma kami akan kembali bukannya diharapkan 69 th prima .347341 347
Penerapan
@PoonLevi menemukan solusi 44-byte berikut, yang secara langsung didasarkan pada :(2)
Dengan menggunakan1 21−1≡0(mod1)
<2
alih-alih==1
, kami menyimpan 1 byte tetapi kami memperkenalkan ke dalam urutan, karena :2 1 - 1 ≡ 0Cobalah online!
Dengan memulai dengan , kita mendapatkan ketentuan yang diharapkan sebesar 1 karena kita melakukan satu iterasi lebih sedikit:p=2
Cobalah online!
Trik terakhir adalah menggunakan
n<1or
alih-alihn and
. Ini sama panjangnya tetapi menjadikan iterasi terakhir menghasilkan True alih-alih 0 , karenanya menambahkan offset yang hilang ke setiap istilah.sumber
Python 3 , crashoz , 45 byte
Cobalah online!
Ungkapannyasin(x) x7
x*60-x**3*10+x**5/2-x**7/84
adalah deret Taylor untuk hingga term , dikalikan dengan 60. Ini cukup akurat pada input yang digunakan, tetapi untuk nilai yang lebih tinggi, keduanya akan berbeda ketika istilah terpotong menjadi lebih relevan.x 7sumber
JavaScript (ES6), jawaban Arnauld (10 byte)
Cobalah online!
sumber
Haskell , jawaban Laikoni ,
2622 byte-4 byte dengan tidak menggunakan infix
div
, terima kasih kepada Laikoni !Cobalah online!
Penjelasan
Untuk istilah ini dapat ditulis ulang karena memberi kita cukup byte untuk mencocokkan pola pada yang mengarah ke celah dalam 28 byte:n > 200≤n≤20 n>20
ceiling(realToFrac n/2)
div(n+1)2
sumber
((n+1)`div`2)
->div(n+1)2
.> <> , jawaban crashoz 203 byte
Cobalah online!
Saya akan melakukan sesuatu yang pintar dengan fakta bahwa angka ganjil / genap di atas
n=20
adalah sama kecuali untuk elemen berulang di tengah, tetapi lebih mudah untuk hanya kode yang keras setiap elemen.Input melalui
-v
flag. Mencetak apa pun untuk elemen di atas 34.sumber
Pascal (FPC) , jawaban AlexRacer , 80 byte
Cobalah online!
Ketika output identik, tetapi ketika kode di atas mengeluarkan , sedangkan kode AlexRacer menghasilkan .n = 128 127 1260≤n≤120 n=128 127 126
Ini sepertinya jawaban yang terlambat, tapi terima kasih @AlexRacer untuk puzzle yang bagus!
sumber
JavaScript, jawaban fəˈnɛtɪk (12 byte)
Ini berfungsi untuk nilai yang diberikan tetapi gagal untuk banyak nilai lainnya (misalnya ) karena kesalahan presisi.x=6
Pengujian
Atau, Coba online!
sumber
JavaScript, jawaban fəˈnɛtɪk (17 byte)
Anda dapat melihat di tautan TIO atau dalam hasil Stack Snippet bahwa gagal untuk entri yang lebih tinggi dari .15
Jika akurasi hanya diperlukan untuk (nilai pertama ), maka akan berfungsi juga untuk 16 byte.15n≤14 15
x=>Math.exp(x)|1
Pengujian
Atau, Coba online!
sumber
Sekam , memecahkan 5 byter BMO dengan
32 byte-1 terima kasih kepada BMO (
LdΣ
->LΣ
karena, ketika diberiTnum
,L
melakukan "panjang representasi string")Cobalah online!
Panjang digital dari angka segitiga * cocok kemudian berbeda pada ... saat menghasilkan sedangkan menghasilkan .a ( 24 ) 3 4a(0)⋯a(23) a(24)
3 4
LΣ
←d+16
* Di mana memiliki panjang digital (bukan )1 0T(0)=0 1 0
sumber
L
danLd
setara penghematan Anda byte;)L
menimpa sebagai "length of string Representation"Tnum
.> <> , Jawaban Aiden F. Pierce , 36 byte
Cobalah online!
Solusi lain dengan setiap nilai hardcoded per baris. Karena jawaban asli sebagian besar juga berupa kode, saya tidak merasa terlalu bersalah tentang ini.
sumber
JavaScript, jawaban fəˈnɛtɪk , 23 byte
Mengembalikan untuk .n ≥ 140 n≥14
Cobalah online!
Bagaimana?
Ekspresi
`${73211e9}`
diperluas ke string"73211000000000"
, memberikan tabel pencarian dari 14 nilai yang dikurangi dari 14, yang memberikan urutan yang diharapkan.Untuk , hasilnya adalah:n≥14
21 byte
Pengembaliann≥14
NaN
untuk , yang mungkin atau mungkin tidak dianggap sebagai output yang valid.Cobalah online!
sumber