W tym wyzwaniu kodu 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:
- 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ą.
- Wbudowane funkcje skrótu lub podobne funkcje (np. Szyfrowanie do bajtów szyfrujących) są niedozwolone.
- Twoja funkcja skrótu musi być deterministyczna.
- 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.
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's
? Co...?D=340275
słów iR=2^24
wyników mieszania losowy skrót ma spodziewaneD^2/(2*R) = 3450
pary kolidujące, z których niektóre nakładają się. Spodziewane sąD^3/(6*R^2) = 23
trzykrotne zderzenia i niewielka liczba większych zderzeń, co oznacza, że te potrójne są prawdopodobnie rozłączne. Daje to oczekiwane6829
słowa, które dzielą wartość skrótu ~70
w potrójnych, a reszta w parach. Standardowe odchylenie jest szacowane na118
, więc uzyskanie<6200
losowego skrótu jest w przybliżeniu zdarzeniem 5 sigma.Odpowiedzi:
W porządku, pójdę nauczyć się języka golfowego.
CJam, 140 bajtów, 3314 zderzających się słów
Definiuje blok (funkcja anonimowa). Aby przetestować, możesz dodać,
qN%%N*N
aby 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:Pyth, 140 bajtów,
35353396 zderzających się słówDefiniuje funkcję o nazwie
y
. Aby przetestować, możesz dodać,jmyd.z
aby 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: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.
źródło
Python,
53334991Uważam, że to pierwszy rywal, który uzyskał znacznie lepsze wyniki niż losowa wyrocznia.
źródło
def H(s):n=int(s.encode('hex'),16);return n%...
oszczędza 5 bajtów, na wypadek, gdybyś mógł ich jakoś wykorzystać ...2**24 == 8**8
.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
Python 2, 140 bajtów do wydrukowania,
466244714362 kolidujące słowaZainspirowany formą rozwiązania Kasperda, oczywiście - ale z ważnym dodatkiem transformacji afinicznej w przestrzeni modułu i zupełnie innych parametrów.
źródło
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!CJam,
4125393737913677To 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
Następujący port do Pythona może być używany z oficjalnym fragmentem oceniania:
źródło
h
w tym porcie Python odpowiada wbudowanemu CJam?b
(konwersja podstawowa).Python,
64466372To rozwiązanie osiąga mniejszą liczbę kolizji niż wszystkie poprzednie wpisy i potrzebuje tylko 44 z 140 bajtów dozwolonych dla kodu:
źródło
%(2**24-1)
, więc myślę, że dobrze byłoby poprosić o wyjaśnienia[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.CJam, 6273
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
źródło
JavaScript (ES6), 6389
Funkcja skrótu (105 bajtów):
Funkcja oceniania (NodeJS) (170 bajtów):
Wywołaj jako
node hash.js dictionary.txt
, gdziehash.js
jest skrypt,dictionary.txt
jest plikiem tekstowym słownika (bez ostatniego nowego wiersza) iF
jest zdefiniowany jako funkcja mieszająca.Dzięki Neil za golenie 9 bajtów funkcji haszowania!
źródło
((...)>>>0)%(1<<24)
ciebie prawdopodobnie możesz użyć(...)<<8>>>8
.i
.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 .
Oto krótki skrypt określający liczbę kolizji:
Właśnie próbowałem systematycznie wszystkich baz od samego
1
począ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.źródło
JavaScript (ES5), 6765
To jest CRC24 ogolony do 140 bajtów. Mogłem więcej golfa, ale chciałem uzyskać odpowiedź :)
Walidator w node.js:
źródło
Python, 340053
Straszna ocena ze strasznego algorytmu, ta odpowiedź istnieje bardziej, aby dać mały skrypt Pythona, który wyświetla ocenę.
Zaliczyć:
źródło
Python,
639063766359Można to uznać za trywialną modyfikację odpowiedzi Martina Büttnera .
źródło
[0, 2**24-1]
. Jedyne, co jest niedozwolone, to wypisywanie dowolnej liczby spoza tego zakresu, np .-1
Lub2**24
.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.
źródło
Matlab,
3082886206848Buduje 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.
Próbnik:
źródło
double
jawnie konwertować swojego znaku na . Możesz także użyćnumel
zamiastlength
. Nie jestem jednak pewien, co zrobiłbyś z tymi wszystkimi dodatkowymi bajtami!Ruby, 9309 zderzeń, 107 bajtów
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.
źródło
Java 8,
70546467Jest to zainspirowane (ale nie skopiowane z) wbudowaną funkcją java.lang.String.hashCode, więc nie krępuj się zgodnie z regułą # 2.
Zaliczyć:
źródło
hashes
sięMap<Integer, Integer> hashes = new HashMap<>()
, a następnie policzyć liczbę słów dla każdego hash, można uwzględnić je poprawnie.Python,
699568626732Po prostu prosta funkcja RSA. Dość kulawy, ale bije kilka odpowiedzi.
źródło
C ++:
711266946483647964126339 kolizji, 90 bajtówWdrożyłem naiwny algorytm genetyczny dla mojej tablicy współczynników. Zaktualizuję ten kod, ponieważ znajdzie lepsze. :)
Funkcja testowa:
źródło
C # 6251
6335Stałe 533 i 733
889 i 155dają najlepszy wynik spośród wszystkich, które do tej pory szukałem.źródło
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.
źródło
proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}
... prawda?Python 3, 89 bajtów, 6534 kolizje skrótów
Wszystkie duże magiczne liczby, które tu widzisz, są stałymi krówek.
źródło
JavaScript, 121 bajtów,
3268325032446354 (3185) kolizjiParametry (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
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
źródło
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
Clojure B, 6021, Pr = 1: 266,0e9
Clojure C, 6148, Pr = 1: 254,0e6
Clojure, 6431, Pr = 1: 2.69e3 (coś innego)
To była moja pierwotna funkcja skrótu ad-hoc, ma cztery dostrojone parametry.
źródło
r
). Ale nadal moim algorytmem wyszukiwania jest w zasadzie brutalna siła i nie jestem pewien, czy początkowy wybór mnożnikar
jest ważny, czy nie.f(n) % (8^8 - g(n))
.Ruby, 6473 zderzeń, 129 bajtów
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:
źródło
tcl
# 91 bajtów, 6508 kolizji91 bajtów, 6502 kolizji
Komputer nadal wykonuje wyszukiwanie w celu oceny, czy istnieje wartość powodująca mniej kolizji niż baza
147875, która wciąż jest rejestratorem.źródło