Tweetable Hash-Funktion Herausforderung

73

In dieser schreiben Sie eine Hash-Funktion in 140 Byte 1 oder weniger Quellcode. Die Hash-Funktion muss eine ASCII-Zeichenfolge als Eingabe annehmen und eine vorzeichenlose 24-Bit-Ganzzahl ([0, 2 24 -1]) als Ausgabe zurückgeben.

Ihre Hash-Funktion wird für jedes Wort in diesem großen Britisch-Englisch-Wörterbuch 2 ausgewertet . Ihre Punktzahl ist die Anzahl der Wörter, die einen Hash-Wert mit einem anderen Wort teilen (eine Kollision).

Die niedrigste Punktzahl gewinnt, Unentschieden durch das erste Plakat.

Testfall

Testen Sie Ihr Scoring-Skript vor dem Absenden anhand der folgenden Eingabe:

duplicate
duplicate
duplicate
duplicate

Wenn es eine andere Punktzahl als 4 gibt, ist es fehlerhaft.


Regeln klären:

  1. Ihre Hash-Funktion muss mit einer einzelnen Zeichenfolge ausgeführt werden, nicht mit einem ganzen Array. Außerdem führt Ihre Hash-Funktion möglicherweise keine anderen E / A-Vorgänge als die Eingabezeichenfolge und die Ausgabe-Ganzzahl aus.
  2. Eingebaute Hash-Funktionen oder ähnliche Funktionen (z. B. Verschlüsselung für verwürfelte Bytes) sind nicht zulässig.
  3. Ihre Hash-Funktion muss deterministisch sein.
  4. Im Gegensatz zu den meisten anderen Wettbewerben ist die Optimierung speziell für die Bewertungseingabe zulässig.

1 Ich bin mir bewusst, dass Twitter Zeichen anstelle von Bytes begrenzt, aber der Einfachheit halber werden wir Bytes als Grenze für diese Herausforderung verwenden.
2 Geändert von Debians britisch-riesigem Format , wobei alle Nicht-ASCII-Wörter entfernt werden.

orlp
quelle
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Was zum...?
Luis Mendo
8
@DonMuesli en.wikipedia.org/wiki/Llanfairpwllgwyngyll (Spaß Tatsache: dieses Wort ist auch in Jelly integrierte Kompressions Wörterbuch)
Martin Ender
8
Ich denke, Sie sollten integrierte Wörterbücher nicht zulassen.
Dennis
4
Als Referenz: Wenn Sie die 24 MSB von SHA-512 nehmen, erhalten Sie eine Punktzahl von 6816.
Dennis,
10
Einige Back-of-the-Envelope-Berechnungen: Bei D=340275Wörtern und R=2^24Hash-Ausgaben hat ein zufälliger Hash erwartete D^2/(2*R) = 3450kollidierende Paare, von denen sich einige überlappen. Es gibt erwartete D^3/(6*R^2) = 23kollidierende Tripel und eine vernachlässigbare Anzahl größerer Kollisionen, was bedeutet, dass diese Tripel wahrscheinlich disjunkt sind. Dies ergibt erwartete 6829Wörter, die einen Hash-Wert teilen, ~ 70in Dreiergruppen und den Rest in Paaren. Die Standardabweichung wird auf geschätzt 118, so dass das Erhalten <6200eines zufälligen Hash ungefähr ein 5-Sigma-Ereignis ist.
Xnor

Antworten:

11

In Ordnung, ich werde eine Golfsprache lernen.

CJam, 140 Bytes, 3314 kollidierende Wörter

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#)%}

Definiert einen Block (anonyme Funktion). Zum Testen können Sie hinzufügen qN%%N*N, dass Sie die durch Zeilenumbrüche getrennte Liste von Wörtern in stdin aufnehmen und eine durch Zeilenumbrüche getrennte Liste von Hashes in stdout schreiben. Äquivalenter Python-Code:

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 Bytes, 3535 3396 kollidierende Wörter

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

Definiert eine Funktion mit dem Namen y. Zum Testen können Sie hinzufügen jmyd.z, dass Sie die durch Zeilenumbrüche getrennte Liste von Wörtern in stdin aufnehmen und eine durch Zeilenumbrüche getrennte Liste von Hashes in stdout schreiben. Äquivalenter Python-Code:

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

Theoretische Grenzen

Wie gut können wir damit rechnen? Hier ist eine grafische Darstellung von x, der Anzahl der kollidierenden Wörter, und y, der Entropie in Bytes, die erforderlich ist, um höchstens x kollidierende Wörter zu erhalten. Zum Beispiel sagt uns der Punkt (2835, 140), dass eine Zufallsfunktion höchstens 2835 kollidierende Wörter mit einer Wahrscheinlichkeit von 1/256 ** 140 erhält, so dass es äußerst unwahrscheinlich ist, dass wir jemals in der Lage sein werden, viel besser als mit 140 zu werden Byte Code.

Graph

Anders Kaseorg
quelle
Gute Analyse der theoretischen Grenzen. Um diese theoretische Grenze zu überschreiten, müsste man wahrscheinlich eine Sprache mit eingebauten Funktionen verwenden, die für das betreffende Wörterbuch optimiert sind (was betrügen würde). Wenn die Sprache einen eingebauten kryptografischen Hash hat, kann das Limit in eine mehr oder weniger konstruktive Methode zum Finden einer optimalen Lösung umgewandelt werden. Beachten Sie Folgendes: $ h (w || c)% 2 ^ {24} $ wobei $ c $ eine Byte-String-Konstante ist. In einem zufälligen Orakelmodell konnte gezeigt werden, dass es sich mit hoher Wahrscheinlichkeit dem Optimum nähert. Natürlich wäre es nicht machbar, das $ c $ brachial zu erzwingen.
Kasperd
Wie haben Sie die Formel für das Diagramm berechnet? Wirklich interessant!
NikoNyrh
@NikoNyrh Dynamische Programmierung. Sei ( w , c , h ) ein Zustand mit w Wörtern, von denen c mit h verschiedenen Hashes kollidieren und die übrigen w - c alle verschiedene Hashes haben. Wenn wir ein zufälliges Wort hinzufügen, wird der Zustand ( w + 1, c , h ) mit der Wahrscheinlichkeit 1 - ( h + w - c ) / 2 ^ 24 oder ( w + 1, c + 1, h ) mit der Wahrscheinlichkeit h / 2 ^ 24 oder ( w + 1, c+ 2, h + 1) mit Wahrscheinlichkeit ( w - c ) / 2 ^ 24. Dann ist die mit x kollidierenden Wörtern graphisch dargestellte Endentropie die logarithmische Basis 1/256 der Summe der Wahrscheinlichkeiten bei Zuständen (340275, c , h ) mit cx .
Anders Kaseorg
Ich kann nicht glauben, dass niemand gefragt hat, wie Sie auf die Hash-Funktion gekommen sind. Das würde mich sehr interessieren.
Anush
22

Python, 5333 4991

Ich glaube, dies ist der erste Anwärter, der deutlich besser abschneidet als ein zufälliges Orakel.

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
quelle
1
Zauberei! def H(s):n=int(s.encode('hex'),16);return n%...spart 5 Bytes, falls Sie sie irgendwie verwenden können ...
Dennis
3
@ Tennis Ich hätte 5 Bytes verwenden können, um die Zeichenfolge 5 Bytes länger zu halten. Aber wenn ich die Länge ändere, müsste ich von vorne anfangen, die String-Konstante zu erstellen. Und ich bin mir nicht sicher, ob diese 5 Bytes mir eine ausreichende Verbesserung bringen werden, sodass es sich lohnt, mit dem Erstellen des Strings zu beginnen. Ich habe schon Stunden CPU-Zeit damit verbracht, die String-Konstante zu optimieren.
Kasperd
@ Tennis Ich denke, ein paar zusätzliche Bytes würden mir die Freiheit geben, einige Zeichen in der Konstante zu verwenden, die es braucht, zu entkommen. Auf diese Weise könnte ich möglicherweise einige zusätzliche Bytes verwenden, ohne die Zeichenfolge erneut erstellen zu müssen.
Kasperd
7
Wenn Sie ein anderes Byte wollen, 2**24 == 8**8.
Anders Kaseorg
20

Python 2, 140 Bytes, 4266 kollidierende Wörter

Ich wollte nicht wirklich mit der nicht druckbaren Bytes-Sache anfangen, da ihre Tweet-Fähigkeit unklar ist, aber nun, ich habe sie nicht gestartet. :-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 druckbare Bytes, 4662 4471 4362 kollidierende Wörter

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

Inspiriert von der Form von Kasperds Lösung - aber mit der wichtigen Hinzufügung einer affinen Transformation auf den Modulraum und völlig anderen Parametern.

Anders Kaseorg
quelle
+1 Ich gebe nicht kampflos auf. Aber ich denke, ich muss aufhören, meine aktuelle Lösung zu optimieren, und einen anderen Ansatz finden, weil ich Sie nicht schlagen werde, wenn ich weiterhin meinen aktuellen Ansatz zur Optimierung der Parameter verwende. Ich werde mit einer Änderung an meiner Lösung zurück sein, sobald ich deine
besiegt habe
@kasperd: Genial, bring es auf. :-P
Anders Kaseorg
1
@AndersKaseorg Wie findest du den String?
Nur ASCII
@AndersKaseorg Ich habe es geschafft, meine Parametersuche erheblich zu beschleunigen. Und ich habe ein Hindernis beseitigt, bei dem meine Suche nach suboptimalen Lösungen hängen blieb. Aber ich konnte es immer noch nicht besser machen als 4885. Nachdem ich überlegt hatte, warum ich es nicht weiter machen konnte, wurde mir plötzlich klar, was mit meiner Lösung nicht stimmt und wie es behoben werden kann. Jetzt macht die affine Transformation in Ihrer Lösung für mich vollkommen Sinn. Ich denke, der einzige Weg, den ich nachholen kann, ist, selbst eine affine Transformation durchzuführen.
Kasperd
1
@kasperd: Sehr schön. Bei der Suche nach einer besseren Zeichenfolge n%(8**8-ord('…'[n%70]))ohne andere Parameteränderungen hatte ich es nur geschafft, auf 4995 zu kommen. Es sieht also so aus, als hätte Ihr neuer Optimierer meine eingeholt. Das wird jetzt interessanter!
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*+}

Dieser Ansatz unterteilt Domain und Codomain in 110 disjunkte Mengen und definiert für jedes Paar eine etwas andere Hash-Funktion.

Wertung / Verifikation

$ 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

Der folgende Port für Python kann mit dem offiziellen Scoring-Snippet verwendet werden:

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
quelle
1
Ich habe meinen Code zur einfachen Überprüfung nach Python portiert.
Dennis
Entspricht hdieser Python-Port einem eingebauten CJam?
Kasperd
Ja. Es ist CJam's b( Basisumwandlung ).
Dennis
Befindet sich Ihr Bewertungsprozess in der Bash-Phase?
GamrCorps
@GamrCorps Ja, das ist Bash.
Dennis
11

Python, 6446 6372


Diese Lösung erzielt eine geringere Anzahl von Kollisionen als alle vorherigen Einträge und benötigt nur 44 der 140 für den Code zulässigen Bytes:

H=lambda s:int(s.encode('hex'),16)%16727401
Kasperd
quelle
2
@ mbomb007 Orlps eigene Einreichung tut %(2**24-1), so denke ich, es könnte gut sein, um Klärung zu bitten
Sp3000
12
@ mbomb007 Die Herausforderung sagt nichts. Die Funktion muss eine ASCII-Zeichenfolge als Eingabe und eine Ganzzahl in diesem Bereich ausgeben. Unabhängig davon, welchen Eingang Sie meiner Funktion geben, liegt der Ausgang in diesem Bereich. Die mathematische Definition der Wortfunktion erfordert nicht, dass jede erlaubte Ausgabe erzeugt wird. Wenn Sie das wollten, war der mathematische Ausdruck, den Sie verwenden würden, eine surjektive Funktion. Aber das Wort Surjektiv wurde in den Anforderungen nicht verwendet.
Kasperd
@ mbomb007: Hash-Funktionen müssen nicht surjektiv sein. Beispielsweise können viele speicheradressbasierte Hash-Funktionen aufgrund der Speicherausrichtung nur ein Vielfaches einer kleinen Zweierpotenz erzeugen, einschließlich des Standardobjekt-Hash in älteren Versionen von Python. Viele Hash-Funktionen haben sogar eine kleinere Domain als Codomain, so dass sie sowieso nicht surjektiv sein können.
user2357112
3
@ mbomb007 - Da es weit mehr Zahlenwerte [0, 2**24-1]als Wörter in der englischen Sprache gibt, wäre es mathematisch unmöglich , einen Hash zu erstellen , bei dem jeder einzelne Wert in diesem Bereich möglich wäre.
Darrel Hoffman
7

CJam, 6273

{49f^245b16777213%}

XOR jedes Zeichen mit 49 , reduziere den resultierenden String mit x, y ↦ 245x + y und nimm das Residuum Modulo 16.777.213 (die größte 24-Bit-Primzahl).

Wertung

$ 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
quelle
Ich habe den Algorithmus aus Ihrer Beschreibung in Python neu implementiert. Ich kann bestätigen, dass Ihre Punktzahl mit der offiziellen Punktzahlberechnung abgerechnet wird.
Kasperd
7

JavaScript (ES6), 6389

Die Hash-Funktion (105 Bytes):

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

Die Bewertungsfunktion (NodeJS) (170 Bytes):

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)

Rufe auf als node hash.js dictionary.txt, wo hash.jsist das Skript, dictionary.txtist die Wörterbuch-Textdatei (ohne die letzte neue Zeile) und Fist als die Hash-Funktion definiert.

Vielen Dank, Neil, dass du 9 Bytes von der Hashing-Funktion entfernt hast!

Mwr247
quelle
Warum die Zuordnung zu einem? Auch ((...)>>>0)%(1<<24)kann man wahrscheinlich anstelle von verwenden (...)<<8>>>8.
Neil
@ Neil Weil Alphabet, und ich bin langweilig = P Auch schön bitweise Mathe! Das sparte 7 Bytes =)
Mwr247
Gut, dass dies kein Codegolf ist, sonst müsste ich Sie auch für die unbenutzte Variable iinteressieren.
Neil
@Neil Crap> _ <Ich habe das benutzt, als ich einige alternative Hashing-Ideen getestet und vergessen habe, XD zu entfernen in die gleichen 140 Bytes, so hilft jedes Bit;)
Mwr247
1
@ Sp3000 Gah, ich verstehe was du meinst. Meins zählt nicht die, die sich zu Beginn der Kollision dort befinden. Ich werde das reparieren.
Mwr247
5

Mathematica, 6473

Der nächste Schritt nach oben ... Anstatt die Zeichencodes zu summieren, behandeln wir sie als die Ziffern einer Basis-151-Zahl, bevor wir sie modulo 2 24 nehmen .

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

Hier ist ein kurzes Skript, um die Anzahl der Kollisionen zu bestimmen:

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

Ich habe gerade alle Basen systematisch von Anfang an ausprobiert 1und bis jetzt ergab Basis 151 die wenigsten Kollisionen. Ich werde ein paar mehr versuchen, um die Punktzahl weiter zu senken, aber das Testen ist etwas langsam.

Martin Ender
quelle
5

Javascript (ES5), 6765

Dies ist CRC24 bis zu 140 Bytes rasiert. Könnte mehr Golf spielen, wollte aber meine Antwort bekommen :)

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}

Validator in 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
quelle
Willkommen bei Programming Puzzles & Code Golf!
Alex A.
... und danke für den herzlichen Empfang @AlexA.!
Binarymax
5

Python, 340053

Eine schreckliche Punktzahl von einem schrecklichen Algorithmus. Diese Antwort gibt eher ein kleines Python-Skript an, das die Punktzahl anzeigt.

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

Um zu punkten:

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
quelle
1
Es kann nützlich sein, wenn der Scoring-Code bestätigt, dass der Rückgabewert der Hash-Funktion eine Ganzzahl im zulässigen Bereich ist.
Kasperd
4

Python, 6390, 6376, 6359

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

Kann als geringfügige Änderung der Antwort von Martin Büttner angesehen werden .

Nur ASCII
quelle
3
@ mbomb007 Das stimmt nicht. Wenn Ihre Funktion immer 4 ausgibt, wird immer noch im Bereich ausgegeben [0, 2**24-1]. Das einzige, was nicht erlaubt ist, ist die Ausgabe einer Nummer, die nicht in diesem Bereich liegt, zB -1oder 2**24.
Orlp
3

Python, 9310


Ja, nicht das Beste, aber zumindest ist es etwas. Wie wir in Krypto sagen, schreiben Sie niemals Ihre eigene Hash-Funktion .

Dies ist ebenfalls genau 140 Byte lang.

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))
Herr Public
quelle
2

Matlab, 30828 8620 6848

Es bildet den Hash, indem es jeder ASCII-Zeichen- / Positionskombination eine Primzahl zuweist und für jedes Wortmodul die größte Primzahl berechnet, die kleiner als 2 ^ 24 ist. Beachten Sie, dass ich zu Testzwecken den Aufruf von primes außerhalb direkt vor der while-Schleife in den Tester verschoben und an die Hash-Funktion übergeben habe, da er die Geschwindigkeit um den Faktor 1000 erhöht hat, diese Version jedoch funktioniert und in sich geschlossen ist. Bei Wörtern, die länger als 40 Zeichen sind, kann es zu einem Absturz kommen.

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üfer:

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 Seher
quelle
Wenn Sie in Ihrem Programm Speicherplatz sparen möchten, müssen Sie Ihr Zeichen nicht doubleexplizit in ein konvertieren . Auch könnte man numeleher als gebrauchen length. Nicht sicher, was Sie mit all den zusätzlichen Bytes machen würden!
Suever
1

Ruby, 9309 Kollisionen, 107 Bytes

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 

Kein guter Anwärter, aber ich wollte eine andere Idee als andere Einträge untersuchen.

Weisen Sie die ersten n Primzahlen den ersten n Positionen der Zeichenfolge zu, summieren Sie dann alle Primzahlen [i] ** (ASCII-Code der Zeichenfolge [i]) und dann mod 2 ** 24-1.

jose_castro_arnaud
quelle
1

Java 8, 7054 6467

Dies wurde von der eingebauten Funktion java.lang.String.hashCode inspiriert (aber nicht kopiert).

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

Um zu punkten:

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
quelle
@muddyfish könntest du dir die aktuelle Version ansehen? Ich denke, ich habe 3-Wege-Kollisionen verursacht und erhalte immer noch das gleiche Ergebnis.
Bewusstsein
Dies berücksichtigt keine Drei-Wege-Kollisionen. Wenn Sie ersetzen hashesmit Map<Integer, Integer> hashes = new HashMap<>()und dann die Anzahl der Wörter für jeden Hash zählen, können Sie richtig für sie berücksichtigen.
Peter Taylor
Deine Wertung sieht immer noch falsch aus. Ich denke, um eine korrekte Punktzahl zu berechnen, muss man numHashes + numCollisions ausgeben. (Ich vermute, Sie
nähern sich
Ändern Sie die gradigen Teile dazu: pastebin.com/nLeg4qut
TheNumberOne
ja, die Einstufung wurde
korrigiert
1

Python, 6995 6862 6732

Nur eine einfache RSA-Funktion. Ziemlich lahm, schlägt aber einige Antworten.

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)
Blau
quelle
1

C ++: 7112 6694 6483 6479 6412 6339 Kollisionen, 90 Bytes

Ich habe einen naiven genetischen Algorithmus für mein Koeffizientenarray implementiert. Ich werde diesen Code aktualisieren, da er bessere findet. :)

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

Testfunktion:

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;
}
flauschige
quelle
1

C #, 6251 6335

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

Die Konstanten 533 und 733, 889 und 155 geben die beste Punktzahl von allen, die ich bisher gesucht habe.

bmm6o
quelle
1

tcl

88 Bytes, 6448/3233 Kollisionen

Ich sehe, dass die Leute entweder die Anzahl der kollidierenden Wörter oder die Anzahl der Wörter in nicht leeren Eimern gezählt haben. Ich gebe beide Zählungen an - die erste entspricht der Problemspezifikation, und die zweite ist das, worüber mehr Plakate berichtet haben.

# 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
quelle
2
Wo sehen Sie Antworten mit der falschen Methode zur Berechnung der Punktzahl? Es hat eine Menge gegeben, aber sie wurden alle vor Jahren korrigiert oder gelöscht. Ich sehe noch vier Antworten mit einer Punktzahl von weniger als 6000, da diese vier Antworten für so niedrige Punktzahlen optimiert wurden.
Kasperd
1
Soweit ich das beurteilen kann, ist Ihr Code proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... richtig?
Erik der Outgolfer
@EriktheOutgolfer: Ja, es ist
Sergiol
1
I second @kasperd: Kannst du angeben, welche Antworten die Kollisionen nicht gemäß Fragenspezifikation berücksichtigen? Hast du wirklich versucht, sie laufen zu lassen?
Sergiol
1

Python 3, 89 Bytes, 6534 Hash-Kollisionen

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

Alle großen magischen Zahlen, die Sie hier sehen, sind Fudge-Konstanten.

Magenta
quelle
1

JavaScript, 121 Byte, 3268 3250 3244 6354 (3185) Kollisionen

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}

Die Parameter (13, 7809064, 380886, 2, 266324) werden durch Ausprobieren ermittelt.

Ich denke immer noch optimierbar, und es gibt immer noch Raum für das Hinzufügen zusätzlicher Parameter, die für die weitere Optimierung arbeiten ...

Nachprüfung

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 - Der 3. Parameter wurde von 380713 in 380560 geändert.

3250> 3244 - Der 3. Parameter wurde von 380560 in 380886 geändert.

3244> 6354 - Der zweite Parameter wurde von 7809143 in 7809064 geändert, und ich habe festgestellt, dass ich die falsche Berechnungsmethode verwendet habe

Shieru Asakoto
quelle
1

Hier einige ähnliche Konstrukte, die durchaus "seedbar" sind und eine inkrementelle Parameteroptimierung ermöglichen. Verdammt, es ist schwierig, unter 6 km zu kommen! Unter der Annahme, dass die Punktzahl den Mittelwert von 6829 und den Standardwert von 118 hat, berechnete ich auch die Wahrscheinlichkeit, zufällig so niedrige Punktzahlen zu erhalten.

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 (etwas anderes)

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

Dies war meine ursprüngliche Ad-hoc-Hash-Funktion. Sie verfügt über vier einstellbare Parameter.

NikoNyrh
quelle
Der Trick zu einer niedrigen Punktzahl ist eine String-Konstante, bei der jedes Zeichen unabhängig optimiert werden kann, ohne die Optimierung zu beeinträchtigen, die Sie für die anderen Zeichen vorgenommen haben.
Kasperd
Ja, ich habe zuerst versucht, nur für kürzere Zeichenfolgen zu optimieren, da das Anhängen weiterer Zeichen an die "Entropie" -Zeichenfolge diese nicht beeinflusst (sobald der Multiplikator von rfestgelegt ist). Trotzdem ist mein Suchalgorithmus im Wesentlichen brachial und ich bin nicht sicher, ob die anfängliche Wahl des Multiplikators von rBedeutung ist oder nicht.
NikoNyrh
Vielleicht bringt nur das Multiplizieren von ASCII-Werten nicht genügend Entropie ins Spiel. Viele gut bewertete Algorithmen scheinen die Form zu haben f(n) % (8^8 - g(n)).
NikoNyrh
Es gibt eine Antwort, die erklärt, wie es so niedrig wie 3677 wurde. Diejenigen, die noch niedrigere Punkte erzielen, haben wenig Erklärung.
Kasperd
0

Ruby, 6473 Kollisionen, 129 Bytes

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

Die Variable @p ist mit allen Primzahlen unter 999 gefüllt.

Dies konvertiert ASCII-Werte in Primzahlen und nimmt ihrem Produktmodul eine große Primzahl. Der Fudge-Faktor von 179 befasst sich mit der Tatsache, dass der ursprüngliche Algorithmus zum Auffinden von Anagrammen verwendet wurde, bei denen alle Wörter, die Umordnungen derselben Buchstaben sind, denselben Hash erhalten. Durch Hinzufügen des Faktors in der Schleife werden Anagramme mit unterschiedlichen Codes versehen.

Ich könnte die ** 0.5 (sqrt test for prime) auf Kosten einer schlechteren Leistung entfernen, um den Code zu verkürzen. Ich könnte sogar veranlassen, dass der Primzahlfinder in der Schleife ausgeführt wird, um neun weitere Zeichen zu entfernen, wobei 115 Bytes übrig bleiben.

Zum Testen wird folgendermaßen versucht, den besten Wert für den Fudge-Faktor im Bereich von 1 bis 300 zu finden. Dabei wird davon ausgegangen, dass sich die Wortdatei im Verzeichnis / tmp befindet:

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
quelle
1
Die Partitur sieht verdächtig aus. Sind Sie sicher, dass Sie alle kollidierenden Wörter zählen? Bei mehreren vorherigen Antworten wurde fälschlicherweise nur ein Wort für jeden kollidierenden Hashwert gezählt.
Kasperd
Du könntest Recht haben. Ich muss überlegen, wie ich gezählt habe, und prüfen, ob es mit Ihrer Definition übereinstimmt. Ich zähle, wie viele Wörter es gibt und subtrahiere, wie viele eindeutige Hashcodes generiert wurden. Wenn die Wörter A und B den gleichen Hashcode erhalten, ist das eine Kollision oder zwei? Ich zähle es als eins.
Paul Chernoch
1
Die Bewertungsfunktion habe ich nicht definiert. Ich habe es gerade aus der Beispielantwort kopiert, die von demselben Benutzer gepostet wurde, der die Herausforderung gepostet hat. Die meisten Antworten haben Punktzahlen zwischen 6273 und 6848. Es gab mehrere Antworten, die denselben Fehler in der Punktzahlberechnung machten, was dazu führte, dass eine Punktzahl berechnet wurde, die ungefähr halb so hoch war wie sie hätte sein sollen. (Genau die Hälfte der korrekten Punktzahl, wenn es keine Fälle von drei kollidierenden Wörtern gibt.)
Kasperd
1
Ja, ich habe den gleichen Fehler gemacht. Ich werde meine Antwort später ändern. Ich muss einen Bus nehmen.
Paul Chernoch
Die Wertung wurde korrigiert.
Paul Chernoch
0

tcl

# 91 Bytes, 6508 Kollisionen

91 Bytes, 6502 Kollisionen

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

Der Computer führt immer noch eine Suche durch, um festzustellen, ob ein Wert vorliegt, der weniger Kollisionen verursacht als die 147 875-Basis, bei der es sich immer noch um den Rekorder handelt.

Sergiol
quelle