Tantangan
Tantangan "mata-mata versus mata-mata" yang sederhana.
Tulis program dengan spesifikasi berikut:
- Program dapat ditulis dalam bahasa apa pun tetapi tidak boleh melebihi 512 karakter (seperti yang diwakili dalam blok kode di situs ini).
- Program harus menerima 5 bilangan bulat 32-bit yang ditandatangani sebagai input. Ini dapat mengambil bentuk fungsi yang menerima 5 argumen, fungsi yang menerima array 5-elemen tunggal, atau program lengkap yang membaca 5 bilangan bulat dari input standar apa pun.
- Program harus mengeluarkan satu bilangan bulat 32-bit yang sudah ditandatangani.
- Program harus mengembalikan 1 jika dan hanya jika lima input, ditafsirkan sebagai urutan, cocok dengan urutan aritmatika tertentu dari pilihan programmer, yang disebut "kunci". Fungsi harus mengembalikan 0 untuk semua input lainnya.
Urutan aritmatika memiliki sifat bahwa setiap elemen berurutan sama dengan pendahulunya ditambah beberapa konstanta tetap a
.
Sebagai contoh, 25 30 35 40 45
adalah urutan aritmatika karena setiap elemen urutan sama dengan pendahulunya ditambah 5. Demikian juga, 17 10 3 -4 -11
adalah urutan aritmatika karena setiap elemen sama dengan pendahulunya ditambah -7.
Urutan 1 2 4 8 16
dan 3 9 15 6 12
bukan urutan aritmatika.
Kunci dapat berupa urutan aritmatika yang Anda pilih, dengan batasan tunggal bahwa urutan yang melibatkan bilangan bulat bilangan bulat tidak diizinkan. Artinya, urutannya harus benar-benar meningkat, sangat menurun, atau memiliki semua elemen yang sama.
Sebagai contoh, misalkan Anda memilih kuncinya 98021 93880 89739 85598 81457
. Program Anda harus mengembalikan 1 jika input (sesuai urutan) cocok dengan lima angka ini, dan 0 sebaliknya.
Harap dicatat bahwa cara melindungi kunci harus dari desain novel Anda sendiri. Juga, solusi probabilistik yang dapat mengembalikan false positive dengan probabilitas bukan nol tidak diizinkan. Khususnya, jangan gunakan hash kriptografi standar, termasuk fungsi pustaka untuk hash kriptografi standar.
Skor
Pengajuan non-retak terpendek per jumlah karakter akan dinyatakan sebagai pemenang.
Jika ada kebingungan, jangan ragu untuk bertanya atau berkomentar.
Counter-Challenge
Semua pembaca, termasuk mereka yang telah mengirimkan program mereka sendiri, didorong untuk "memecahkan" kiriman. Kiriman retak ketika kuncinya diposting di bagian komentar terkait. Jika kiriman bertahan selama 72 jam tanpa diubah atau di-crack, itu dianggap "aman" dan setiap keberhasilan selanjutnya dalam cracking itu akan diabaikan demi kontes.
Lihat "Penafian" di bawah ini untuk perincian tentang kebijakan skor retak yang diperbarui.
Pengajuan yang retak dihilangkan dari pertikaian (asalkan tidak "aman"). Tidak boleh diedit. Jika pembaca ingin mengirimkan program baru, ia harus melakukannya dalam jawaban yang terpisah.
Para cracker dengan skor tertinggi akan dinyatakan sebagai pemenang bersama dengan pengembang dari program yang menang.
Harap jangan merusak kiriman Anda sendiri.
Semoga berhasil. :)
Papan peringkat
Klasemen Penultimate (keamanan tertunda dari pengajuan Dennis 'CJam 49).
Loker Aman
- CJam 49, Dennis
- CJam 62, Dennis aman
- CJam 91, Dennis aman
- Python 156, Maarten Baert aman
- Perl 256, aman chilemagic
- Java 468, Geobits aman
Kerupuk yang tak terhentikan
- Peter Taylor [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Dennis [Pyth 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
- Martin Büttner [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
- Tyilo [C 459, Javascript 958 *]
- freddieknets [Mathematica 67 *]
- Ilmari Karonen [Python27 182 *]
- nitrous [C 212 *]
* pengiriman yang tidak sesuai
Penafian (Diperbarui 11:15 PM EST, 26 Agustus)
Dengan masalah skor yang akhirnya mencapai massa kritis (mengingat dua pertiga dari kiriman yang retak sejauh ini tidak memenuhi persyaratan), saya telah memberi peringkat kerupuk teratas dalam hal jumlah kiriman yang retak (primer) dan jumlah total karakter dalam kiriman retak yang sesuai (sekunder).
Seperti sebelumnya, pengiriman persis retak, panjang pengiriman, dan status patuh / tidak patuh mereka semua ditandai sehingga pembaca dapat menyimpulkan peringkat mereka sendiri jika mereka percaya peringkat resmi baru itu tidak adil.
Maafkan saya karena mengubah aturan di akhir permainan.
Jawaban:
CJam, 62 karakter
Stack Exchange cenderung untuk menganiaya karakter yang tidak patut, tetapi menyalin kode dari tempel ini dan menempelkannya pada juru bahasa CJam berfungsi baik untuk saya.
Bagaimana itu bekerja
Setelah mengganti string Unicode dengan string ASCII, kode berikut ini dijalankan:
Pendekatan ini menggunakan Bivium-B (lihat analisis aljabar dari trivium-like ciphers ), versi pelemahan stream cipher Trivium .
Program ini menggunakan urutan bilangan bulat sebagai keadaan awal, memperbarui keadaan 434 kali (354 putaran mencapai difusi penuh) dan menghasilkan 177 bit output, yang dibandingkan dengan urutan yang benar.
Karena ukuran negara justru 177 bit, ini harus cukup untuk secara unik mengidentifikasi keadaan awal.
Contoh dijalankan
sumber
CJam, 91 karakter
Stack Exchange cenderung untuk menganiaya karakter yang tidak patut, tetapi menyalin kode dari tempel ini dan menempelkannya pada juru bahasa CJam berfungsi baik untuk saya.
Bagaimana itu bekerja
Setelah mengganti string Unicode dengan integer (dengan mempertimbangkan digit karakter nomor 65533 basis), kode berikut ini dijalankan:
Karena 13 adalah coprime terhadap total modulus (totalnya adalah rahasia, jadi Anda hanya perlu mempercayai saya), basis yang berbeda akan menghasilkan hasil yang berbeda, yaitu solusinya unik.
Kecuali seseorang dapat mengeksploitasi eksponen kecil (13), cara paling efisien untuk memecahkan kunci ini adalah dengan memfaktisasi modulus (lihat masalah RSA ). Saya memilih integer 512-bit untuk modulus, yang harus tahan 72 jam dari upaya faktorisasi.
Contoh dijalankan
sumber
found 1740001 rational and 1739328 algebraic entries
; karena sudah hampir 100 jam untuk memprosesnya, dan melaporkansieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Mari kita coba yang ini:
(Mengharapkan pengguna untuk memasukkan 5 angka yang dipisah koma, mis
1,2,3,4,5
.)sumber
32416190039,32416190047,32416190055,32416190063,32416190071
Jawa: 468
Input diberikan sebagai
k(int[5])
. Menalangi lebih awal jika jaraknya tidak merata. Kalau tidak, perlu sedikit mencari tahu apakah semua sepuluh hash benar. Untuk jumlah besar, "sedikit" bisa berarti sepuluh detik atau lebih, jadi itu bisa mencegah kerupuk.sumber
Jawa: 342
Berikut adalah pengunci berbasis string yang bergantung pada jumlah karakter input dan input spesifik. Urutan mungkin didasarkan pada referensi budaya pop yang tidak jelas. Selamat bersenang-senang!
Sedikit tidak ungolfed:
sumber
-8675309
, delta adalah5551212
.Python, 147
Sunting: versi lebih pendek berdasarkan komentar Dennis. Saya memperbarui urutan juga untuk menghindari kebocoran informasi.
Berdasarkan masalah logaritma diskrit yang diyakini tidak dapat dipecahkan, namun yang utama saya gunakan mungkin terlalu kecil untuk diamankan (dan mungkin memiliki masalah lain, saya tidak tahu). Dan Anda dapat dengan paksa memaksakannya, karena satu-satunya yang tidak diketahui adalah dua bilangan bulat 32-bit.
sumber
c=1
, menghitungc=(c<<32)+d
dan mengubah konstanta yang sesuai.Javascript 125
Yang ini harus cepat retak. Saya akan menindaklanjuti dengan sesuatu yang lebih kuat.
sumber
0, 3913, 7826, 11739, 15652
Ruby, 175
Tidak seperti menggunakan hash kriptografi atau
srand
, hash ini terbukti unik (yang merupakan sedikit petunjuk). Mengambil lima angka melalui STDIN, dibatasi oleh karakter atau karakter non-baris baru. Output ke STDOUT.sumber
622238809,1397646693,2173054577,2948462461,3723870345
(Dugaan saya sebelumnya memiliki kesalahan, tetapi yang ini diuji). Saya tidak berpikir ini valid, karena angka terakhir tidak cocok dengan bilangan bulat 32-bit yang ditandatangani.GolfScript (116 karakter)
Mengambil input sebagai bilangan bulat yang dipisahkan oleh ruang.
sumber
-51469355 -37912886 -24356417 -10799948 2756521
C 459 byte
ASK OLEH Tyilo - BACA EDIT DI BAWAH
Kami membutuhkan seseorang untuk menulis solusi C, bukan? Saya tidak mengesankan siapa pun dengan panjang, saya bukan pegolf. Saya harap ini tantangan yang menarik!
Saya tidak berpikir ada cara yang jelas untuk memecahkan yang ini, dan saya dengan sabar menunggu semua upaya! Saya tahu solusi ini unik. Kebingungan yang sangat minim, sebagian besar untuk memenuhi persyaratan panjang. Ini dapat diuji secara sederhana:
NB Ada arti penting
a[0]
sebagai nomor dalam dirinya sendiri, dan saya ingin melihat seseorang menunjukkannya di komentar!EDIT:
Larutan:
6174, 48216, 90258, 132300, 174342
Catatan tentang cracking:
Meskipun ini bukan metode yang digunakan (lihat komentar), saya kebetulan memecahkan sandi saya sendiri dengan bruteforce yang sangat mudah. Saya mengerti sekarang, sangat penting untuk membuat jumlahnya besar. Kode berikut dapat memecahkan setiap cipher di mana
upper_bound
batas atas diketahuia[0] + a[1] + a[2] + a[3] + a[4]
. Batas atas dalam cipher di atas adalah457464
, yang dapat diturunkan dari sistem persamaanb[]
dan beberapa kerja-algoritma. Dapat ditunjukkan itub[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.Dengan
a[0] = 6174
, lingkaran ini memecah pekerjaan saya dalam waktu kurang dari satu menit.sumber
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Berlari:
Mungkin cukup mudah retak, mungkin juga memiliki beberapa solusi.
Pembaruan: Peningkatan golf dengan melakukan apa yang disarankan Martin Büttner. Fungsi fungsi dan kunci tidak berubah.
sumber
{58871,5592,-47687,-100966,-154245}
NextPrime
bisa mengembalikan nilai negatif. Bagaimana caramu menemukannya?Python27,
283182Baiklah, saya sangat percaya pada loker saya, namun cukup lama karena saya telah menambahkan perhitungan 'sulit untuk dibalik' ke input, untuk membuatnya baik - sulit untuk dibalik.
sunting: Terima kasih kepada colevk untuk bermain golf lebih lanjut. Saya menyadari selama mengedit bahwa ada bug dan juga cacat pada algoritme saya, mungkin saya akan lebih beruntung di lain waktu.
sumber
121174841 121174871 121174901 121174931 121174961
berfungsi, tetapi hanya jika daftar[1,3,5,7]
pada baris 7 diganti[1,3,5,7,11]
.Mathematica
142146Sunting : kunci itu tidak unik, menambahkan 4 karakter, sekarang.
(Spasi dan baris baru ditambahkan agar mudah dibaca, tidak dihitung & tidak diperlukan).
Pemakaian:
sumber
256208
, delta-5
.IntegerDigits
dan kemudian faktor untuk mendapatkan kandidat untuk istilah awal dan delta.NextPrime
; jika kita memvariasikannya dengan plus atau minus satu, setidaknya salah satu dari mereka akan memberikan perdana berikutnya yang sama.Retak oleh @ Dennis dalam 2 jam
Hanya yang sederhana untuk memulai sesuatu - Saya sepenuhnya berharap ini cepat retak.
Pyth , 13
Mengambil input yang dipisahkan koma pada STDIN.
Jalankan seperti ini (-c berarti ambil program sebagai argumen baris perintah):
Memperbaiki program - Saya belum mengerti spesifikasi.
Bahasa ini mungkin terlalu esoteris untuk kompetisi ini - Jika OP berpikir begitu, saya akan menghapusnya.
sumber
1,2,3,4,5
kuncinya?97,96,95,94,93
(Saya baru saja membunuh skor retak saya.)Lua 105
Saya curiga tidak akan lama sebelum retak, tapi di sini kita mulai:
(spasi ditambahkan untuk kejelasan, tetapi bukan bagian dari perhitungan)
sumber
3, 7, 11, 15, 19
atau6, 14, 22, 30, 38
t1==0
kapanS
meningkat. Juga, kedua kondisinya homogen; jikaS
merupakan solusi, demikian pula halnyakS
.Perl - 256
Saya harus memasukkan banyak kesalahan dalam menangani logika dan ini pasti bisa diturunkan lebih banyak. Ini akan mencetak
1
ketika Anda mendapatkan lima angka yang tepat. Mudah- mudahan akan mencetak a0
untuk segala sesuatu yang lain (mungkin kesalahan atau tidak sama sekali, saya tidak tahu). Jika ada yang ingin membantu meningkatkan kode atau golf lebih banyak, jangan ragu untuk membantu!Telepon dengan:
sumber
Ruby - 130
Berdasarkan Daftar Shift Umpan Balik Linier. Input dengan argumen baris perintah.
Harus unik berdasarkan sifat LFSR. Petunjuk: naik dan semuanya positif.
Akan memberikan lebih banyak petunjuk jika tidak ada yang menyelesaikannya segera.
sumber
Ruby, 249
Harusnya menyenangkan. Siapa yang butuh matematika?
sumber
309, 77347, 154385, 231423, 308461
tapi saya rasa itu tidak unik.103, 232041, 463979, 695917, 927855
dan3, 7966741, 15933479, 23900217, 31866955
. Dan saya cukup yakin ada regex lain yang valid dengan menggunakan tambahan+
.()
atau serupa.CJam, 49 karakter
Cobalah online.
Bagaimana itu bekerja
Hasilnya akan menjadi 1 jika dan hanya jika bilangan bulat kedua adalah faktor yang pertama, yang merupakan produk dari dua bilangan prima: yang sesuai dengan urutan rahasia dan yang lain yang tidak sesuai dengan urutan yang valid. Karena itu, solusinya unik.
Memfaktorkan integer 512 bit tidak terlalu sulit, tapi saya harap tidak ada yang bisa melakukannya dalam 72 jam. Versi saya sebelumnya menggunakan bilangan bulat 320 bit telah rusak .
Contoh dijalankan
sumber
Javascript 958
Mengonversi input ke sejumlah tipe data dan melakukan beberapa manipulasi yang relevan dengan setiap tipe data di sepanjang jalan. Harus dibalik dengan mudah bagi siapa saja yang membutuhkan waktu.
sumber
320689, 444121, 567553, 690985, 814417
C, 239 (Cracked oleh Dennis)
Buka di sini untuk kiriman saya yang diperbarui.
Mungkin bisa bermain golf lebih teliti. Memang, saya belum meluangkan waktu untuk membuktikan bahwa kuncinya unik (mungkin tidak) tetapi pasti ada di urutan tabrakan hash. Jika Anda memecahkannya, silakan bagikan metode Anda :)
sumber
0 0 0 0 0
,?C, 212 oleh Orby - Cracked
https://codegolf.stackexchange.com/a/36810/31064 oleh Orby memiliki setidaknya dua kunci:
Orby meminta metode yang saya gunakan untuk memecahkannya. Fungsi p memeriksa apakah x adalah bilangan prima dengan memeriksa
x%i==0
semua i antara 2 dan x (meskipun menggunakan(x/i)*i==x
bukanx%i==0
), dan mengembalikan true jika x adalah bilangan prima. Fungsi f memeriksa bahwa semua a, b, c, d dan e adalah prima. Ia juga memeriksa apakah angka m, suatu gabungan dari representasi desimal dari e, d, c, b dan a (dalam urutan itu), adalah prima. Kuncinya adalah sedemikian rupa sehingga a, b, c, d, e, dan m semuanya prima.Green dan Tao (2004) menunjukkan bahwa ada banyak deret aritmatika bilangan prima untuk panjang k, jadi kita hanya perlu mencari urutan ini yang juga memuaskan saya sebagai prima. Dengan memakan waktu lama yang dibatasi oleh -9.223372037e + 18 dan 9.223372037e + 18, kita tahu bahwa untuk string bersambung cocok menjadi panjang, angkanya memiliki batas atas 9999. Jadi dengan menggunakan skrip python untuk menghasilkan semua urutan aritmatika dalam semua bilangan prima <10.000 dan kemudian memeriksa apakah rangkaian kebalikannya adalah prima, kita dapat menemukan banyak solusi yang mungkin.
Untuk beberapa alasan saya datang dengan positif palsu, tetapi keduanya di atas sesuai dengan program. Selain itu mungkin ada solusi di mana e negatif dan sisanya positif (p menggunakan modulus x), tetapi saya tidak mencari mereka.
Kunci yang saya berikan adalah semua urutan aritmatika tetapi skrip Orby tampaknya tidak benar-benar memerlukan input untuk menjadi urutan aritmatika, jadi mungkin ada kunci yang tidak valid juga.
sumber
MATLAB: Tampaknya tidak valid
Sangat sederhana, Anda hanya perlu menghasilkan nomor acak yang tepat.
Itu masih bisa error, tapi itu seharusnya tidak menjadi masalah.
sumber
MATLAB (dengan Symbolic Toolbox), 173 karakter
Ini bukan entri resmi dan tidak akan dihitung terhadap skor retak siapa pun, tetapi itu akan memberi Anda hak menyombongkan diri yang gila. ;)
Kotak alat simbolis hanya diperlukan untuk menangani pengurangan bilangan bulat besar.
Memaksa dengan kasar haruslah seekor anjing, tetapi jika Anda terbiasa dengan seri yang terlibat, solusinya sepele.
sumber
Python 2 (91)Sunting: Ini tidak diizinkan karena argumen untuk keunikan adalah probabilistik. Saya menyerah.
Mengambil daftar bilangan bulat sebagai input, seperti
[1,2,3,4,5]
.Loop dimaksudkan untuk beroperasi pada input dengan cara yang menjengkelkan, meninggalkan menara penjumlahan dan eksponen. Idenya seperti log diskrit, tetapi dengan komplikasi berantakan bukan kesederhanaan matematis. Mungkin kekompakan modulus adalah kerentanan, dalam hal ini saya bisa membuatnya menjadi seperti
7**58+8
.Saya tidak benar-benar tahu bagaimana saya membuktikan bahwa kunci saya adalah satu-satunya, tetapi rentang output setidaknya 10 kali lebih besar dari kisaran input, jadi mungkin? Meskipun mungkin hanya sebagian kecil dari output potensial yang dapat dicapai. Saya selalu bisa menambah jumlah digit dengan mengorbankan karakter. Saya akan menyerahkan kepada Anda untuk memutuskan apa yang adil.
Senang retak!
sumber
Mathematica - 72
Versi 2 skrip saya, dengan kunci yang sama dengan yang dimaksudkan untuk versi saya 1.
Ini pada dasarnya menghilangkan bilangan prima negatif untuk
NextPrime
.Berlari:
sumber
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 karakter
Masukkan angka seperti
1,2,3,4,5
.sumber
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
bukan angka 32-bit.Python, 78
(Retak oleh Tyilo dalam 14 menit)
Menyenangkan!
Oke, itu tidak ditampilkan dengan benar di sini :(
Mengharapkan daftar lima angka, mis. [1,2,3,4,5]
sumber
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 karakter (rusak)
Cobalah online.
Bagaimana itu bekerja
Lihat jawaban baru saya.
Contoh dijalankan
sumber
737262825 208413108 3974530688 3445680972 2916831257
bekerja tetapi bukan merupakan perkembangan aritmatika. Diperhitungkan dalam 3 jam 20 menit. Angka 512-bit tampaknya dapat dilakukan dalam 72 jam untuk $ 75 pada EC2 dua tahun lalu, jadi saya pikir itu akan aman.737262825 208413109 -320436607 -849286323 -1378136039
C, 212 (Retak)
Ini adalah ide yang sama dengan kiriman saya sebelumnya , bermain golf lebih teliti, dengan bug yang terkoreksi yang lulus 0,0,0,0,0 (Terima kasih kepada Dennis karena telah menunjukkan bug). Kompilasi dengan -std = c99.
sumber
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37