Ten kod golfowy został zainspirowany najnowszym artykułem Daily WTF, którego nie możesz poradzić sobie z prawdą! , który zawiera porównanie ciągów napisane jako:
String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())
Wyobraź sobie kłopoty, jakie spowodowałoby to dla zespołu Steve'a, gdyby String.hashCode
metoda Java została zaimplementowana w taki sposób "YES".hashCode() == "NO".hashCode()
. Wyzwanie, które proponuję tutaj, to:
Napisz,
h
używając jak najmniej znaków, funkcję skrótu (nazywam ją ) z parametrem ciągu i wartością zwracaną liczby całkowitej, którah("YES")
jest równah("NO")
.
Oczywiście byłoby to trywialne w przypadku funkcji typu def h(s): return 0
, która powoduje kolizję skrótu dla każdego łańcucha. Aby uczynić to wyzwanie bardziej interesującym, musisz przestrzegać następującej dodatkowej zasady:
Spośród pozostałych 18 277 możliwych ciągów składających się z trzech lub mniej wielkich liter ASCII (
^[A-Z]{0,3}$
), musi istnieć żadne kolizje hash.
Wyjaśnienie (wskazane przez Heiko Oberdiek): Łańcuch wejściowy może zawierać znaki inne niż A-Z
, a Twój kod musi mieć możliwość mieszania dowolnych ciągów. (Można jednak założyć, że dane wejściowe to ciąg znaków, a nie wskaźnik zerowy lub obiekt innego typu danych.) Jednak nie ma znaczenia, jaka jest wartość zwracana dla ciągów, które nie pasują ^[A-Z]{0,3}$
, o ile to liczba całkowita.
Ponadto, aby zaciemnić cel tej funkcji:
Kod nie może zawierać żadnej litery „Y”, „E”, „S”, „N” lub „O” (wielkimi lub małymi literami) w literałach znaków lub ciągów.
Oczywiście, ograniczenie to nie ma zastosowania do słów kluczowych językowych, tak else
, return
itp są w porządku.
YESNO
celu sprawdzenia tego konkretnego wyjątku.Odpowiedzi:
GolfScript: 19 znaków (24 znaki dla nazwanej funkcji)
To jest ciało funkcji. Przypisanie jej do nazwanej funkcji
h
wymaga pięciu dodatkowych znaków:(Ostatni średnik można pominąć, jeśli nie masz nic przeciwko pozostawieniu kopii kodu leżącej na stosie).
Rdzeń funkcji mieszającej jest
26base
, która oblicza sumę (26 n - K · K ; K = 1 .. n ), gdzie n jest liczbą znaków na wejściu i k oznacza kodu ASCII k -tego wprowadź znak. W przypadku danych wejściowych składających się z wielkich liter ASCII jest to bezkolizyjna funkcja skrótu. Reszta kodu porównuje wynik z 2107 (kod skrótu ) i, jeśli są równe, dodaje 59934, aby uzyskać 2701 + 59934 = 62041, czyli kod skrótu .NO
YES
Na przykład dane wyjściowe można znaleźć w tym demo online z przypadkami testowymi.
źródło
h('DXP') == h('KK') == 65884
.lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983
)32-bitowy Python 2.x (19)
RSA używa modułu semiprime, a to czyni go bezpiecznym, więc użycie jednego z moim algorytmem mieszającym powinno z pewnością uczynić go jeszcze lepszym! 1
Jest to czysta funkcja matematyczna, działa na wszystkich ciągach znaków (do diabła, działa na każdym haszowalnym obiekcie Pythona) i nie zawiera żadnych warunków warunkowych ani specjalnej obudowy! 32-bitowy język Python można zwykle wywoływać jak
python-32
w większości systemów, w których oba są zainstalowane 2 .Przetestowałem to i zwraca 18 278 różnych wartości dla 18 279 3-literowych lub mniejszych ciągów znaków. Przypisanie tego do funkcji zajmuje jeszcze 11 bajtów:
a
h('YES') == h('NO') == 188338253
.64-bitowy Python 2.x (19)
Ta sama oferta jak powyżej.
Aby wymyślić te liczby, użyto trochę modułowej matematyki. Szukałem funkcji
f
oraz modułn
taki, żehash(f('YES')) % n == hash(f('NO')) % n
. Jest to równoważne testowi, któryn
dzielid = hash(f('YES')) - hash(f('NO'))
, tzn. Musimy tylko sprawdzić współczynnikid
dla odpowiednich wartościn
.Ideał
n
znajduje się w okolicach 20000 ** 2, aby zmniejszyć ryzyko kolizji paradoksu urodzinowego. Znalezienie odpowiedniegon
okazuje się trochę próbą i błędem, grając ze wszystkimi czynnikamid
(zwykle nie ma ich wiele) i różnymi opcjami wyboru funkcjif
. Zauważ jednak, że próba i błąd są potrzebne tylko dlatego, że chciałem zrobićn
jak najmniejszy (do gry w golfa). Gdyby to nie było wymaganie, mógłbym po prostu wybraćd
jako mój moduł, który zwykle jest wystarczająco duży.Zauważ też, że nie można oderwać tej sztuczki za pomocą
f(s) = s
funkcji (funkcja tożsamości), ponieważ najbardziej prawy znak ciągu ma zasadniczo liniowy związek (w rzeczywistościXOR
związek) z końcowym hashem (pozostałe znaki wnoszą wkład w znacznie bardziej nieliniowy sposób ). Powtórzenie ciągu zapewnia zatem, że różnice między strunami zostaną wzmocnione, aby wyeliminować efekt zmiany tylko znaku znajdującego się najdalej po prawej stronie.1 To jest nonsens patentowy.
2 Hashowanie napisów w języku Python zależy od głównej wersji (2 vs 3) i bitowości (32-bit vs 64-bit). Nie zależy to od platformy AFAIK.
źródło
hash('YES'*9)
ma34876679
jako czynnik, podczas gdyhash('NO'*9)
ma34876679+537105043
jako czynnik. Ale skąd wiesz, że to537105043
był dobry moduł? tzn. nie spowodował innych kolizji?Perl,
534940 bajtówTest:
Wartości skrótu dla
YES
iNO
są takie same, a istnieje 18279 ciągów^[A-Z]{0,3}$
, które są wolne od kolizji, z wyjątkiem jedynej kolizji dlaYES
iNO
.Nie golfowany:
Starsza wersja, 49 bajtów
Ponieważ nowy algorytm jest nieco inny, zachowuję starą wersję.
Test:
Nie golfowany:
Edycje:
"\0"
jako bajtu wypełnienia pozwala zaoszczędzić 4 bajty w porównaniu do$"
.źródło
5457241
i20047
skąd pochodzą? Jak obliczyć te liczby? Z góry dziękuję.YES
w hex jest594553
. 0x594553 = 5850451.NO
w hex jest4e4f
. 0x4e4f = 20047.Python: 63
Niezwykle kiepskie rozwiązanie:
Działa, interpretując ciągi alfanumeryczne jako liczby podstawowe 36, i zwracając 0 dla wszystkiego innego. Istnieje wyraźny specjalny przypadek, aby sprawdzić wartość zwracaną 852 (NIE) i zamiast tego zwrócić 44596 (TAK).
źródło
try:
i całą trzecią linię. Można również zapisać kilka ukąszeń przez posiadające każdą logiczną linię na samym rzeczywistej linii, oddzielone średnikami (def h(s):r=int(s,36);return(r,44596)[r==852]
)Pure Bash, 29 bajtów (ciało funkcji)
To po prostu traktuje łańcuch wejściowy jako liczbę podstawową 36 i konwertuje na dziesiętny, a następnie zajmuje się
NO
przypadkiem specjalnym .Wynik:
źródło
Rubinowy, 51 bajtów
kod testowy:
wynik :
źródło
JavaScript ( ES6 ) 54 bajty
źródło
Java -
9477Rozwinięty:
Narracyjny - dla
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)
mam rację?źródło
CJam, 15 bajtów
Działa jako rozwiązanie GolfScript poniżej. Wypróbuj online.
GolfScript, 17 bajtów
To podejście opiera się na odpowiedziach Nneonneo i Ilmari Karonen .
Jak to działa
Wybór algorytmu
Zaczynamy od
{b base}:h
, tzn. Ciąg wejściowy jest uważany za liczbę podstawową-b. Dopókib > 25
,h
to inyective.Otrzymujemy kolizję dla ciągów „TAK” i „NIE”, jeśli zmodyfikujemy
h
w następujący sposób :,{x base n}:h
gdzien
jest dzielnik"YES" h "NO" h -
.Niestety, oznacza to będziemy również uzyskać kolizję dla np
YET
iNP
. Aby temu zapobiec, musimy przyjąć liczbę bazową b w sposób nieliniowy, zanim weźmiemy moduł.Najkrótszym sposobem na osiągnięcie tego w GolfScript jest pomnożenie liczby bazowej b przez siebie (tj. Podniesienie jej do kwadratu).
h
jest teraz{base b .* n %}:h
.Pozostaje tylko znaleźć odpowiednie wartości dla
b
in
. Możemy to osiągnąć brutalną siłą:Najkrótsze możliwe wartości
b n
to:Testowanie
źródło
JavaScript (ES6) - 38 znaków (33 funkcje znaku)
Przypadki testowe:
Wyjaśnienie:
Po pierwsze, pozwól, że przedstawię ci
NaN
- „Not A Number” - w JavaScript. To jest liczba:Tak jak:
Jego szczególną właściwością jest to, że nigdy się nie równa . Moja funkcja zwraca,
1
jeśli ciąg jestYES
lubNO
, iNaN
dla dowolnego innego ciągu.To nie łamie reguł, ponieważ nie byłoby kolizji skrótu dla żadnego innego ciągu;) (
NaN !== NaN
pokazane powyżej w przypadkach testowych).A moje marzenie się spełnia: pokonanie Basha, Perla i Ruby pod względem długości kodu!
Nieskluczony kod:
Jeśli ta wartość to
"WUVT"
lub"Tk8="
, zwróć1
. W przeciwnym razie wróćco by było
NaN
.źródło
^\d+$
. A JS traktujeNaN
jak liczbę. Możesz pomnożyć go przez liczbę, dodawać, dzielić, odejmować, tak jak w przypadku liczb. Jest to specjalna właściwość JavaScript. Korzystanie z niego nie jest szkodliwe. Tak nazywamy zginanie reguł ;)Object.is()
i twierdzić, że to nadal kolizja…==
do porównania operatora równości ( ), co zagwarantuje, że nie wystąpi kolizja skrótu dla dowolnego łańcucha oprócz „TAK” lub „NIE”.NaN
nie liczy się jako kolizja wydaje się tanie, to rozwiązanie ma kolizji z ciągówNA
poprzezNP
iYEQ
dziękiYET
Python 92
Funkcja mieszająca łączy wartości porządkowe znaków ASCII, instrukcja print zapewnia, że dwa pożądane dane wejściowe kolidują.
źródło
ECMAScript 6 (30 bajtów)
Próbowałem uniknąć przypisania zmiennej, słowa kluczowego return i funkcji, i wygląda to na świetny sposób na uniknięcie tych bzdur (w pewnym sensie wygląda to również na programowanie funkcjonalne). W przeciwieństwie do innych rozwiązań, nie zależy od
btoa
lubatob
, co nie jest ECMAScript 6, ale HTML5.0+
jest potrzebne, aby mógł parsować dowolne ciągi.źródło
a=>parseInt(0+a,36)-852||43744
Java - 45 (lub 62?)
Nie mam pojęcia, jak rzetelnie ocenić, biorąc pod uwagę, co trzeba uruchomić program w Javie, czy muszę podać definicję funkcji? Nie krępuj się odpowiednio edytować i dostosowywać mój wynik. Obecnie oceniam w ten sam sposób, co odpowiedź @OldCurmudgeon. Dodaj 17,
int h(String t){}
jeśli jest to wymagane:Nie golfowane z uprzężą testową:
źródło
A przegrany jest ...
Przenośnik, 145 znaków
Zasadniczo ten program działa na zasadzie 26 znaków na znakach. Następnie sprawdza, czy skrót jest równy 12999 (kod skrótu TAK), a jeśli tak, wydrukuj 404 (kod skrótu NIE), w przeciwnym razie po prostu wydrukuje kod skrótu.
Conveyor to stworzony przeze mnie język, który jest obecnie w fazie beta, ale interpreter wraz z kilkoma przykładami i kodem źródłowym można znaleźć tutaj: https://github.com/loovjo/Conveyor
źródło
C # 4.5 (112 bajtów)
Działająca (?) Wersja próby podziemnej kolejki, w C #. Łączy bajty ciągu z 32-bitową liczbą całkowitą (działa tylko do 4 znaków), następnie OR zwraca wynik w stosunku do wyniku odpowiednio dla „TAK” i „NIE”, a następnie OR je razem.
Chociaż w pewnym momencie może się zderzyć, nie powinno tak być w przypadku żadnego ^ [AZ] {2,3} $ innego niż „TAK” i „NIE”.
źródło
Bez komentarza - 31 (treść funkcji: 26)
Całkiem proste rozwiązanie. ;) Działa dla wszystkich ciągów UTF-8.
OBJAŚNIENIE:
'
jest oczywiście funkcją. Najpierw sprawdza, czy*
(jego dane wejściowe) są równe|,,|+|"#|
(|NO|
). Jeśli tak, zwraca|, |+|-%3|
(|YES|
) - w przeciwnym razie po prostu zwraca*
.źródło
C 54
Konwertuj ciąg na liczbę całkowitą - „NIE” i pomnóż go przez tę samą wartość + „NIE” - „TAK”, aby uzyskać 0 dla „NIE” i „TAK” i niezerowe dla dowolnego innego ciągu w określonym zakresie.
Wszystkie wartości na komputerze z systemem Windows 7, jeśli istnieją jakiekolwiek obawy Endian.
źródło
Stax ,
1211 bajtówUruchom i debuguj
Tłumaczy dane wejściowe jako base-36, odejmuje 852, a następnie zamienia 0 na 43744. Jest to doskonałe rozwiązanie Konrada .
źródło
CoffeeScript - 36
Powinny wrócić
1
doYES
iNO
, i cokolwiek zniekształconego nonsensuatob
produkuje dla wszystkiego innego, co nie jest ciągiem base64.Odpowiednik JavaScript ( nie kod JS z kompilatora CS):
źródło
_
gdy wejście nie jest „TAK” lub „NIE”.Oto super kulawy. TAK LAMO, ŻE TO NIE DZIAŁA
Python 2.7 - 79 bajtówNajpierw otrzymujemy sumę (wartość ascii każdego znaku) * 100 ^ (pozycja tego znaku w ciągu). Następnie mnożymy (ten wynik - 7978) i (ten wynik - 836989), aby uzyskać naszą ostateczną odpowiedź. 7978 i 836989 są wynikami dla „TAK” i „NIE” pierwszego bitu, więc dla TAK i NIE mnożymy przez 0.
To nie powinno mieć żadnych kolizji? Nie mam ochoty testować na 18000 możliwych kontrpróbkach, ale jeśli doszło do niezamierzonej kolizji, mogę rzucić na nią kolejne 0,
100
a wtedy naprawdę nie powinno być żadnych kolizji.Rozczarowany, że nie mogłem użyć
lambda
do tego, ale nie chciałem wykonać całego obliczenia dwa razy, więc musiałem zapisać go w zmiennej.Proszę, nie pozwól temu wygrać. Jest bardzo kiepski i nie zasługuję na to.
źródło