Tweetowanie wyzwanie funkcji skrótu

73

W tym napiszesz funkcję skrótu w 140 bajtach 1 lub mniej kodu źródłowego. Funkcja skrótu musi pobrać ciąg ASCII jako dane wejściowe i zwrócić 24-bitową liczbę całkowitą bez znaku ([0, 2 24 -1]) jako wynik.

Twoja funkcja haszująca będzie oceniana dla każdego słowa w tym dużym słowniku brytyjsko-angielskim 2 . Twój wynik to liczba słów, które dzielą wartość skrótu z innym słowem (kolizją).

Wygrywa najniższy wynik, remisy zerwane przez pierwszy plakat.

Przypadek testowy

Przed przesłaniem sprawdź skrypt oceniania na podstawie następujących danych wejściowych:

duplicate
duplicate
duplicate
duplicate

Jeśli daje wynik inny niż 4, jest błędny.


Zasady wyjaśniające:

  1. Twoja funkcja skrótu musi działać na jednym ciągu, a nie na całej tablicy. Ponadto funkcja skrótu może nie wykonywać żadnych innych operacji we / wy poza łańcuchem wejściowym i liczbą całkowitą wyjściową.
  2. Wbudowane funkcje skrótu lub podobne funkcje (np. Szyfrowanie do bajtów szyfrujących) są niedozwolone.
  3. Twoja funkcja skrótu musi być deterministyczna.
  4. W przeciwieństwie do większości innych konkursów dozwolona jest optymalizacja specjalnie pod kątem punktacji.

1 Wiem, że Twitter ogranicza znaki zamiast bajtów, ale dla uproszczenia użyjemy bajtów jako ograniczenia tego wyzwania.
2 Zmodyfikowane z wbritish-ogromny Debiana , usuwając wszelkie słowa spoza ASCII.

orlp
źródło
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Co...?
Luis Mendo
8
@DonMuesli en.wikipedia.org/wiki/Llanfairpwllgwyngyll (fajny fakt: to słowo znajduje się również we wbudowanym słowniku kompresji Jelly)
Martin Ender
8
Myślę, że powinieneś zabronić wbudowanych słowników.
Dennis
4
Dla porównania: Biorąc 24 MSB SHA-512 uzyskałby wynik 6816.
Dennis
10
Niektóre obliczenia z tyłu koperty: W przypadku D=340275słów i R=2^24wyników mieszania losowy skrót ma spodziewane D^2/(2*R) = 3450pary kolidujące, z których niektóre nakładają się. Spodziewane są D^3/(6*R^2) = 23trzykrotne zderzenia i niewielka liczba większych zderzeń, co oznacza, że ​​te potrójne są prawdopodobnie rozłączne. Daje to oczekiwane 6829słowa, które dzielą wartość skrótu ~ 70w potrójnych, a reszta w parach. Standardowe odchylenie jest szacowane na 118, więc uzyskanie <6200losowego skrótu jest w przybliżeniu zdarzeniem 5 sigma.
xnor

Odpowiedzi:

11

W porządku, pójdę nauczyć się języka golfowego.

CJam, 140 bajtów, 3314 zderzających się słów

00000000: 7b5f 3162 225e d466 4a55 a05e 9f47 fc51  {_1b"^.fJU.^.G.Q
00000010: c45b 4965 3073 72dd e1b4 d887 a4ac bcbd  .[Ie0sr.........
00000020: 9c8f 70ca 2981 b2df 745a 10d0 dfca 6cff  ..p.)...tZ....l.
00000030: 7a3b 64df e730 54b4 b068 8584 5f6c 9f6b  z;d..0T..h.._l.k
00000040: b7f8 7a1f a2d3 b2b8 bcf5 cfa6 1ef7 a55c  ..z............\
00000050: dca8 795c 2492 dc32 1fb6 f449 f9ca f6b7  ..y\$..2...I....
00000060: a2cf 4772 266e ad4f d90c d236 b51d c5d5  ..Gr&n.O...6....
00000070: 5c46 3f9b 7cb4 f195 4efc fe4a ce8d 9aee  \F?.|...N..J....
00000080: 9dbc 223d 6962 3443 2329 257d            .."=ib4C#)%}

Definiuje blok (funkcja anonimowa). Aby przetestować, możesz dodać, qN%%N*Naby wziąć listę słów oddzielonych od nowego wiersza na stdin i napisać listę skrótów oddzielonych od nowego wiersza na stdout. Równoważny kod Pythona:

b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,ord('^\xd4fJU\xa0^\x9fG\xfcQ\xc4[Ie0sr\xdd\xe1\xb4\xd8\x87\xa4\xac\xbc\xbd\x9c\x8fp\xca)\x81\xb2\xdftZ\x10\xd0\xdf\xcal\xffz;d\xdf\xe70T\xb4\xb0h\x85\x84_l\x9fk\xb7\xf8z\x1f\xa2\xd3\xb2\xb8\xbc\xf5\xcf\xa6\x1e\xf7\xa5\\\xdc\xa8y\\$\x92\xdc2\x1f\xb6\xf4I\xf9\xca\xf6\xb7\xa2\xcfGr&n\xadO\xd9\x0c\xd26\xb5\x1d\xc5\xd5\\F?\x9b|\xb4\xf1\x95N\xfc\xfeJ\xce\x8d\x9a\xee\x9d\xbc'[b(s,1)%125]))%(8**8+1)

Pyth, 140 bajtów, 3535 3396 zderzających się słów

00000000: 4c25 4362 2d68 5e38 2038 2a36 3643 4022  L%Cb-h^8 8*66C@"
00000010: aa07 f29a 27a7 133a 3901 484d 3f9b 1982  ....'..:9.HM?...
00000020: d261 79ab adab 9d92 888c 3012 a280 76cf  .ay.......0...v.
00000030: a2e5 8f81 7039 acee c42e bc18 28d8 efbf  ....p9......(...
00000040: 0ebe 2910 9c90 158e 3742 71b4 bdf5 59c2  ..).....7Bq...Y.
00000050: f90b e291 8673 ea59 6975 10be e750 84c8  .....s.Yiu...P..
00000060: 0b0f e7e8 f591 f628 cefa 1ab3 2e3c 72a3  .......(.....<r.
00000070: 7f09 6190 dbd2 d54e d6d0 d391 a780 ebb6  ..a....N........
00000080: ae86 2d1e 49b0 552e 7522 4362            ..-.I.U.u"Cb

Definiuje funkcję o nazwie y. Aby przetestować, możesz dodać, jmyd.zaby wziąć listę słów oddzielonych od nowego wiersza na stdin i napisać listę skrótów oddzielonych od nowego wiersza na stdout. Równoważny kod Pythona:

b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,256)%(8**8+1-66*ord("\xaa\x07\xf2\x9a'\xa7\x13:9\x01HM?\x9b\x19\x82\xd2ay\xab\xad\xab\x9d\x92\x88\x8c0\x12\xa2\x80v\xcf\xa2\xe5\x8f\x81p9\xac\xee\xc4.\xbc\x18(\xd8\xef\xbf\x0e\xbe)\x10\x9c\x90\x15\x8e7Bq\xb4\xbd\xf5Y\xc2\xf9\x0b\xe2\x91\x86s\xeaYiu\x10\xbe\xe7P\x84\xc8\x0b\x0f\xe7\xe8\xf5\x91\xf6(\xce\xfa\x1a\xb3.<r\xa3\x7f\ta\x90\xdb\xd2\xd5N\xd6\xd0\xd3\x91\xa7\x80\xeb\xb6\xae\x86-\x1eI\xb0U.u"[b(s,256)%121]))

Teoretyczne granice

Jak dobrze możemy się spodziewać? Oto wykres x, liczba kolidujących słów, w porównaniu do y, entropia w bajtach wymagana do uzyskania maksymalnie x kolidujących słów. Na przykład punkt (2835, 140) mówi nam, że funkcja losowa uzyskuje co najwyżej 2835 zderzających się słów z prawdopodobieństwem 1/256 ** 140, więc jest bardzo mało prawdopodobne, że kiedykolwiek będziemy w stanie zrobić znacznie lepiej niż z 140 bajty kodu.

wykres

Anders Kaseorg
źródło
Ładna analiza teoretycznych granic. Aby pokonać ten teoretyczny limit, prawdopodobnie należałoby użyć języka z wbudowanymi funkcjami zoptymalizowanymi dla słownika w pytaniu (co byłoby oszustwem). Jeśli język ma wbudowany skrót kryptograficzny, limit można zmienić w bardziej lub mniej konstruktywną metodę znajdowania optymalnego rozwiązania. Rozważ to: $ h (w || c)% 2 ^ {24} $ gdzie $ c $ jest stałą ciągu bajtów. W losowym modelu wyroczni, który z dużym prawdopodobieństwem może być zbliżony do optymalnego. Oczywiście brutalne wymuszenie $ c $ nie byłoby wykonalne.
kasperd
Jak obliczyłeś wzór na wykres? Naprawdę interesujące!
NikoNyrh
@NikoNyrh Programowanie dynamiczne. Niech ( W , C , H ) reprezentują stan z w słowa, które C kolidują z wys różnych skrótów i pozostałą W - C mają różne skrótów. Jeśli dodamy losowe słowo, stan staje się ( w + 1, c , h ) z prawdopodobieństwem 1 - ( h + w - c ) / 2 ^ 24 lub ( w + 1, c + 1, h ) z prawdopodobieństwem h / 2 ^ 24 lub ( w + 1, c+ 2, h + 1) z prawdopodobieństwem ( w - c ) / 2 ^ 24. Zatem ostatnia entropia wyrysowana za pomocą x kolidujących słów jest logarytmiczną podstawą 1/256 sumy prawdopodobieństwa w stanach (340275, c , h ) o cx .
Anders Kaseorg
Nie mogę uwierzyć, że nikt nie zapytał, jak wymyśliłeś funkcję skrótu? Byłbym bardzo zainteresowany, aby wiedzieć.
Anush
22

Python, 5333 4991

Uważam, że to pierwszy rywal, który uzyskał znacznie lepsze wyniki niż losowa wyrocznia.

def H(s):n=int(s.encode('hex'),16);return n%(8**8-ord('+%:5O![/5;QwrXsIf]\'k#!__u5O}nQ~{;/~{CutM;ItulA{uOk_7"ud-o?y<Cn~-`bl_Yb'[n%70]))
kasperd
źródło
1
Czary! def H(s):n=int(s.encode('hex'),16);return n%...oszczędza 5 bajtów, na wypadek, gdybyś mógł ich jakoś wykorzystać ...
Dennis
3
@ Dennis Mógłbym użyć 5 bajtów, aby ciąg stał się dłuższy o 5 bajtów. Ale gdybym zmienił długość, musiałbym zacząć od zbudowania stałej łańcucha od zera. I nie jestem pewien, czy te 5 bajtów da mi wystarczającą poprawę, że warto zacząć od zbudowania łańcucha. Spędziłem już godziny czasu procesora, optymalizując stałą ciągu.
kasperd
@Dennis Wydaje mi się, że kilka dodatkowych bajtów dałoby mi swobodę używania niektórych znaków w ciągłej potrzebie ucieczki. W ten sposób mogłem potencjalnie użyć kilku dodatkowych bajtów bez konieczności ponownego tworzenia łańcucha.
kasperd
7
Jeśli chcesz kolejny bajt 2**24 == 8**8.
Anders Kaseorg
20

Python 2, 140 bajtów, 4266 zderzających się słów

Tak naprawdę nie chciałem zacząć od bajtów, które nie są drukowalne, biorąc pod uwagę ich niejasną tweetalność, ale cóż, nie zacząłem. :-P

00000000: efbb bf64 6566 2066 2873 293a 6e3d 696e  ...def f(s):n=in
00000010: 7428 732e 656e 636f 6465 2827 6865 7827  t(s.encode('hex'
00000020: 292c 3336 293b 7265 7475 726e 206e 2528  ),36);return n%(
00000030: 382a 2a38 2b31 2d32 3130 2a6f 7264 2827  8**8+1-210*ord('
00000040: 6f8e 474c 9f5a b49a 01ad c47f cf84 7b53  o.GL.Z........{S
00000050: 49ea c71b 29cb 929a a53b fc62 3afb e38e  I...)....;.b:...
00000060: e533 7360 982a 50a0 2a82 1f7d 768c 7877  .3s`.*P.*..}v.xw
00000070: d78a cb4f c5ef 9bdb 57b4 7745 3a07 8cb0  ...O....W.wE:...
00000080: 868f a927 5b6e 2536 375d 2929            ...'[n%67]))

Python 2, 140 bajtów do wydrukowania, 4662 4471 4362 kolidujące słowa

def f(s):n=int(s.encode('hex'),16);return n%(8**8+3-60*ord('4BZp%(jTvy"WTf.[Lbjk6,-[LVbSvF[Vtw2e,NsR?:VxC0h5%m}F5,%d7Kt5@SxSYX-=$N>'[n%71]))

Zainspirowany formą rozwiązania Kasperda, oczywiście - ale z ważnym dodatkiem transformacji afinicznej w przestrzeni modułu i zupełnie innych parametrów.

Anders Kaseorg
źródło
+1 Nie poddaję się bez walki. Ale myślę, że muszę przestać optymalizować moje obecne rozwiązanie i znaleźć inne podejście, ponieważ nie zamierzam cię pokonać, jeśli będę nadal używać mojego obecnego podejścia do optymalizacji parametrów. Wrócę z edycją mojego rozwiązania, gdy już
pobiję
@kasperd: Awesome, włącz to. :-P
Anders Kaseorg
1
@AndersKaseorg Jak znaleźć ciąg?
Tylko ASCII,
@AndersKaseorg Udało mi się znacznie przyspieszyć wyszukiwanie parametrów. Usunąłem przeszkodę, która spowodowała, że ​​moje poszukiwania utknęły w nieoptymalnych rozwiązaniach. Ale nadal nie mogłem zrobić nic lepszego niż 4885. Po zastanowieniu się, dlaczego nie mogłem tego zrobić dalej, nagle zdałem sobie sprawę, co jest nie tak z moim rozwiązaniem i jak to naprawić. Teraz afiniczna transformacja w twoim rozwiązaniu ma dla mnie idealny sens. Myślę, że jedynym sposobem, w jaki mogę to nadrobić, jest sama transformacja afiniczna.
kasperd
1
@kasperd: Very nice. Kiedy szukałem lepszego ciągu n%(8**8-ord('…'[n%70]))bez innych zmian parametrów, udało mi się dostać tylko do 4995, więc wygląda na to, że twój nowy optymalizator do mnie dotarł. Teraz staje się to bardziej interesujące!
Anders Kaseorg,
16

CJam, 4125 3937 3791 3677

0000000: 7b 5f 39 62 31 31 30 25 5f 22 7d 13 25 77  {_9b110%_"}.%w
000000e: 77 5c 22 0c e1 f5 7b 83 45 85 c0 ed 08 10  w\"...{.E.....
000001c: d3 46 0c 5c 22 59 f8 da 7b f8 18 14 8e 4b  .F.\"Y..{....K
000002a: 3a c1 9e 97 f8 f2 5c 18 21 63 13 c8 d3 86  :.....\.!c....
0000038: 45 8e 64 33 61 50 96 c4 48 ea 54 3b b3 ab  E.d3aP..H.T;..
0000046: bc 90 bc 24 21 20 50 30 85 5f 7d 7d 59 2c  ...$! P0._}}Y,
0000054: 4a 67 88 c8 94 29 1a 1a 1a 0f 38 c5 8a 49  Jg...)....8..I
0000062: 9b 54 90 b3 bd 23 c6 ed 26 ad b6 79 89 6f  .T...#..&..y.o
0000070: bd 2f 44 6c f5 3f ae af 62 9b 22 3d 69 40  ./Dl.?..b."=i@
000007e: 62 31 35 32 35 31 39 25 31 31 30 2a 2b 7d  b152519%110*+}

To podejście dzieli domenę i kodomainę na 110 rozłącznych zestawów i definiuje nieco inną funkcję skrótu dla każdej pary.

Punktacja / weryfikacja

$ echo $LANG
en_US
$ cat gen.cjam
"qN%{_9b110%_"
[125 19 37 119 119 34 12 225 245 123 131 69 133 192 237 8 16 211 70 12 34 89 248 218 123 248 24 20 142 75 58 193 158 151 248 242 92 24 33 99 19 200 211 134 69 142 100 51 97 80 150 196 72 234 84 59 179 171 188 144 188 36 33 32 80 48 133 95 125 125 89 44 74 103 136 200 148 41 26 26 26 15 56 197 138 73 155 84 144 179 189 35 198 237 38 173 182 121 137 111 189 47 68 108 245 63 174 175 98 155]
:c`"=i@b152519%110*+}%N*N"
$ cjam gen.cjam > test.cjam
$ cjam test.cjam < british-english-huge.txt | sort -n > temp
$ head -1 temp
8
$ tail -1 temp
16776899
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(uniq -u < temp | wc -l)
$ echo $[all - unique]
3677

Następujący port do Pythona może być używany z oficjalnym fragmentem oceniania:

h=lambda s,b:len(s)and ord(s[-1])+b*h(s[:-1],b)

def H(s):
 p=h(s,9)%110
 return h(s,ord(
  '}\x13%ww"\x0c\xe1\xf5{\x83E\x85\xc0\xed\x08\x10\xd3F\x0c"Y\xf8\xda{\xf8\x18\x14\x8eK:\xc1\x9e\x97\xf8\xf2\\\x18!c\x13\xc8\xd3\x86E\x8ed3aP\x96\xc4H\xeaT;\xb3\xab\xbc\x90\xbc$! P0\x85_}}Y,Jg\x88\xc8\x94)\x1a\x1a\x1a\x0f8\xc5\x8aI\x9bT\x90\xb3\xbd#\xc6\xed&\xad\xb6y\x89o\xbd/Dl\xf5?\xae\xafb\x9b'
  [p]))%152519*110+p
Dennis
źródło
1
Przeniesiłem mój kod do Pythona w celu łatwej weryfikacji.
Dennis,
Czy hw tym porcie Python odpowiada wbudowanemu CJam?
kasperd
Tak. To CJam's b(konwersja podstawowa).
Dennis,
Czy Twój proces oceniania jest bash?
GamrCorps
@GamrCorps Tak, to jest Bash.
Dennis
11

Python, 6446 6372


To rozwiązanie osiąga mniejszą liczbę kolizji niż wszystkie poprzednie wpisy i potrzebuje tylko 44 z 140 bajtów dozwolonych dla kodu:

H=lambda s:int(s.encode('hex'),16)%16727401
kasperd
źródło
2
@ mbomb007 własne zgłoszenie orlp robi %(2**24-1), więc myślę, że dobrze byłoby poprosić o wyjaśnienia
Sp3000,
12
@ mbomb007 Wyzwanie mówi, że nie ma czegoś takiego. Mówi, że funkcja musi przyjmować ciąg ASCII jako dane wejściowe i wyjściowe liczby całkowite w tym zakresie. Bez względu na to, jakie dane wejściowe podasz mojej funkcji, wynik będzie w tym zakresie. Matematyczna definicja funkcji słowa nie wymaga, aby generowała każdy dozwolony wynik. Jeśli tego właśnie chciałeś, to matematyczny termin, którego używałbyś, był funkcją wymuszającą. Ale słowo „przymiotnik” nie było używane w wymaganiach.
kasperd
@ mbomb007: Nie ma wymogu, aby funkcje mieszające były narzucające. Na przykład wiele funkcji skrótu opartych na adresie pamięci może generować wielokrotności niewielkiej mocy 2 z powodu wyrównania pamięci, w tym domyślny skrót obiektów w starszych wersjach Pythona. Wiele funkcji skrótu ma nawet mniejszą domenę niż kodomena, więc i tak nie mogą być zaskakujące.
user2357112
3
@ mbomb007 - W rzeczywistości, biorąc pod uwagę, że istnieje znacznie więcej wartości liczbowych [0, 2**24-1]niż słów w języku angielskim, matematycznie niemożliwe byłoby utworzenie skrótu, w którym każda pojedyncza wartość z tego zakresu byłaby możliwa.
Darrel Hoffman
7

CJam, 6273

{49f^245b16777213%}

XOR każdy znak z 49 , zmniejsz wynikowy ciąg przez x, y ↦ 245x + y , i weź moduł reszty 16 777 213 (największa liczba 24-bitowa).

Punktacja

$ cat hash.cjam
qN% {49f^245b16777213%} %N*N
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(cjam hash.cjam < british-english-huge.txt | sort | uniq -u | wc -l)
$ echo $[all - unique]
6273
Dennis
źródło
Ponownie zaimplementowałem algorytm w pythonie z twojego opisu. Mogę potwierdzić, że Twój wynik sprawdza się na podstawie oficjalnego obliczenia wyniku.
kasperd
7

JavaScript (ES6), 6389

Funkcja skrótu (105 bajtów):

s=>[...s.replace(/[A-Z]/g,a=>(b=a.toLowerCase())+b+b)].reduce((a,b)=>(a<<3)*28-a^b.charCodeAt(),0)<<8>>>8

Funkcja oceniania (NodeJS) (170 bajtów):

h={},c=0,l=require('fs').readFileSync(process.argv[2],'utf8').split('\n').map(a=>h[b=F(a)]=-~h[b])
for(w of Object.getOwnPropertyNames(h)){c+=h[w]>1&&h[w]}
console.log(c)

Wywołaj jako node hash.js dictionary.txt, gdzie hash.jsjest skrypt, dictionary.txtjest plikiem tekstowym słownika (bez ostatniego nowego wiersza) i Fjest zdefiniowany jako funkcja mieszająca.

Dzięki Neil za golenie 9 bajtów funkcji haszowania!

Mwr247
źródło
Dlaczego przypisanie do? Również zamiast ((...)>>>0)%(1<<24)ciebie prawdopodobnie możesz użyć (...)<<8>>>8.
Neil
@Neil Ponieważ alfabet i jestem nudny = P Poza tym, ładna matematyka bitowa! To zaoszczędziło 7 bajtów =)
Mwr247
Dobrze, że to nie jest golf golfowy, w przeciwnym razie musiałbym wysłać cię za nieużywaną zmienną i.
Neil,
@Neil Crap> _ <Używam tego podczas testowania alternatywnych pomysłów na haszowanie i zapomniałem usunąć XD Tak, dobrze, że to nie jest golf, choć mimo wszystko, bardzo bym chciał, gdybym mógł skompresować funkcje skrótu i ​​oceniania do tych samych 140 bajtów, więc każdy pomaga;)
Mwr247
1
@ Sp3000 Gah, rozumiem, co masz na myśli. Mój nie liczy tych, które są tam początkowo po znalezieniu kolizji. Naprawię to.
Mwr247,
5

Mathematica, 6473

Następny krok w górę ... zamiast sumowania kodów znaków traktujemy je jako cyfry liczby podstawowej-151, zanim weźmiemy je modulo 2 24 .

hash[word_] := Mod[FromDigits[ToCharacterCode @ word, 151], 2^24]

Oto krótki skrypt określający liczbę kolizji:

Total[Last /@ DeleteCases[Tally[hash /@ words], {_, 1}]]

Właśnie próbowałem systematycznie wszystkich baz od samego 1początku i jak dotąd baza 151 spowodowała najmniej kolizji. Spróbuję jeszcze kilka, aby obniżyć wynik jeszcze bardziej, ale testowanie jest trochę wolne.

Martin Ender
źródło
5

JavaScript (ES5), 6765

To jest CRC24 ogolony do 140 bajtów. Mogłem więcej golfa, ale chciałem uzyskać odpowiedź :)

function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

Walidator w node.js:

var col = new Array(16777215);
var n = 0;

var crc24_140 = 
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

require('fs').readFileSync('./dict.txt','utf8').split('\n').map(function(s){ 
    var h = crc24_140(s);
    if (col[h]===1) {
        col[h]=2;
        n+=2;
    } else if (col[h]===2) {
        n++;
    } else {
        col[h]=1;
    }
});

console.log(n);
binarymax
źródło
Witamy w Programowaniu Puzzle i Code Golf!
Alex A.
... I dzięki za ciepłe powitanie @AlexA.!
binarymax
5

Python, 340053

Straszna ocena ze strasznego algorytmu, ta odpowiedź istnieje bardziej, aby dać mały skrypt Pythona, który wyświetla ocenę.

H=lambda s:sum(map(ord, s))%(2**24)

Zaliczyć:

hashes = []
with open("british-english-huge.txt") as f:
    for line in f:
        word = line.rstrip("\n")
        hashes.append(H(word))

from collections import Counter
print(sum(v for k, v in Counter(hashes).items() if v > 1))
orlp
źródło
1
Przydatne może być sprawdzenie, czy kod oceniający zwraca wartość funkcji haszującej jako liczbę całkowitą w dozwolonym zakresie.
kasperd
4

Python, 6390 6376 6359

H=lambda s:reduce(lambda a,x:a*178+ord(x),s,0)%(2**24-48)

Można to uznać za trywialną modyfikację odpowiedzi Martina Büttnera .

Tylko ASCII
źródło
3
@ mbomb007 To nieprawda. Jeśli twoja funkcja zawsze wyprowadza 4, nadal działa w zakresie [0, 2**24-1]. Jedyne, co jest niedozwolone, to wypisywanie dowolnej liczby spoza tego zakresu, np . -1Lub 2**24.
orlp
3

Python, 9310


Tak, nie najlepsze, ale przynajmniej to jest coś. Jak mówimy w kryptografii, nigdy nie pisz własnej funkcji skrótu .

Ma również dokładnie 140 bajtów.

F=lambda x,o=ord,m=map:int((int(''.join(m(lambda z:str(o(z)^o(x[-x.find(z)])^o(x[o(z)%len(x)])),x)))^(sum(m(int,m(o,x))))^o(x[-1]))%(2**24))
Mr Public
źródło
2

Matlab, 30828 8620 6848

Buduje skrót, przypisując liczbę pierwszą do każdej kombinacji znaków / pozycji ascii i obliczając ich iloczyn dla każdego słowa modulo największej liczby pierwszej mniejszej niż 2 ^ 24. Zauważ, że do testowania przeniosłem wywołanie liczb pierwszych na tester bezpośrednio przed pętlą while i przekazałem je do funkcji skrótu, ponieważ przyspieszyło to około 1000 razy, ale ta wersja działa i jest samodzielna. Może się zawiesić ze słowami dłuższymi niż około 40 znaków.

function h = H(s)
p = primes(1e6);
h = 1;
for i=1:length(s)
    h = mod(h*p(double(s(i))*i),16777213);
end
end

Próbnik:

clc
clear variables
close all

file = fopen('british-english-huge.txt');
hashes = containers.Map('KeyType','uint64','ValueType','uint64');

words = 0;
p = primes(1e6);
while ~feof(file)
    words = words + 1;
    word = fgetl(file);
    hash = H(word,p);
    if hashes.isKey(hash)
        hashes(hash) = hashes(hash) + 1;
    else
        hashes(hash) = 1;
    end
end

collisions = 0;
for key=keys(hashes)

    if hashes(key{1})>1
        collisions = collisions + hashes(key{1});
    end
end
Godric Seer
źródło
Jeśli chcesz zaoszczędzić miejsce w swoim programie, nie musisz doublejawnie konwertować swojego znaku na . Możesz także użyć numelzamiast length. Nie jestem jednak pewien, co zrobiłbyś z tymi wszystkimi dodatkowymi bajtami!
Suever,
1

Ruby, 9309 zderzeń, 107 bajtów

def hash(s);require'prime';p=Prime.first(70);(0...s.size).reduce(0){|a,i|a+=p[i]**(s[i].ord)}%(2**24-1);end 

Nie jestem dobrym kandydatem, ale chciałem odkryć inny pomysł niż inne wpisy.

Przypisz pierwsze n liczb pierwszych do pierwszych n pozycji łańcucha, a następnie zsumuj wszystkie liczby pierwsze [i] ** (kod ascii łańcucha [i]), a następnie mod 2 ** 24-1.

jose_castro_arnaud
źródło
1

Java 8, 7054 6467

Jest to zainspirowane (ale nie skopiowane z) wbudowaną funkcją java.lang.String.hashCode, więc nie krępuj się zgodnie z regułą # 2.

w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

Zaliczyć:

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public class TweetableHash {
    public static void main(String[] args) throws Exception {
        List<String> words = Files.readAllLines(Paths.get("british-english-huge.txt"));

        Function<String, Integer> hashFunc = w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

        Map<Integer, Integer> hashes = new HashMap<>();
        for (String word : words) {
            int hash = hashFunc.apply(word);
            if (hash < 0 || hash >= 16777216) {
                throw new Exception("hash too long for word: " + word + " hash: " + hash);
            }

            Integer numOccurences = hashes.get(hash);
            if (numOccurences == null) {
                numOccurences = 0;
            }
            numOccurences++;

            hashes.put(hash, numOccurences);
        }

        int numCollisions = hashes.values().stream().filter(i -> i > 1).reduce(Integer::sum).get();
        System.out.println("num collisions: " + numCollisions);
    }
}
Bewusstsein
źródło
@muddyfish, czy możesz sprawdzić aktualną wersję? myślę, że wziąłem udział w kolizjach trójstronnych i nadal otrzymuję ten sam wynik.
Bewusstsein
Nie uwzględnia to kolizji trójstronnych. Jeśli zastąpi hashessię Map<Integer, Integer> hashes = new HashMap<>(), a następnie policzyć liczbę słów dla każdego hash, można uwzględnić je poprawnie.
Peter Taylor
Twój wynik nadal wygląda na nieprawidłowy. Myślę, że aby obliczyć poprawny wynik, musisz wypisać wartości numHash + numCollisions. (Myślę, że przybliżę cię do mojej oceny 6832 dla losowej wyroczni.)
kasperd
Zmodyfikuj części klasyfikacji do tego: pastebin.com/nLeg4qut
TheNumberOne
tak, naprawiłem ocenianie i wygląda teraz na znacznie bardziej rozsądną wartość, ty
Bewusstsein
1

Python, 6995 6862 6732

Po prostu prosta funkcja RSA. Dość kulawy, ale bije kilka odpowiedzi.

M=0x5437b3a3b1
P=0x65204c34d
def H(s):
    n=0
    for i in range(len(s)):
        n+=pow(ord(s[i]),P,M)<<i
    return n%(8**8)
niebieski
źródło
1

C ++: 7112 6694 6483 6479 6412 6339 kolizji, 90 bajtów

Wdrożyłem naiwny algorytm genetyczny dla mojej tablicy współczynników. Zaktualizuję ten kod, ponieważ znajdzie lepsze. :)

int h(const char*s){uint32_t t=0,p=0;while(*s)t="cJ~Z]q"[p++%6]*t+*s++;return t%16777213;}

Funkcja testowa:

int main(void)
{
    std::map<int, int> shared;

    std::string s;
    while (std::cin >> s) {
        shared[h(s.c_str())]++;
    }

    int count = 0;
    for (auto c : shared) {
        if ((c.first & 0xFFFFFF) != c.first) { std::cerr << "invalid hash: " << c.first << std::endl; }
        if (c.second > 1) { count += c.second; }
    }

    std::cout << count << std::endl;
    return 0;
}
puszysty
źródło
1

C # 6251 6335

int H(String s){int h = 733;foreach (char c in s){h = (h * 533 + c);}return h & 0xFFFFFF;}

Stałe 533 i 733 889 i 155 dają najlepszy wynik spośród wszystkich, które do tej pory szukałem.

bmm6o
źródło
1

tcl

88 bajtów, kolizje 6448/3233

Widzę, że ludzie liczą albo liczbę kolidujących słów, albo liczbę słów umieszczonych w niepustych wiadrach. Podaję oba obliczenia - pierwszy jest zgodny ze specyfikacją problemu, a drugi to, co zgłaszają kolejne plakaty.

# 88 bytes, 6448 collisions, 3233 words in nonempty buckets

puts "[string length {proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}}] bytes"

proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}

# change 2551 above to:
#   7: 85 bytes, 25839 colliding words, 13876 words in nonempty buckets
#   97: 86 bytes, 6541 colliding words, 3283 words in nonempty buckets
#   829: 87 bytes, 6471 colliding words, 3251 words in nonempty buckets


# validation program

set f [open ~/Downloads/british-english-huge.txt r]
set words [split [read $f] \n]
close $f

set have {};                        # dictionary whose keys are hash codes seen
foreach w $words {
    if {$w eq {}} continue
    set h [H $w]
    dict incr have $h
}
set coll 0
dict for {- count} $have {
    if {$count > 1} {
        incr coll $count
    }
}
puts "found $coll collisions"
Kevin Kenny
źródło
2
Gdzie widzisz odpowiedzi, używając niewłaściwej metody obliczania wyniku? Było wiele, ale wszystkie zostały poprawione lub usunięte lata temu. Widzę cztery odpowiedzi, które mają mniej niż 6000 punktów, ponieważ te cztery odpowiedzi zostały zoptymalizowane, aby uzyskać tak niskie wyniki.
kasperd
1
O ile wiem, twój kod jest proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... prawda?
Erik the Outgolfer,
@EriktheOutgolfer: Tak, to jest
sergiol
1
Po drugie @kasperd: Czy możesz wskazać, które odpowiedzi nie uwzględniają kolizji zgodnie ze specyfikacją pytania? Czy naprawdę próbowałeś je uruchomić?
sergiol
1

Python 3, 89 bajtów, 6534 kolizje skrótów

def H(x):
 v=846811
 for y in x:
  v=(972023*v+330032^ord(y))%2**24
 return v%2**24

Wszystkie duże magiczne liczby, które tu widzisz, są stałymi krówek.

Magenta
źródło
1

JavaScript, 121 bajtów, 3268 3250 3244 6354 (3185) kolizji

s=>{v=i=0;[...s].map(z=>{v=((((v*13)+(s.length-i)*7809064+i*380886)/2)^(z.charCodeAt(0)*266324))&16777215;i++});return v}

Parametry (13, 7809064, 380886, 2, 266324) są metodą prób i błędów.

Sądzę, że wciąż można go zoptymalizować, a wciąż jest miejsce na dodanie dodatkowych parametrów, pracę nad dalszą optymalizacją ...

Weryfikacja

hashlist = [];
conflictlist = [];
for (x = 0; x < britain.length; x++) {
    hash = h(britain[x]);                      //britain is the 340725-entry array
    hashlist.push(hash);
}

conflict = 0; now_result = -1;
(sortedlist = sort(hashlist)).map(v => {
    if (v == now_result) {
        conflict++;
        conflictlist.push(v);
    }
    else
        now_result = v;
});

console.log(conflictlist);

var k = 0;
while (k < conflictlist.length) {
    if (k < conflictlist.length - 1 && conflictlist[k] == conflictlist[k+1])
        conflictlist.splice(k,1);
    else
        k++;
}

console.log(conflict + " " + (conflict+conflictlist.length));

3268> 3250 - Zmieniono trzeci parametr z 380713 na 380560.

3250> 3244 - Zmieniono trzeci parametr z 380560 na 380886.

3244> 6354 - Zmieniłem drugi parametr z 7809143 na 7809064 i stwierdziłem, że zastosowałem niewłaściwą metodę obliczeń; P

Shieru Asakoto
źródło
1

Oto kilka podobnych konstrukcji, które są dość „wysiewalne” i umożliwiają stopniową optymalizację parametrów. Cholera, trudno jest zejść poniżej 6k! Zakładając, że wynik ma średnią 6829, a std 118, również obliczyłem prawdopodobieństwo otrzymania tak niskich wyników losowo.

Clojure A, 6019, Pr = 1: 299,5e9

 #(reduce(fn[r i](mod(+(* r 811)i)16777213))(map *(cycle(map int"~:XrBaXYOt3'tH-x^W?-5r:c+l*#*-dtR7WYxr(CZ,R6J7=~vk"))(map int %)))

Clojure B, 6021, Pr = 1: 266,0e9

#(reduce(fn[r i](mod(+(* r 263)i)16777213))(map *(cycle(map int"i@%(J|IXt3&R5K'XOoa+Qk})w<!w[|3MJyZ!=HGzowQlN"))(map int %)(rest(range))))

Clojure C, 6148, Pr = 1: 254,0e6

#(reduce(fn[r i](mod(+(* r 23)i)16777213))(map *(cycle(map int"ZtabAR%H|-KrykQn{]u9f:F}v#OI^so3$x54z2&gwX<S~"))(for[c %](bit-xor(int c)3))))

Clojure, 6431, Pr = 1: 2.69e3 (coś innego)

#(mod(reduce bit-xor(map(fn[i[a b c]](bit-shift-left(* a b)(mod(+ i b c)19)))(range)(partition 3 1(map int(str"w"%"m")))))16776869)

To była moja pierwotna funkcja skrótu ad-hoc, ma cztery dostrojone parametry.

NikoNyrh
źródło
Trikiem do niskiego wyniku jest stała łańcuchowa, w której każda postać może być optymalizowana niezależnie bez rujnowania optymalizacji dokonanej dla innych postaci.
kasperd
Tak, próbowałem najpierw zoptymalizować tylko dla krótszych ciągów, ponieważ dodanie większej liczby znaków do ciągu „entropii” nie wpływa na te (po ustaleniu mnożnika r). Ale nadal moim algorytmem wyszukiwania jest w zasadzie brutalna siła i nie jestem pewien, czy początkowy wybór mnożnika rjest ważny, czy nie.
NikoNyrh
Być może samo pomnożenie wartości ASCII nie zapewnia wystarczającej entropii w grze. Wydaje się, że wiele algorytmów dobrze oceniających ma formę f(n) % (8^8 - g(n)).
NikoNyrh
Jest jedna odpowiedź, która wyjaśnia, jak spadła do 3677. Te, które osiągnęły jeszcze niższy wynik, mają małe wyjaśnienie.
kasperd
0

Ruby, 6473 zderzeń, 129 bajtów

h=->(w){@p=@p||(2..999).select{|i|(2..i**0.5).select{|j|i%j==0}==[]};c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+179)%((1<<24)-3)}}

Zmienna @p jest wypełniona wszystkimi liczbami pierwszych poniżej 999.

To przekształca wartości ascii w liczby pierwsze i sprawia, że ​​ich moduł produktu jest dużą liczbą pierwszą. Współczynnik krycia 179 dotyczy faktu, że oryginalny algorytm służył do znajdowania anagramów, w których wszystkie słowa, które są przegrupowaniami tych samych liter, mają ten sam skrót. Dodając czynnik w pętli, sprawia, że ​​anagramy mają różne kody.

Mógłbym usunąć ** 0,5 (test sqrt dla liczby pierwszej) kosztem gorszej wydajności, aby skrócić kod. Mógłbym nawet sprawić, by wyszukiwarka liczb pierwszych działała w pętli, aby usunąć jeszcze dziewięć znaków, pozostawiając 115 bajtów.

Aby przetestować, poniższe próbują znaleźć najlepszą wartość współczynnika krówki w zakresie od 1 do 300. Zakłada się, że plik słowa w katalogu / tmp:

h=->(w,y){
  @p=@p||(2..999).
    select{|i|(2..i**0.5). 
    select{|j|i%j==0}==[]};
  c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+y)%((1<<24)-3)}
}

american_dictionary = "/usr/share/dict/words"
british_dictionary = "/tmp/british-english-huge.txt"
words = (IO.readlines british_dictionary).map{|word| word.chomp}.uniq
wordcount = words.size

fewest_collisions = 9999
(1..300).each do |y|
  whash = Hash.new(0)
  words.each do |w|
    code=h.call(w,y)
    whash[code] += 1
  end
  hashcount = whash.size
  collisions = whash.values.select{|count| count > 1}.inject(:+)
  if (collisions < fewest_collisions)
    puts "y = #{y}. #{collisions} Collisions. #{wordcount} Unique words. #{hashcount} Unique hash values"
    fewest_collisions = collisions
  end
end
Paul Chernoch
źródło
1
Wynik wygląda podejrzanie. Czy na pewno liczysz wszystkie kolidujące słowa? Kilka poprzednich odpowiedzi błędnie policzyło tylko jedno słowo dla każdej kolidującej wartości skrótu.
kasperd
Możesz mieć rację. Muszę zastanowić się, jak policzyłem i sprawdzić, czy jest taka sama jak twoja definicja. Liczę, ile jest słów, i odejmuję, ile wygenerowano unikatowych kodów skrótu. Jeśli słowa A i B otrzymują ten sam kod skrótu, to czy to jedno zderzenie, czy dwa? Liczę to jako jeden.
Paul Chernoch
1
Nie zdefiniowałem funkcji oceniania. Właśnie skopiowałem go z przykładowej odpowiedzi opublikowanej przez tego samego użytkownika, który opublikował wyzwanie. Większość odpowiedzi ma wyniki w zakresie od 6273 do 6848. Było wiele odpowiedzi, z których każda popełniła ten sam błąd w obliczeniu wyniku, co doprowadziło do obliczenia wyniku w przybliżeniu połowy tego, co powinno być. (Dokładnie połowa poprawnego wyniku, jeśli nie ma przypadków trzech kolidujących słów.)
kasperd
1
Tak, popełniłem ten sam błąd. Poprawię swoją odpowiedź później. Muszę złapać autobus.
Paul Chernoch
Naprawiono punktację.
Paul Chernoch
0

tcl

# 91 bajtów, 6508 kolizji

91 bajtów, 6502 kolizji

proc H s {lmap c [split $s ""] {incr h [expr [scan $c %c]*875**[incr i]]};expr $h&0xFFFFFF}

Komputer nadal wykonuje wyszukiwanie w celu oceny, czy istnieje wartość powodująca mniej kolizji niż baza 147 875, która wciąż jest rejestratorem.

sergiol
źródło