Golf Kode ini terinspirasi oleh artikel Harian WTF, You Can't Handle the True! , yang menampilkan perbandingan string yang ditulis sebagai:
String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())
Bayangkan masalah yang akan ditimbulkan tim Steve jika String.hashCode
metode Java kebetulan diterapkan dengan cara seperti itu "YES".hashCode() == "NO".hashCode()
. Jadi, tantangan yang saya usulkan di sini adalah:
Tulis, sesedikit mungkin karakter, fungsi hash (saya akan menyebutnya
h
) dengan parameter string dan nilai pengembalian integer, sehinggah("YES")
sama denganh("NO")
.
Tentu saja, ini akan sepele untuk dilakukan dengan fungsi seperti def h(s): return 0
, yang membuat tabrakan hash untuk setiap string. Untuk membuat tantangan ini lebih menarik, Anda harus mematuhi aturan tambahan berikut:
Dari lain 18 277 string mungkin terdiri dari tiga atau lebih sedikit huruf ASCII huruf besar (
^[A-Z]{0,3}$
), harus ada ada tabrakan hash.
Klarifikasi (ditunjukkan oleh Heiko Oberdiek): String input dapat berisi karakter selain A-Z
, dan kode Anda harus dapat hash string sewenang-wenang. (Anda dapat, bagaimanapun, menganggap bahwa input adalah string karakter daripada pointer nol atau objek dari beberapa tipe data lainnya.) Namun, tidak masalah apa nilai pengembalian untuk string yang tidak cocok ^[A-Z]{0,3}$
, selama itu adalah bilangan bulat.
Selanjutnya, untuk mengaburkan maksud fungsi ini:
Kode Anda tidak boleh menyertakan huruf 'Y', 'E', 'S', 'N', atau 'O' (dalam huruf besar atau kecil) dalam karakter atau string literal.
Tentu saja, pembatasan ini tidak berlaku untuk kata kunci bahasa, sehingga else
, return
, dll baik-baik saja.
YESNO
untuk memeriksa pengecualian khusus ini.Jawaban:
GolfScript: 19 karakter (24 karakter untuk fungsi bernama)
Ini adalah fungsi tubuh. Menugaskannya ke fungsi bernama
h
membutuhkan lima karakter lagi:(Tanda titik koma terakhir dapat dihilangkan, jika Anda tidak keberatan meninggalkan salinan kode di tumpukan.)
Inti dari fungsi hash adalah
26base
, yang menghitung jumlah (26 n - k · a k ; k = 1 .. n ), di mana n adalah jumlah karakter dalam input dan sebuah k menunjukkan kode ASCII dari k th karakter input. Untuk input yang terdiri dari huruf ASCII huruf besar, ini adalah fungsi hash bebas tabrakan. Sisa kode membandingkan hasilnya dengan 2107 (kode hashNO
) dan, jika sama, menambah 59934 untuk menghasilkan 2701 + 59934 = 62041, kode hashYES
.Sebagai contoh keluaran, lihat demo online ini dengan test case.
sumber
h('DXP') == h('KK') == 65884
.lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983
)32-bit Python 2.x (19)
RSA menggunakan modulus semiprime, dan itu membuatnya aman, jadi menggunakan satu dengan algoritma hash saya pasti akan membuatnya lebih baik! 1
Ini adalah fungsi matematika murni, bekerja untuk semua string (neraka, bekerja untuk objek Python hashable), dan tidak mengandung persyaratan atau casing khusus! 32-bit Python biasanya dapat disebut sebagai
python-32
pada kebanyakan sistem yang keduanya menginstal 2 .Saya telah menguji ini, dan mengembalikan 18.278 nilai yang berbeda untuk string huruf besar 18.279 atau kurang. Menugaskan ini ke suatu fungsi membutuhkan 11 byte lebih:
dan
h('YES') == h('NO') == 188338253
.64-bit Python 2.x (19)
Kesepakatan yang sama seperti di atas.
Untuk menghasilkan angka-angka ini, sedikit matematika modular digunakan. Saya sedang mencari fungsi
f
dan modulusn
sedemikian rupahash(f('YES')) % n == hash(f('NO')) % n
. Ini setara dengan pengujian yangn
membagid = hash(f('YES')) - hash(f('NO'))
, yaitu kita hanya perlu memeriksa faktord
untuk nilai yang sesuain
.Yang ideal
n
ada di sekitar 20000 ** 2 untuk mengurangi kemungkinan tabrakan paradoks ulang tahun. Menemukan yang cocokn
ternyata sedikit trial and error, bermain dengan semua faktord
(biasanya tidak banyak) dan pilihan yang berbeda untuk fungsi tersebutf
. Perhatikan bahwa coba-coba hanya diperlukan karena saya ingin membuatn
sekecil mungkin (untuk bermain golf). Jika itu bukan persyaratan, saya hanya bisa memilihd
modulus saya, yang biasanya cukup besar.Perhatikan juga bahwa Anda tidak dapat melakukan trik ini hanya dengan menggunakan
f(s) = s
(fungsi identitas) karena karakter paling kanan dari string pada dasarnya memiliki hubungan linier (sebenarnyaXOR
hubungan) dengan hash terakhir (karakter lain berkontribusi dalam cara yang jauh lebih nonlinear ). Oleh karena itu, pengulangan string memastikan bahwa perbedaan antara string diperkuat untuk menghilangkan efek mengubah hanya karakter paling kanan.1 Ini omong kosong paten.
2 hashing string Python tergantung pada versi utama (2 vs 3) dan bitness (32-bit vs 64-bit). Itu tidak tergantung pada platform AFAIK.
sumber
hash('YES'*9)
memiliki34876679
sebagai faktor, sementarahash('NO'*9)
memiliki34876679+537105043
sebagai faktor. Tapi bagaimana Anda tahu537105043
itu modulus yang bagus? yaitu tidak membuat tabrakan lainnya?Perl,
534940 byteUji:
Nilai hash untuk
YES
danNO
sama dan ada 18279 string^[A-Z]{0,3}$
, yang bebas benturan kecuali untuk satu-satunya tabrakan untukYES
danNO
.Tidak Disatukan:
Versi yang lebih lama, 49 byte
Karena algoritma baru sedikit berbeda, saya tetap menggunakan versi yang lama.
Uji:
Tidak Disatukan:
Suntingan:
"\0"
sebagai byte mengisi menghemat 4 byte dibandingkan dengan$"
.sumber
5457241
dan20047
berasal? Bagaimana Anda menghitung angka-angka ini? Terima kasih sebelumnya.YES
dalam hex adalah594553
. 0x594553 = 5850451.NO
dalam hex adalah4e4f
. 0x4e4f = 20047.Python: 63
Solusi yang sangat timpang:
Ini bekerja dengan mengartikan string alfanumerik sebagai angka base-36, dan mengembalikan 0 untuk yang lainnya. Ada kasus khusus yang eksplisit untuk memeriksa nilai kembali 852 (TIDAK), dan mengembalikan 44596 (YA) sebagai gantinya.
sumber
try:
dan seluruh baris ketiga. Anda juga dapat menyimpan beberapa gigitan dengan membuat setiap baris logis pada baris aktual yang sama, dipisahkan oleh tanda titik koma (def h(s):r=int(s,36);return(r,44596)[r==852]
)Pure Bash, 29 byte (badan fungsi)
Ini hanya memperlakukan string input sebagai nomor basis 36 dan mengubahnya menjadi desimal, kemudian berurusan dengan
NO
case khusus .Keluaran:
sumber
Ruby, 51 byte
kode pengujian:
keluaran:
sumber
Javascript ( ES6 ) 54 byte
sumber
Jawa -
9477Belum dibuka:
Narasi - untuk
f(s) = BigInteger(s.getBytes())
:f("YES") xor f("NO") = 5835548
f("YES") xor 5835548 = f("NO")
f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)
saya benar?sumber
CJam, 15 byte
Berfungsi sebagai solusi GolfScript di bawah ini. Cobalah online.
GolfScript, 17 byte
Pendekatan ini dibangun berdasarkan jawaban nneonneo dan Ilmari Karonen .
Bagaimana itu bekerja
Memilih algoritma
Kita mulai dengan
{b base}:h
, yaitu, string input dianggap sebagai nomor basis-b. Selamab > 25
,h
adalah inyective.Kami mendapatkan tabrakan untuk string "YA" dan "TIDAK" jika kami memodifikasi
h
dengan cara berikut:, di{x base n}:h
manan
adalah pembagi"YES" h "NO" h -
.Sayangnya, ini berarti kami juga akan mendapatkan tabrakan untuk, misalnya,
YET
danNP
. Untuk mencegah hal ini, kita harus memodifikasi basa basis-b secara non-linear sebelum mengambil modulus.Cara terpendek untuk mencapai hal ini dalam GolfScript adalah mengalikan nomor basis-b dengan dirinya sendiri (yaitu, mengkuadratkannya).
h
sekarang{base b .* n %}:h
.Yang harus dilakukan hanyalah menemukan nilai yang sesuai untuk
b
dann
. Kita bisa mencapai ini dengan kekerasan:Nilai terpendek yang mungkin untuk
b n
adalah:Pengujian
sumber
JavaScript (ES6) - 38 karakter (33 fungsi char)
Kasus uji:
Penjelasan:
Pertama-tama, izinkan saya memperkenalkan Anda kepada
NaN
- "Bukan Angka" - dalam JavaScript. Ini nomor:Seperti:
Properti khususnya adalah bahwa ia tidak pernah sama dengan dirinya sendiri . Fungsi saya kembali
1
jika string adalahYES
atauNO
, danNaN
untuk string lainnya.Jadi, ini tidak melanggar aturan, karena tidak akan ada tabrakan hash untuk string lain;) (
NaN !== NaN
ditunjukkan di atas dalam kasus uji).Dan impian saya menjadi kenyataan: mengalahkan Bash, Perl dan Ruby dalam kode panjangnya!
Kode Tidak Terkunci:
Jika nilai itu
"WUVT"
atau"Tk8="
, kembali1
. Lain, kembaliyang akan menjadi
NaN
.sumber
^\d+$
. Dan JS memperlakukanNaN
sebagai angka. Anda dapat mengalikannya dengan angka, menambah, membagi, mengurangi seperti halnya dengan angka. Ini adalah properti khusus JavaScript. Tidak ada salahnya menggunakannya. Itulah yang kami sebut pelengkungan aturan ;)Object.is()
dan mengklaim itu masih tabrakan ...==
) untuk perbandingan, yang akan menjamin tidak ada tabrakan hash untuk string apa pun selain "YA" atau "TIDAK".NaN
tidak dianggap sebagai tabrakan tampaknya murah, solusi ini memiliki tabrakan dengan stringNA
melaluiNP
danYEQ
melaluiYET
Python 92
Fungsi hashing menyatukan nilai-nilai ordinal karakter ASCII, pernyataan cetak memastikan bahwa dua input yang diinginkan bertabrakan.
sumber
ECMAScript 6 (30 byte)
Saya sudah mencoba menghindari penugasan variabel, pengembalian, dan kata kunci fungsi, dan ini terlihat seperti cara yang bagus untuk menghindari semua omong kosong itu (ini juga terlihat seperti pemrograman fungsional, dengan cara). Tidak seperti solusi lain, itu tidak bergantung pada
btoa
atauatob
, yang bukan ECMAScript 6, tetapi HTML5.0+
diperlukan, sehingga bisa mengurai string sewenang-wenang.sumber
a=>parseInt(0+a,36)-852||43744
Java - 45 (atau 62?)
Saya tidak tahu bagaimana cara menilai secara adil mengingat apa yang dibutuhkan seseorang untuk menjalankan suatu program di Jawa, apakah saya perlu memasukkan definisi fungsi? Merasa bebas untuk mengedit dan menyesuaikan skor saya dengan tepat. Saat ini saya mencetak dengan cara yang sama dengan jawaban @OldCurmudgeon. Tambahkan 17
int h(String t){}
jika diperlukan:Tidak diikat dengan test harness:
sumber
Dan yang lebih longgar adalah ...
Conveyor, 145 karakter
Pada dasarnya program ini melakukan beberapa hal berbasis 26 pada karakter. Setelah itu memeriksa apakah hash sama dengan 12999 (Kode hash YA) dan jika demikian cetak 404 (kode hash TIDAK), kalau tidak hash hanya akan mencetak kode hash.
Conveyor adalah bahasa yang dibuat oleh saya yang saat ini masih dalam tahap beta tetapi seorang juru bahasa beserta beberapa contoh dan kode sumber dapat ditemukan di sini: https://github.com/loovjo/Conveyor
sumber
C # 4.5 (112 byte)
Bekerja (?) Versi upayamonmon bawah tanah, dalam C #. Concats byte dalam string menjadi integer 32-bit (hanya bekerja hingga 4 karakter), lalu ATAU hasilnya terhadap hasil untuk "YA" dan "TIDAK" masing-masing, lalu ATAU yang bersama-sama.
Meskipun mungkin bertabrakan di beberapa titik, itu tidak boleh terjadi untuk ^ ^ [AZ] $ 2,2 selain $ "YA" dan "TIDAK".
sumber
Tidak Ada Komentar - 31 (konten fungsi: 26)
Solusi yang cukup sederhana. ;) Bekerja untuk semua dan semua string UTF-8.
PENJELASAN:
'
jelas, fungsinya. Pertama, ia memeriksa apakah*
(inputnya) sama dengan|,,|+|"#|
(|NO|
). Jika ya, ia mengembalikan|, |+|-%3|
(|YES|
) - jika tidak, ia hanya mengembalikan*
.sumber
C 54
Konversikan string ke integer - "TIDAK" dan kalikan dengan nilai yang sama + "TIDAK" - "YA" untuk mendapatkan 0 untuk "TIDAK" dan "YA" dan bukan-nol untuk string lain dalam rentang yang ditentukan.
Semua nilai pada mesin Windows 7 jika ada masalah endian.
sumber
Stax ,
1211 byteJalankan dan debug itu
Menerjemahkan input sebagai basis-36, kurangi 852, lalu ganti 0 dengan 43744. Ini adalah port solusi terbaik Konrad .
sumber
CoffeeScript - 36
Harus kembali
1
untukYES
danNO
, dan omong kosong kacau apa punatob
menghasilkan untuk segala sesuatu yang bukan string base64.Setara dengan JavaScript ( bukan kode JS dari kompiler CS):
sumber
_
ketika input bukan "YA" atau "TIDAK".Ini yang super lumpuh. BEGITU LAME ITU TIDAK BEKERJA
Python 2.7 - 79 bytePertama kita mendapatkan jumlah (nilai ascii masing-masing karakter) * 100 ^ (posisi karakter dalam string). Kemudian kita mengalikan (hasil itu - 7978) dan (hasil itu - 836989) untuk mendapatkan jawaban akhir kita. 7978 dan 836989 adalah hasil untuk "YA" dan "TIDAK" dari bit pertama, jadi untuk YA dan TIDAK kita mengalikan dengan 0.
Ini seharusnya tidak memiliki tabrakan? Saya tidak merasa ingin menguji terhadap 18000 contoh tandingan yang mungkin, tetapi jika ada tabrakan yang tidak disengaja saya bisa melempar 0 lagi pada itu
100
dan kemudian benar-benar ada - tidak boleh ada tabrakan.Kecewa karena saya tidak bisa menggunakan a
lambda
untuk ini, tetapi saya tidak ingin melakukan seluruh perhitungan dua kali jadi saya harus menyimpannya ke variabel.Tolong jangan biarkan ini menang. Itu sangat timpang dan aku tidak pantas mendapatkannya.
sumber