Dalam kode-tantangan ini Anda akan menulis fungsi hash dalam 140 byte 1 atau kurang dari kode sumber. Fungsi hash harus mengambil string ASCII sebagai input, dan mengembalikan integer 24-bit unsigned ([0, 2 24 -1]) sebagai output.
Fungsi hash Anda akan dievaluasi untuk setiap kata dalam kamus Inggris-Inggris 2 yang besar ini . Skor Anda adalah jumlah kata yang berbagi nilai hash dengan kata lain (tabrakan).
Skor terendah menang, dasi rusak oleh poster pertama.
Kasus cobaan
Sebelum mengirim, silakan uji skrip penilaian Anda pada input berikut:
duplicate
duplicate
duplicate
duplicate
Jika memberikan skor selain dari 4, itu buggy.
Aturan klarifikasi:
- Fungsi hash Anda harus dijalankan pada string tunggal, bukan seluruh array. Selain itu, fungsi hash Anda mungkin tidak melakukan I / O selain String input dan integer output.
- Fungsi hash bawaan atau fungsionalitas serupa (mis. Enkripsi untuk perebutan byte) tidak diizinkan.
- Fungsi hash Anda harus deterministik.
- Berlawanan dengan kebanyakan kontes lain yang mengoptimalkan secara khusus untuk input penilaian diperbolehkan.
1 Saya sadar Twitter membatasi karakter alih-alih byte, tetapi untuk kesederhanaan kita akan menggunakan byte sebagai batas untuk tantangan ini.
2 Dimodifikasi dari wbritish-huge Debian , menghilangkan kata-kata non-ASCII.
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's
? Apa yang ...?D=340275
kata-kata danR=2^24
output hash, hash acak memilikiD^2/(2*R) = 3450
pasangan bertabrakan yang diharapkan , beberapa di antaranya tumpang tindih. AdaD^3/(6*R^2) = 23
tiga kali lipat bertabrakan yang diharapkan dan jumlah tabrakan yang lebih besar yang dapat diabaikan, yang berarti tiga kali lipat ini cenderung terpisah. Ini memberikan6829
kata-kata yang diharapkan yang memiliki nilai hash, ~70
tiga kali lipat dan sisanya berpasangan. Deviasi standar diperkirakan118
, jadi mendapatkan<6200
dengan hash acak kira-kira acara 5 sigma.Jawaban:
Baiklah saya akan belajar bahasa golf.
CJam, 140 byte, 3314 kata bertabrakan
Menentukan blok (fungsi anonim). Untuk mengujinya, Anda dapat menambahkan
qN%%N*N
untuk mengambil daftar kata yang dipisahkan baris baru di stdin dan menulis daftar hash yang dipisahkan baris baru di stdout. Kode Python Setara:Pyth, 140 byte,
35353396 kata bertabrakanMenentukan fungsi bernama
y
. Untuk mengujinya, Anda dapat menambahkanjmyd.z
untuk mengambil daftar kata yang dipisahkan baris baru di stdin dan menulis daftar hash yang dipisahkan baris baru di stdout. Kode Python Setara:Batas teoritis
Seberapa baik yang bisa kita harapkan? Berikut adalah plot x, jumlah kata bertabrakan, vs y, entropi dalam byte yang diperlukan untuk mendapatkan paling banyak x kata bertabrakan. Misalnya, titik (2835, 140) memberi tahu kita bahwa fungsi acak paling banyak 2835 kata bertabrakan dengan probabilitas 1/256 ** 140, jadi sangat tidak mungkin bahwa kita akan dapat melakukan jauh lebih baik daripada dengan 140 byte kode.
sumber
Python,
53334991Saya percaya ini adalah pesaing pertama yang mencetak skor secara signifikan lebih baik daripada oracle acak.
sumber
def H(s):n=int(s.encode('hex'),16);return n%...
menghemat 5 byte, kalau-kalau Anda bisa menggunakannya entah bagaimana ...2**24 == 8**8
,.Python 2, 140 byte, 4266 kata bertabrakan
Saya tidak benar-benar ingin memulai dengan byte yang tidak dapat dicetak karena tweetability mereka yang tidak jelas, tetapi saya tidak memulainya. :-P
Python 2, 140 byte yang dapat dicetak,
466244714362 bertabrakan kata-kataTerinspirasi oleh bentuk solusi kasperd, jelas — tetapi dengan tambahan penting dari transformasi affine pada ruang modulus, dan parameter yang sama sekali berbeda.
sumber
n%(8**8-ord('…'[n%70]))
tanpa perubahan parameter lainnya, saya hanya berhasil mencapai 4995, jadi sepertinya pengoptimal Anda yang baru berhasil menangkap saya. Sekarang ini semakin menarik!CJam,
4125393737913677Pendekatan ini membagi domain dan codomain menjadi 110 set terpisah, dan mendefinisikan fungsi hash yang sedikit berbeda untuk setiap pasangan.
Penilaian / Verifikasi
Port berikut ke Python dapat digunakan dengan cuplikan skor resmi:
sumber
h
dalam port Python sesuai dengan built-in CJam?b
(konversi basis).Python,
64466372Solusi ini menghasilkan jumlah tumbukan yang lebih rendah daripada semua entri sebelumnya, dan hanya membutuhkan 44 dari 140 byte yang diizinkan untuk kode:
sumber
%(2**24-1)
, jadi saya pikir mungkin baik untuk meminta klarifikasi[0, 2**24-1]
dari ada kata-kata dalam bahasa Inggris, itu akan menjadi matematis tidak mungkin untuk membuat hash mana setiap nilai tunggal dalam kisaran yang mungkin.CJam, 6273
XOR setiap karakter dengan 49 , kurangi string yang dihasilkan melalui x, y y 245x + y , dan ambil modulo residu 16.777.213 (prime 24-bit terbesar).
Mencetak gol
sumber
JavaScript (ES6), 6389
Fungsi hash (105 byte):
Fungsi penilaian (NodeJS) (170 byte):
Panggil sebagai
node hash.js dictionary.txt
, di manahash.js
skrip,dictionary.txt
adalah file teks kamus (tanpa baris akhir akhir), danF
didefinisikan sebagai fungsi hashing.Terima kasih Neil untuk mencukur 9 byte dari fungsi hashing!
sumber
((...)>>>0)%(1<<24)
Anda mungkin bisa menggunakan(...)<<8>>>8
.i
juga.Mathematica, 6473
Langkah selanjutnya ... alih-alih menjumlahkan kode karakter, kami memperlakukannya sebagai digit angka dasar-151, sebelum mengambilnya modulo 2 24 .
Berikut ini skrip pendek untuk menentukan jumlah tabrakan:
Saya baru saja mencoba semua pangkalan secara sistematis sejak saat itu
1
, dan sejauh ini pangkalan 151 menghasilkan tabrakan paling sedikit. Saya akan mencoba beberapa lagi untuk menurunkan skor sedikit lebih jauh, tetapi pengujiannya agak lambat.sumber
Javascript (ES5), 6765
Ini adalah CRC24 yang dicukur hingga 140 Bytes. Bisa bermain golf lebih banyak tetapi ingin mendapatkan jawaban saya :)
Validator di node.js:
sumber
Python, 340053
Skor mengerikan dari algoritma yang mengerikan, jawaban ini ada lebih untuk memberikan skrip Python kecil yang menampilkan skor.
Untuk mencetak gol:
sumber
Python,
639063766359Dapat dianggap sebagai modifikasi sepele untuk jawaban Martin Büttner .
sumber
[0, 2**24-1]
. Satu-satunya hal yang tidak diperbolehkan adalah mengeluarkan nomor apa pun yang tidak di dalam rentang itu, misalnya-1
atau2**24
.Python, 9310
Ya, bukan yang terbaik, tapi setidaknya itu adalah sesuatu. Seperti yang kami katakan di crypto, jangan pernah menulis fungsi hash Anda sendiri .
Panjangnya persis 140 byte, juga.
sumber
Matlab,
30.82886206848Ini membangun hash dengan menetapkan bilangan prima untuk setiap kombo karakter / posisi ascii dan menghitung produk mereka untuk setiap kata modulo, bilangan prima terbesar yang lebih kecil dari 2 ^ 24. Perhatikan bahwa untuk pengujian saya memindahkan panggilan ke bilangan prima di luar ke tester langsung sebelum loop sementara dan meneruskannya ke fungsi hash, karena mempercepatnya dengan faktor sekitar 1000, tetapi versi ini berfungsi, dan mandiri. Mungkin macet dengan kata-kata yang lebih panjang dari sekitar 40 karakter.
Penguji:
sumber
double
eksplisit. Anda juga bisa menggunakannumel
daripadalength
. Tidak yakin apa yang akan Anda lakukan dengan semua byte ekstra itu!Ruby, 9309 tabrakan, 107 byte
Bukan pesaing yang baik, tetapi saya ingin menjelajahi ide yang berbeda dari entri lain.
Tetapkan n primes pertama ke posisi n pertama dari string, kemudian jumlahkan semua prima [i] ** (kode ascii dari string [i]), lalu mod 2 ** 24-1.
sumber
Java 8,
70546467Ini terinspirasi oleh (tetapi tidak disalin dari) fungsi java.lang.String.hashCode bawaan, jadi silakan larang sesuai dengan aturan # 2.
Untuk mencetak gol:
sumber
hashes
denganMap<Integer, Integer> hashes = new HashMap<>()
dan kemudian menghitung jumlah kata untuk setiap hash, Anda dapat menjelaskannya dengan benar.Python,
699568626732Hanya fungsi RSA sederhana. Cukup lemah, tetapi mengalahkan beberapa jawaban.
sumber
C ++:
711266946483647964126339 tabrakan, 90 bytesSaya menerapkan algoritma genetik yang naif untuk array koefisien saya. Saya akan memperbarui kode ini karena menemukan yang lebih baik. :)
Fungsi tes:
sumber
C #, 6251
6335Konstanta 533 dan 733
889 dan 155memberikan skor terbaik dari semua yang saya cari sejauh ini.sumber
tcl
88 byte, 6448/3233 tabrakan
Saya melihat orang-orang telah menghitung jumlah kata yang bertabrakan, atau jumlah kata yang ditempatkan dalam ember kosong. Saya memberikan kedua hitungan - yang pertama sesuai dengan spesifikasi masalah, dan yang kedua adalah apa yang dilaporkan lebih banyak poster.
sumber
proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}
... benar?Python 3, 89 byte, 6534 tabrakan hash
Semua angka ajaib besar yang Anda lihat di sini adalah konstanta fudge.
sumber
JavaScript, 121 byte,
3268325032446354 (3185) tabrakanParameter (13, 7809064, 380886, 2, 266324) adalah dengan coba-coba.
Masih dapat dioptimalkan menurut saya, dan masih ada ruang untuk menambahkan parameter tambahan, bekerja untuk pengoptimalan lebih lanjut ...
Verifikasi
3268> 3250 - Mengubah parameter ke-3 dari 380713 menjadi 380560.
3250> 3244 - Mengubah parameter ke-3 dari 380560 menjadi 380886.
3244> 6354 - Mengubah parameter ke-2 dari 7809143 menjadi 7809064, dan menemukan saya telah menggunakan metode perhitungan yang salah; P
sumber
Berikut adalah beberapa konstruksi serupa, yang cukup "seedable" dan memungkinkan optimasi parameter tambahan. Sial sulit mendapatkan lebih rendah dari 6k! Dengan asumsi skor memiliki rata-rata 6829 dan std dari 118 saya juga menghitung kemungkinan mendapatkan skor rendah seperti itu secara acak.
Clojure A, 6019, Pr = 1: 299.5e9
Clojure B, 6021, Pr = 1: 266.0e9
Clojure C, 6148, Pr = 1: 254.0e6
Clojure, 6431, Pr = 1: 2.69e3 (sesuatu yang berbeda)
Ini adalah fungsi hash ad-hoc asli saya, ia memiliki empat parameter yang bisa diubah.
sumber
r
diperbaiki). Tapi tetap saja algoritma pencarian saya pada dasarnya brute force, dan saya tidak yakin apakah pilihan awal dari pengalir
itu penting atau tidak.f(n) % (8^8 - g(n))
.Ruby, 6473 tabrakan, 129 byte
Variabel @p diisi dengan semua bilangan prima di bawah 999.
Ini mengubah nilai ascii menjadi bilangan prima dan menjadikan modulo produk mereka prima besar. Faktor fudge dari 179 berkaitan dengan fakta bahwa algoritma asli digunakan untuk menemukan anagram, di mana semua kata yang disusun ulang dari huruf yang sama mendapatkan hash yang sama. Dengan menambahkan faktor dalam loop, itu membuat anagram memiliki kode yang berbeda.
Saya bisa menghapus ** 0,5 (uji sqrt untuk prime) dengan mengorbankan kinerja yang lebih buruk untuk mempersingkat kode. Saya bahkan bisa membuat nomor utama finder dieksekusi dalam loop untuk menghapus sembilan karakter lagi, meninggalkan 115 byte.
Untuk menguji, yang berikut ini mencoba untuk menemukan nilai terbaik untuk faktor fudge di kisaran 1 hingga 300. Ini mengasumsikan bahwa kata file di dalam direktori / tmp:
sumber
tcl
# 91 byte, 6508 tabrakan91 byte, 6502 tabrakan
Komputer masih melakukan pencarian untuk mengevaluasi jika ada nilai yang menyebabkan tabrakan kurang dari basis
147875, yang masih merupakan perekam.sumber