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.hashCodemetoda Java została zaimplementowana w taki sposób "YES".hashCode() == "NO".hashCode(). Wyzwanie, które proponuję tutaj, to:

Napisz, hużywając jak najmniej znaków, funkcję skrótu (nazywam ją ) z parametrem ciągu i wartością zwracaną liczby całkowitej, która h("YES")jest równa h("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, returnitp są w porządku.

GolfScript: 19 znaków (24 znaki dla nazwanej funkcji)

26base.2107=59934*+

To jest ciało funkcji. Przypisanie jej do nazwanej funkcji hwymaga pięciu dodatkowych znaków:

{26base.2107=59934*+}:h;

(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 .NOYES

Na przykład dane wyjściowe można znaleźć w tym demo online z przypadkami testowymi.

32-bitowy Python 2.x (19)

hash(w*9)%537105043

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! ¹

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-32w większości systemów, w których oba są zainstalowane ² .

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:

h=lambda w:hash(w*9)%537105043

a h('YES') == h('NO') == 188338253.

64-bitowy Python 2.x (19)

hash(w*2)%105706823

Ta sama oferta jak powyżej.

Aby wymyślić te liczby, użyto trochę modułowej matematyki. Szukałem funkcji foraz moduł ntaki, że hash(f('YES')) % n == hash(f('NO')) % n. Jest to równoważne testowi, który ndzieli d = hash(f('YES')) - hash(f('NO')), tzn. Musimy tylko sprawdzić współczynniki ddla odpowiednich wartości n.

Ideał nznajduje się w okolicach 20000 ** 2, aby zmniejszyć ryzyko kolizji paradoksu urodzinowego. Znalezienie odpowiedniego nokazuje się trochę próbą i błędem, grając ze wszystkimi czynnikami d(zwykle nie ma ich wiele) i różnymi opcjami wyboru funkcji f. Zauważ jednak, że próba i błąd są potrzebne tylko dlatego, że chciałem zrobić njak najmniejszy (do gry w golfa). Gdyby to nie było wymaganie, mógłbym po prostu wybrać djako mój moduł, który zwykle jest wystarczająco duży.

Zauważ też, że nie można oderwać tej sztuczki za pomocą f(s) = sfunkcji (funkcja tożsamości), ponieważ najbardziej prawy znak ciągu ma zasadniczo liniowy związek (w rzeczywistości XORzwią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.

¹ To jest nonsens patentowy.
² 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.

Perl, 53 49 40 bajtów

sub h{hex(unpack H6,pop)-20047||5830404}

Test:

h('YES') = 5830404
h('NO')  = 5830404
Keys:   18279
Values: 18278

Wartości skrótu dla YESi NOsą takie same, a istnieje 18279 ciągów ^[A-Z]{0,3}$, które są wolne od kolizji, z wyjątkiem jedynej kolizji dla YESi NO.

Nie golfowany:

sub h {
    hex(unpack("H6", pop())) - 20047 || 5830404;
    # The argument is the first and only element in the argument array @_.
    # "pop" gets the argument from array @_ (from the end).
    # The first three bytes of the argument or less, if the argument
    # is shorter, are converted to a hex string, examples:
    #   "YES" -> "594553"
    #   "NO"  -> "4e4f"
    # Then the hex string is converted to a number by function "hex":
    #   0x594553 = 5850451
    #   0x4e4f   =   20047
    # The value for "NO" is subtracted, examples:
    #   case "YES": 5850451 - 20047 = 5830404
    #   case "NO":    20047 - 20047 =       0
    # If the argument is "NO", the subtraction is zero, therefore
    # 5830404 is returned, the result of "YES".
}

# Test
my %cache;
sub addcache ($) {$cache{$_[0]} = h($_[0])}

# Check entries 'YES' and 'NO'
addcache 'YES';
addcache 'NO';
print "h('YES') = $cache{'YES'}\n";
print "h('NO')  = $cache{'NO'}\n";

# Fill cache with all strings /^[A-Z]{0-3}$/
addcache '';
for my $one (A..Z) {
    addcache $one;
    for (A..Z) {
        my $two = "$one$_";
        addcache $two;
        for (A..Z) {
            my $three = "$two$_";
            addcache $three;
        }
    }
}
# Compare number of keys with number of unique values
my $keys = keys %cache;
my %hash;
@hash{values %cache} = 1 x $keys;
$values = keys %hash;
print "Keys:   $keys\n";
print "Values: $values\n";

Starsza wersja, 49 bajtów

Ponieważ nowy algorytm jest nieco inny, zachowuję starą wersję.

sub h{($_=unpack V,pop."\0"x4)==20302?5457241:$_}

Test:

h('YES') = 5457241
h('NO')  = 5457241
Keys:   18279
Values: 18278

Nie golfowany:

sub h {
    $_ = unpack('V', pop() . ($" x 4);
        # pop():  gets the argument (we have only one).
        # $" x 4: generates the string "    " (four spaces);
        #   adding the four spaces ensures that the string is long
        #   enough for unpack's template "V".
        # unpack('V', ...): takes the first four bytes as
        #   unsigned long 32-bit integer in little-endian ("VAX") order.
    $_ == 20302 ? 5457241 : $_;
        # If the hash code would be "NO", return the value for "YES".
}

Edycje:

• Użycie "\0"jako bajtu wypełnienia pozwala zaoszczędzić 4 bajty w porównaniu do $".

Python: 63

Niezwykle kiepskie rozwiązanie:

def h(s):
 try:r=int(s,36)
 except:r=0
 return(r,44596)[r==852]

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).

Pure Bash, 29 bajtów (ciało funkcji)

h()(echo $[n=36#$1,n-852?n:44596])

To po prostu traktuje łańcuch wejściowy jako liczbę podstawową 36 i konwertuje na dziesiętny, a następnie zajmuje się NOprzypadkiem specjalnym .

Wynik:

$ h A.
10
$ h B
11
$ h CAT
15941
$ h NIE
44596
$ h TAK
44596
$ h ZZZ
46655
$

Rubinowy, 51 bajtów

h=->s{d=s.unpack('C*').join;d=~/896983|^7879$/?0:d}

kod testowy:

h=->s{d=s.unpack('C*').join;d=~/896983|^7879$/?0:d}

puts 'YES : '+h.call('YES').to_s # 0
puts 'NO : '+h.call('NO').to_s # 0
puts 'NOX : '+h.call('NOX').to_s # 787988
puts 'FNO : '+h.call('FNO').to_s # 707879
puts ''

values = Hash[]
n = 0
('A'..'Z').each{|c|
    values[c] = h.call(c)
    ('A'..'Z').each{|c2|
        values[c+c2] = h.call(c+c2)
        ('A'..'Z').each{|c3|
            values[c+c2+c3] = h.call(c+c2+c3)
            n += 1
        }
    }
}
puts 'tested '+n.to_s
duplicate = Hash.new()

values.each{|k, e|
    if duplicate.has_key?(e)
        puts 'duplicate : "'+k+'" = "'+duplicate[e].to_s+'" ('+e.to_s+')'
    else
        duplicate[e] = k
    end
}

wynik :

YES : 0
NO : 0
NOX : 787988
FNO : 707879

tested 17576
duplicate : "YES" = "NO" (0)

JavaScript ( ES6 ) 54 bajty

f=s=>[x.charCodeAt()for(x of s)].join('')^7879||897296

f('YES'); // 897296
f('NO'); // 897296
f('MAYBE'); // -824036582

Java - 94 77

int h=new BigInteger(s.getBytes()).intValue();return Math.abs(h-(h^5835548));

Rozwinięty:

int hashCode(String s) {
    int h = new BigInteger(s.getBytes()).intValue();
    return Math.abs(h - (h ^ 5835548));
}

Narracyjny - dla f(s) = BigInteger(s.getBytes()):

• f("YES") xor f("NO") = 5835548
• Więc f("YES") xor 5835548 = f("NO")
• Więc f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)mam rację?

CJam, 15 bajtów

q42b_*81991617%

Działa jako rozwiązanie GolfScript poniżej. Wypróbuj online.

GolfScript, 17 bajtów

42base.*81991617%

To podejście opiera się na odpowiedziach Nneonneo i Ilmari Karonen .

Jak to działa

42base    # Interpret the input string as a base 42 number.
          # "YES" is [ 89 69 83 ] in ASCII, so it becomes 42 * (42 * 89 + 69) + 83 = 159977.
          # "NO" is [ 78 79 ] in ASCII, so it becomes 42 * 78 + 79 = 3355.
          #
.*        # Square. "YES" becomes 25592640529, "NO" becomes 11256025.
          #
81991617% # "YES" becomes 11256025.

Wybór algorytmu

Zaczynamy od {b base}:h, tzn. Ciąg wejściowy jest uważany za liczbę podstawową-b. Dopóki b > 25, hto inyective.

Otrzymujemy kolizję dla ciągów „TAK” i „NIE”, jeśli zmodyfikujemy hw następujący sposób :, {x base n}:hgdzie njest dzielnik "YES" h "NO" h -.

Niestety, oznacza to będziemy również uzyskać kolizję dla np YETi NP. 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). hjest teraz {base b .* n %}:h.

Pozostaje tylko znaleźć odpowiednie wartości dla bi n. Możemy to osiągnąć brutalną siłą:

for((b=26;b<100;b++)){
    P=($(golfscript <<< "['YES' 'NO']{$b base.*}/-" | factor | cut -d\  -f 2-))

    for n in $(for((i=0;i<2**${#P[@]};i++)){
        for((n=1,j=0;j<${#P[@]};n*=${P[j]}**((i>>j)&1),j++)){ :;};echo $n;} | sort -nu);{
            [[ $n -ge 18277 && $(echo -n '' {A..Z}{,{A..Z}{,{A..Z}}} |
                golfscript <(echo "' '/[{$b base.*$n%}/].&,")) = 18278 ]] &&
            echo $b $n && break
    }
}

Najkrótsze możliwe wartości b nto:

37 92176978
42 81991617

Testowanie

$ echo -n '' {A..Z}{,{A..Z}{,{A..Z}}} |
     golfscript <(echo '{42base.*81991617%}:h;" "/{.`"\t"+\h+puts}/') |
     sort -k 2n |
     uniq -Df 1
"NO"    11256025
"YES"   11256025

JavaScript (ES6) - 38 znaków (33 funkcje znaku)

h=s=>(a=btoa(s))=="WUVT"|a=="Tk8="||+s

Przypadki testowe:

var l = console.log;
l(  h("YES")  );                // 1
l(  h("NO")  );                 // 1
l(  h("ABC")  );                // NaN     
l(  h("WIN")  );                // NaN
l(  h("YES") === h("NO")  );    // true
l(  h("ABC") === h("WIN")  );   // false
l(  h("WIN") === h("YES")  );   // false

l(  NaN === NaN  );             // false

Wyjaśnienie:

Po pierwsze, pozwól, że przedstawię ci NaN- „Not A Number” - w JavaScript. To jest liczba:

typeof NaN  // number

Tak jak:

typeof 42   // number

Jego szczególną właściwością jest to, że nigdy się nie równa . Moja funkcja zwraca, 1jeśli ciąg jest YESlub NO, i NaNdla dowolnego innego ciągu.

To nie łamie reguł, ponieważ nie byłoby kolizji skrótu dla żadnego innego ciągu;) ( NaN !== NaNpokazane 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:

h =  // h is a function 
s => // s = string argument

( ( a = btoa(s) )  ==  "WUVT" | a == "Tk8=" )
        ^-- returns some value stored in `a`

Jeśli ta wartość to "WUVT"lub "Tk8=", zwróć 1. W przeciwnym razie wróć

+s // parseInt(s, 10)

co by było NaN.

Python 92

n=int("".join(map(str,map(ord,raw_input()))))    # hashing function
print n if 1+(n**2-904862*n)/7067329057 else-1   # input validation

Funkcja mieszająca łączy wartości porządkowe znaków ASCII, instrukcja print zapewnia, że ​​dwa pożądane dane wejściowe kolidują.

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 btoalub atob, co nie jest ECMAScript 6, ale HTML5. 0+jest potrzebne, aby mógł parsować dowolne ciągi.

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:

int h=t.hashCode();return h*h*3%1607172496;

Nie golfowane z uprzężą testową:

import static org.junit.Assert.*;

import java.util.*;

import org.junit.Test;

public class YesNo {
  @Test
  public void testHashValue() {
    YesNo yesNo = new YesNo();
    Set<Integer> set = new HashSet<>();

    assertEquals(yesNo.hash("YES"), yesNo.hash("NO"));

    set.add(yesNo.hash(""));
    for(char i = 'A'; i <= 'Z'; i++) {
      set.add(yesNo.hash("" + i));
      for(char j = 'A'; j <= 'Z'; j++) {
        set.add(yesNo.hash("" + i + j));
        for(char k = 'A'; k <= 'Z'; k++) {
          set.add(yesNo.hash("" + i + j + k));
        }
      }
    }
    assertEquals(18278, set.size());
  }

  int hash(String toHash) {
    int hashValue=toHash.hashCode();
    return hashValue*hashValue*3%1607172496;
  }
}

A przegrany jest ...

Przenośnik, 145 znaków

 I
>#<
 26*)2**\88
 >========*
 ^    \ \+-
 ^=====#==<
5**222P:
5======<
5***26*)*(\P\:@e25*:*)4*,F
>==============#=========
             P,F

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

C # 4.5 (112 bajtów)

int h(string s){int code=s.Select((v,i)=>((int)v)<<(2*(i-1))).Sum();return(code|1073742225)|(code|-2147483569);}

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”.

Bez komentarza - 31 (treść funkcji: 26)

'=|*==|,,|+|"#|[|,  |+|-%3|]*|:

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 *.

C 54

h(char *c){int d=*(int*)c-20302;return d*(d-5436939);}

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.

Stax , 12 11 bajtów

ì≤ïøZ‼kESa←

Uruchom 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 .

CoffeeScript - 36

Powinny wrócić 1do YESi NO, i cokolwiek zniekształconego nonsensu atobprodukuje dla wszystkiego innego, co nie jest ciągiem base64.

h=(s)->_=atob s;_ in["`D","4"]&&1||_

Odpowiednik JavaScript ( nie kod JS z kompilatora CS):

function h( s ) {
    var _ = atob( s );

    if( _ === "`D" || _ === "4" )
        return 1;
    else
        return _;
}

Oto super kulawy. TAK LAMO, ŻE TO NIE DZIAŁA

Python 2.7 - 79 bajtów

def h(s):n=sum(100**i*ord(c)for i,c in enumerate(s));return (n-7978)*(n-836989)

Najpierw 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, 100a wtedy naprawdę nie powinno być żadnych kolizji.

Rozczarowany, że nie mogłem użyć lambdado 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.