Tujuan dari tantangan ini adalah untuk menemukan mustahil pelaksanaan singkat dari fungsi berikut p
, dalam bahasamu yang Anda pilih. Ini adalah kode C yang mengimplementasikannya (lihat
tautan TIO ini yang juga mencetak hasilnya) dan halaman wikipedia yang memuatnya .
unsigned char pi[] = {
252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,
233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,
249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,
5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,
235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,
181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,
21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,
50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,
223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,
224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,
167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,
173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,
7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,
225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,
32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,
89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182,
};
unsigned char p(unsigned char x) {
return pi[x];
}
apa yang p
p
adalah komponen dari dua standar kriptografi Rusia, yaitu fungsi hash Streebog dan blok cipher Kuznyechik . Dalam artikel ini (dan selama pertemuan ISO), para desainer algoritma ini mengklaim bahwa mereka menghasilkan array pi
dengan memilih permutasi 8-bit acak.
Implementasi "Tidak Mungkin"
Ada permutasi pada 8 bit. Oleh karena itu, untuk permutasi acak yang diberikan, program yang mengimplementasikannya tidak diharapkan membutuhkan kurang dari 1683 bit.
Namun, kami telah menemukan beberapa implementasi kecil yang tidak normal (yang kami sebutkan di sini ), misalnya program C berikut:
p(x){unsigned char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",l=0,b=17;while(--l&&x^1)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
yang hanya berisi 158 karakter dan dengan demikian cocok dalam 1264 bit. Klik di sini untuk melihat bahwa itu berfungsi.
Kami berbicara tentang implementasi pendek yang "tidak mungkin" karena, jika permutasi adalah output dari proses acak (seperti yang diklaim oleh perancang), maka program yang singkat ini tidak akan ada (lihat halaman ini untuk lebih jelasnya).
Implementasi referensi
Versi yang lebih mudah dibaca dari kode C sebelumnya adalah:
unsigned char p(unsigned char x){
unsigned char
s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
if(x != 0) {
unsigned char l=1, a=2;
while(a!=x) {
a=(a<<1)^(a>>7)*29;
l++;
}
unsigned char i = l % 17, j = l / 17;
if (i != 0) return 252^k[i]^s[j];
else return 252^k[j];
}
else return 252;
}
Tabelnya k
sedemikian sehingga k[x] = L(16-x)
, di mana L
linear dalam arti itu L(x^y)==L(x)^L(y)
, dan di mana, seperti dalam C, ^
menunjukkan XOR. Namun, kami tidak berhasil memanfaatkan properti ini untuk mempersingkat implementasi kami. Kami tidak mengetahui adanya struktur di s
mana dapat memungkinkan implementasi yang lebih sederhana --- outputnya selalu di subfield, yaitu mana eksponensial dilakukan di bidang hingga. Tentu saja, Anda benar-benar bebas menggunakan ekspresi yang lebih sederhana jika Anda menemukannya!s
Loop sementara sesuai dengan evaluasi logaritma diskrit di bidang hingga dengan 256 elemen. Ini bekerja melalui pencarian brute-force sederhana: variabel dummy a
diatur untuk menjadi generator dari bidang yang terbatas, dan itu dikalikan dengan generator ini hingga hasilnya sama dengan x
. Ketika itu terjadi, kita memiliki itu l
adalah log diskrit x
. Fungsi ini tidak didefinisikan dalam 0, maka kasus khusus sesuai dengan if
pernyataan tersebut.
Perkalian oleh generator dapat dilihat sebagai perkalian oleh dalam yang kemudian direduksi modulo polinomial . Peran dari ini adalah untuk memastikan bahwa variabel tetap pada 8 bit. Atau, kita bisa menggunakan , dalam hal ini bisa menjadi (atau tipe integer lainnya). Di sisi lain, perlu untuk memulai karena kita perlu memiliki ketika sama dengan 1.unsigned char
a
a=(a<<1)^(a>>7)*(256^29)
a
int
l=1,a=2
l=255
x
Rincian lebih lanjut tentang sifat-sifat p
disajikan dalam makalah kami , dengan penulisan sebagian besar optimasi kami untuk mendapatkan implementasi singkat sebelumnya.
Aturan
Usulkan program yang mengimplementasikan fungsi p
dalam waktu kurang dari 1683 bit. Semakin pendek program, semakin abnormal, untuk bahasa tertentu, semakin pendek lebih baik. Jika bahasa Anda memiliki Kuznyechik, Streebog atau p
sebagai builtin, Anda tidak dapat menggunakannya.
Metrik yang kami gunakan untuk menentukan implementasi terbaik adalah panjang program dalam byte. Kami menggunakan bit-length dalam makalah akademis kami, tetapi kami tetap pada byte di sini demi kesederhanaan.
Jika bahasa Anda tidak memiliki gagasan yang jelas tentang fungsi, argumen, atau keluaran, penyandian terserah Anda untuk menentukan, tetapi trik seperti penyandian nilai pi[x]
seperti x
yang jelas-jelas dilarang.
Kami telah mengirimkan makalah penelitian dengan temuan kami tentang topik ini. Ini tersedia di sini . Namun, jika diterbitkan di tempat ilmiah, kami dengan senang hati akan mengakui penulis implementasi terbaik.
Omong-omong, terima kasih kepada xnor atas bantuannya saat menyusun pertanyaan ini!
sumber
1683 bits at most
pembatasan ketat atau tujuan?Jawaban:
AMD64 Assembly (78 byte atau 624 bit kode mesin)
Perakitan x86 64-bit
Kode 64-bit dibongkar
Perakitan x86 32-bit
Bongkar kode 32-bit
sumber
uint8_t
args diperpanjang nol menjadi 64-bit untuk JRCXZ). Juga, jika Anda menulis kode tergantung posisi, Anda dapat memasukkan alamat tabel ke register dengan 5-bytemov ebx, imm32
alih - alih 6-bytecall
/pop
. Atau gunakan itu sebagaidisp32
dimov al, [table + rax]
, tetapi itu mungkin hilang karena Anda sudah punya duaxlatb
danmov
sudah. Trik panggilan + pop shellcode memang menang vs 7 byte RIP-relatif LEA dengan data setelahret
, meskipun.CJam ,
72676663 bytees*
mengulangi sesuatu dengan cap waktu saat ini, yang merupakan angka besar, dan akan memakan waktu terlalu lama untuk selesai.Sebenarnya versi yang dapat diuji, 64 byte:
Cobalah online!
Coba semua online!
Untuk menjalankan kode ini (pada mesin Linux), Anda perlu menambahkan baris
en_US.ISO-8859-1 ISO-8859-1
ke/etc/locale.gen
dan jalankanlocale-gen
. Maka Anda bisa menggunakan:Atau Anda dapat mencoba versi UTF-8 72 byte yang setara ini:
Penjelasan
Karakter dalam string adalah:
sumber
"Ý0$&Ü™ÖD�’\n˜×EO“N"
?Jelly
7159 byteCobalah online!
Verifikasi semua kemungkinan
Sekarang ditulis ulang menggunakan versi CJam pintar jimmy23013 yang dikerjakan ulang jadi pastikan untuk mengunggahnya juga! Hanya menggunakan 472 bit (28,0% dari pendekatan naif). @ jimmy23013 juga menyimpan byte lain!
Penjelasan
Tahap 1
Tahap 2
Tahap 3
Pendekatan asli
Jelly ,
7166 byteCobalah online!
Verifikasi semua kemungkinan
Tautan monadik atau program lengkap yang mengambil argumen tunggal dan mengembalikan nilai yang relevan
pi[x]
. Ini adalah 536 bit, jadi di bawah sepertiga penyimpanan pi naif.Disimpan 3 byte dengan menggunakan metode untuk menemukan
l
dari jawaban CJam jimmy23013 jadi pastikan untuk meng-upgrade yang juga!Penjelasan
Tahap 1
Tahap 2
Tahap 3
sumber
C (gcc) ,
157 148 140139 bytePerbaikan sederhana dibandingkan contoh C.
Cobalah online!
C (gcc) ,
150 142 127126 byteYang ini tergantung pada kebiasaan gcc dan x86 dan UTF-8.
Cobalah online!
Berkat @XavierBonnetain untuk -1 dan perilaku yang kurang terdefinisi.
sumber
05AB1E ,
10110098979594 byte-3 byte terima kasih kepada @Grimy .
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
Port fungsi Xavier Bonnetain C (versi 1106 bit) dari sini , dengan peningkatan yang sama dengan @ceilingcat yang dibuat dalam jawaban C-nya untuk menghemat 3 byte, jadi pastikan untuk membesarkannya!
Lihat ini ujung 05AB1E saya (bagian Cara kompres bilangan bulat besar? Dan Cara kompres daftar bilangan bulat? ) Untuk memahami mengapa
•α">η≠ε∍$<Θγ\&@(Σα•
adalah20576992798525946719126649319401629993024
;•α">η≠ε∍$<Θγ\&@(Σα•₅в
adalah[64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]
;Ƶ¹
adalah285
;•¾#kôlb¸ù,-ó"a·ú•
adalah930891775969900394811589640717060184
;•¾#kôlb¸ù,-ó"a·ú•₅в
adalah[189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]
; danƵ∞
adalah188
.sumber
s^
=>^
(XOR komutatif). Sebenarnya, tidaks^_
sama denganQ
?i==0 || X==0 || X==1
.Stax ,
6564625958 byteJalankan dan debug itu
Sayangnya, program ini menggunakan beberapa instruksi yang secara internal menggunakan beberapa instruksi stax yang sudah usang. Saya hanya lupa untuk memperbarui implementasinya. Ini menyebabkan beberapa peringatan palsu muncul, tetapi hasilnya masih benar.
Ini terinspirasi oleh jawaban jimmy23013 yang luar biasa . Beberapa bagian telah diubah agar sesuai dengan stax lebih baik.
Program Stax yang ditulis dalam ASCII yang dapat dicetak memiliki representasi alternatif yang menghemat sedikit lebih dari 1 bit per byte, karena hanya ada 95 karakter ASCII yang dapat dicetak.
Berikut representasi ascii dari program ini yang diformat untuk "keterbacaan" dengan komentar.
Jalankan yang ini
Versi modifikasi untuk dijalankan untuk semua input 0..255
sumber
S
power set. Anda bisa mendapatkan set daya [18 38 36 48], indeks dan kurangi dengan xor. (Saya tidak tahu Stax dan saya tidak yakin itu akan lebih pendek.)S
operator tidak dalam urutan yang tepat untuk itu berfungsi. mis."abc"SJ
(powerset dari "abc" bergabung dengan spasi) menghasilkan "a ab abc ac b bc c".Python 3 , 151 byte
Cobalah online!
Fungsi yang mengimplementasikan permutasi. Kode hanya menggunakan karakter ASCII 7-bit.
Dikodekan
k
sebagai bytestring Python 3, bergeser^64
ke kisaran yang dapat dicetak. Sebaliknya,s
dikodekan sebagai basis-256 digit dari konstanta numerik, dan digit diekstraksi sebagai[number]>>[shift]*8&255
. Ini lebih pendek daripada penyandians
dalam string karena jumlah karakter melarikan diri yang diperlukan ini, bahkan dengan pergeseran yang optimal^160
untuk meminimalkan mereka.Perhitungan diskrit-log dilakukan mundur. Pembaruan
x=x*2^x//128*285
loop maju dalam grup siklik dengan mensimulasikan mengalikan dengan menghasilkan, sampai mencapai identitasx=1
. Kami memulai log diskrit dil=255
(panjang siklus), dan mengurangi setiap iterasi. Untuk menanganix=0
kasing dan membuatnya tidak berulang, kami juga mengakhiri kapanl=0
, yang membuatx=0
peta menjadil=0
seperti yang ditentukan.Python 2 kalah karena tidak memiliki bytestrings yang bagus, jadi perlu kita lakukan
map(ord,...)
(ArBo menyimpan byte di sini). Itu memungkinkan kita menggunakan/
daripada//
untuk pembagian integer.Python 2 , 156 byte
Cobalah online!
sumber
JavaScript (ES6), 139 byte
Mirip dengan versi Node.js, tetapi menggunakan karakter di luar rentang ASCII.
Cobalah online!
JavaScript (Node.js) ,
149148 byteBerdasarkan implementasi C Xavier Bonnetain (yang disajikan di sini ).
Cobalah online!
Pengkodean
Dalam jawaban asli Xavier, tabel
s[]
dank[]
disimpan dalam string berikut:17 karakter pertama adalah representasi ASCII
k[i] XOR 64
dan 15 karakter berikutnya adalah representasi ASCIIs[i-17] XOR 173
, ataus[i-17] XOR 64 XOR 17 XOR 252
.k[i] XOR 64
s[i-17] XOR 173
Inilah yang kami dapatkan:
110010011001001
NB: Ini hanya catatan tambahan, tidak terkait dengan jawaban di atas.
Cobalah online!
sumber
C # (Visual C # Interactive Compiler) , 141 byte
Hanya port dari solusi contoh, porting ke C #.
Cobalah online!
sumber
Python 3 , 182 byte
Cobalah online!
Python tidak akan memenangkan hadiah pertama di sini, tapi ini masih 10 byte golf dari program Python terbaik di sini .
Python 3 , 176 byte
Cobalah online!
Sebagai lambda, ini masih enam byte lebih pendek. Sangat menyakitkan saya harus menggunakan
if... else
, tapi saya tidak melihat opsi lain untuk hubungan arus pendek, mengingat bagaimana 0 adalah jawaban yang mungkin.Python 3 , 173 byte
Cobalah online!
Bahkan lebih pendek dalam byte (meskipun saya tidak yakin tentang bit, karena ini bukan ASCII murni lagi), milik ovs.
sumber
\x..
lolosRust ,
170163 byteCobalah online!
Ini adalah port solusi saya dalam C, dengan string yang sedikit berbeda, yang tidak perlu untuk xor 17. Saya berharap bahwa sebagian besar solusi berdasarkan string "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "dapat ditingkatkan juga (cukup ganti string, hapus xor 17, dan xor 173 alih-alih 188).
Saya dihapus salah satu pencarian dengan kondisional menambahkan
17*17
untukl
, seperti yang kita (kurang lebih) lakukan di solusi ARM kode mesin.Karat memiliki tipe inferensi dan penutup, tetapi gipsnya (bahkan untuk boolean atau antara bilangan bulat) selalu eksplisit, kemampuan berubah harus ditandai, ia tidak memiliki operator ternary, operasi integer, secara default, panik pada overflow, dan operasi bermutasi (
l+=1
) mengembalikan unit. Saya tidak berhasil mendapatkan solusi yang lebih pendek dengan iterator, karena penutupan + pemetaan masih cukup bertele-tele.Ini sepertinya membuat Rust pilihan yang buruk untuk bermain golf. Namun demikian, bahkan dalam bahasa yang menekankan keterbacaan dan keamanan daripada keringkasan, kita terlalu pendek.
Pembaruan: menggunakan fungsi anonim, dari saran manatwork.
sumber
let p=
ke Header dan tidak menghitungnya. Tidak yakin tentang;
, karena untuk panggilan anonim tidak diperlukan: Cobalah online! .05AB1E , 74 byte
Port jawaban pertama Jelly @NickKennedy . Saya sedang mengerjakan port dari jawaban @ jimmy23013 CJam secara langsung , tetapi saya sudah mencapai 78 byte dan masih harus memperbaiki bug, jadi itu akan lebih besar. Ini pasti masih bisa golf sedikit.
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
Lihat ini ujung 05AB1E saya (bagian Cara kompres bilangan bulat besar? Dan Cara kompres daftar bilangan bulat? ) Untuk memahami mengapa
Ƶf
adalah142
;•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•
adalah29709448685778434533295690952203992295278432248
,ƵŠ
adalah239
; dan•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠв
adalah[19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
.sumber