W tym wyzwaniu kodu napiszesz funkcję skrótu w 140 bajtach ¹ 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 ²⁴ -1]) jako wynik.

Twoja funkcja haszująca będzie oceniana dla każdego słowa w tym dużym słowniku brytyjsko-angielskim ² . 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.}

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.

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

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.

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

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

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

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!

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 ²⁴ .

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.

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

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

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 .

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

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

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.

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);
    }
}

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)

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;
}

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.

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"

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.

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

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.

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

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.