Ce code de golf a été inspiré par le récent article du Daily WTF Vous ne pouvez pas gérer le vrai! , qui comporte une comparaison de chaînes écrite comme suit:

String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())

Imaginez le problème que l’équipe de Steve aurait eu si la String.hashCodeméthode de Java avait été implémentée de cette manière "YES".hashCode() == "NO".hashCode(). Donc, le défi que je propose ici est:

Ecrivez, dans le moins de caractères possible, une fonction de hachage (je l'appellerai h) avec un paramètre de chaîne et une valeur de retour entière, telle qu'elle h("YES")soit égale à h("NO").

Bien sûr, il serait trivial de le faire avec une fonction comme def h(s): return 0, ce qui crée une collision de hachage pour chaque chaîne. Pour rendre ce défi plus intéressant, vous devez respecter la règle supplémentaire suivante:

Parmi les autres 18 277 chaînes possibles composé de trois lettres ou moins ASCII (majuscules ^[A-Z]{0,3}$), il doit y avoir aucune collision de hachage.

Clarification (soulignée par Heiko Oberdiek): La chaîne de saisie peut contenir des caractères autres que A-Z, et votre code doit être en mesure de hacher des chaînes arbitraires. (Vous pouvez toutefois supposer que l'entrée est une chaîne de caractères plutôt qu'un pointeur null ou un objet d'un autre type de données.) Toutefois, peu importe la valeur de retour pour les chaînes qui ne correspondent pas ^[A-Z]{0,3}$, tant que c'est un entier.

De plus, pour brouiller l’intention de cette fonction:

Votre code ne doit contenir aucune des lettres "Y", "E", "S", "N" ou "O" (en majuscules ou minuscules) dans les littéraux de caractères ou de chaînes.

Bien sûr, cette restriction ne concerne pas les mots clés du langage, donc else, return, etc. sont très bien.

GolfScript: 19 caractères (24 caractères pour la fonction nommée)

26base.2107=59934*+

Ceci est le corps de la fonction. L'attribuer à une fonction nommée hnécessite cinq caractères supplémentaires:

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

(Le dernier point-virgule peut être omis, si cela ne vous dérange pas de laisser une copie du code sur la pile.)

Le cœur de la fonction de hachage est le 26basecalcul de la somme (26 ^{n - k} · a _k ; k = 1 .. n ), où n est le nombre de caractères de l'entrée et a _k le code ASCII de la k- ème caractère d'entrée. Pour les entrées composées de lettres ASCII majuscules, il s'agit d'une fonction de hachage sans collision. Le reste du code compare le résultat à 2107 (le code de hachage de NO) et, s’ils sont égaux, ajoute 59934 pour obtenir 2701 + 59934 = 62041, le code de hachage de YES.

Par exemple, voir cette démonstration en ligne avec des cas de test.

Python 32 bits 2.x (19)

hash(w*9)%537105043

RSA utilise un module semi-prime, ce qui le sécurise. En utiliser un avec mon algorithme de hachage devrait certainement le rendre encore meilleur! ¹

Ceci est une fonction mathématique pure, fonctionne pour toutes les chaînes (enfer, fonctionne pour tout objet Python hachage), et ne contient pas de conditional ou de casse spéciale! Python 32 bits peut généralement être appelé comme python-32sur la plupart des systèmes sur lesquels les deux sont installés ² .

J'ai testé cela et il renvoie 18 278 valeurs différentes pour les 18 279 chaînes de 3 lettres ou moins en majuscules. L'attribution de cette fonction à une fonction nécessite 11 octets supplémentaires:

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

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

Python 2.x 64 bits (19)

hash(w*2)%105706823

Même affaire que ci-dessus.

Pour arriver à ces chiffres, un peu de calcul modulaire a été utilisé. Je cherchais une fonction fet un module ntels que hash(f('YES')) % n == hash(f('NO')) % n. Ceci équivaut à un test qui ndivise d = hash(f('YES')) - hash(f('NO')), c'est-à-dire qu'il suffit de vérifier les facteurs de dpour des valeurs appropriées de n.

L’idéal nest d’environ 20000 ** 2 pour réduire les risques de collision avec un paradoxe d’anniversaire. Trouver une solution adaptée ns'avère être un peu un essai et une erreur, en jouant avec tous les facteurs de d(il n'y a généralement pas beaucoup) et des choix différents pour la fonction f. Notez cependant que les essais et les erreurs ne sont nécessaires que parce que je voulais faire le nplus petit possible (pour le golf). Si ce n'était pas une exigence, je pourrais simplement choisir dmon module, qui est généralement suffisamment grand.

Notez également que vous ne pouvez pas tirer cette astuce en utilisant simplement f(s) = s(la fonction identité) car le caractère le plus à droite de la chaîne a essentiellement une relation linéaire (en fait une XORrelation) avec le hachage final (les autres caractères contribuent de manière beaucoup plus non linéaire). ). La répétition de la chaîne garantit donc que les différences entre les chaînes sont amplifiées pour éliminer l’effet de ne changer que le caractère le plus à droite.

¹ Ceci est un non-sens évident.
^{2 Le} hachage de chaîne Python dépend de la version majeure (2 vs 3) et du nombre de bits (32 bits contre 64 bits). Cela ne dépend pas de la plate-forme AFAIK.

Perl, 53 49 40 octets

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

Tester:

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

Les valeurs de hachage pour YESet NOsont identiques et il y a 18279 chaînes ^[A-Z]{0,3}$libres de collision, à l'exception de la seule collision pour YESet NO.

Ungolfed:

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

Ancienne version, 49 octets

Comme le nouvel algorithme est légèrement différent, je conserve l'ancienne version.

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

Tester:

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

Ungolfed:

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".
}

Modifications:

• Utiliser "\0"comme octet de remplissage enregistre 4 octets par rapport à $".

Python: 63

Une solution incroyablement boiteuse:

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

Cela fonctionne en interprétant les chaînes alphanumériques comme des nombres en base 36 et en renvoyant 0 pour tout le reste. Il existe un cas particulier explicite pour vérifier une valeur de retour de 852 (NO) et 44596 (YES) à la place.

Pure Bash, 29 octets (corps de la fonction)

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

Ceci traite simplement la chaîne d'entrée comme un nombre de base 36 et la convertit en décimale, puis traite le NOcas spécial .

Sortie:

$ h A
dix
$ h B
11
$ h CAT
15941
$ h NO
44596
$ h OUI
44596
$ h ZZZ
46655
$

Ruby, 51 octets

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

code de test:

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
}

sortie:

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

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

Javascript ( ES6 ) 54 octets

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

Déroulé:

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

Narrative - pour f(s) = BigInteger(s.getBytes()):

• f("YES") xor f("NO") = 5835548
• Alors f("YES") xor 5835548 = f("NO")
• Alors f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)j'ai raison?

CJam, 15 octets

q42b_*81991617%

Fonctionne comme la solution GolfScript ci-dessous. Essayez-le en ligne.

GolfScript, 17 octets

42base.*81991617%

Cette approche s'appuie sur les réponses de Nneonneo et Ilmari Karonen .

Comment ça fonctionne

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.

Choisir un algorithme

Nous commençons par {b base}:h, c'est-à-dire que la chaîne d'entrée est considérée comme un nombre base-b. Tant que b > 25, hest inyective.

Nous obtenons une collision pour les chaînes "OUI" et "NON" si nous modifions hde la manière suivante:, {x base n}:hoù nest un diviseur de "YES" h "NO" h -.

Malheureusement, cela signifie que nous aurons également une collision pour, par exemple, YETet NP. Pour éviter cela, nous devons modifier le nombre base-b de manière non linéaire avant de prendre le module.

Dans GolfScript, le moyen le plus simple d’atteindre cet objectif consiste à multiplier le nombre base-b par lui-même (c’est-à-dire de le mettre au carré). hest maintenant {base b .* n %}:h.

Tout ce qui reste à faire est de trouver des valeurs appropriées pour bet n. Nous pouvons accomplir cela par la force brute:

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

Les valeurs les plus courtes possibles pour b nsont:

37 92176978
42 81991617

Essai

$ 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 caractères (corps de la fonction 33 caractères)

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

Cas de test:

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

Explication:

Tout d’abord, permettez-moi de vous présenter NaN- "Pas un nombre" - en JavaScript. C'est un numéro:

typeof NaN  // number

Juste comme:

typeof 42   // number

Sa propriété particulière est qu'il ne s'égale jamais . Ma fonction retourne 1si la chaîne est YESou NO, et NaNpour toute autre chaîne.

Donc, cela n'enfreint pas les règles, car il n'y aurait aucune collision de hachage pour aucune autre chaîne;) ( NaN !== NaNmontré ci-dessus dans les cas de test).

Et mon rêve devient réalité: battre Bash, Perl et Ruby en longueur de code!

Code non-golfé:

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

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

Si cette valeur est "WUVT"ou "Tk8=", retournez 1. Sinon retour

+s // parseInt(s, 10)

ce qui serait 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

La fonction de hachage concatène les valeurs ordinales des caractères ASCII. L'instruction print veille à la collision des deux entrées souhaitées.

ECMAScript 6 (30 octets)

J'ai essayé d'éviter les mots-clés d'attribution, de retour et de fonction de variable, et cela semble être un excellent moyen d'éviter tout ce qui est absurde (cela ressemble aussi à de la programmation fonctionnelle, en quelque sorte). Contrairement à d'autres solutions, elle ne dépend pas de btoaou atob, ce qui n'est pas ECMAScript 6, mais HTML5. 0+est nécessaire pour pouvoir analyser des chaînes arbitraires.

a=>parseInt(0+a,36)-852||43744

Java - 45 (ou 62?)

Je ne sais pas comment évaluer équitablement compte tenu de ce qui est nécessaire pour exécuter un programme en Java. Dois-je inclure la définition de la fonction? N'hésitez pas à modifier et à ajuster mon score de manière appropriée. Actuellement, je marque de la même manière que la réponse @OldCurmudgeon. Ajoutez 17 int h(String t){}si nécessaire:

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

Ungolfed avec harnais de test:

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

Et le perdant est ...

Convoyeur, 145 caractères

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

Fondamentalement, ce programme est en quelque sorte basé sur les caractères. Après cela, il vérifie si le hachage est égal à 12999 (le code de hachage de OUI) et si oui, affiche 404 (le hachage de NON), sinon il imprimera simplement le hachage.

Conveyor est un langage que j'ai créé et qui est actuellement en phase bêta, mais un interprète ainsi que quelques exemples et le code source sont disponibles à l' adresse suivante : https://github.com/loovjo/Conveyor.

C # 4.5 (112 octets)

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

Version de travail (?) De la tentative de undergroundmonorail, en C #. Concatte les octets de la chaîne en un entier de 32 bits (ne fonctionne que jusqu'à 4 caractères), puis OR le résultat par rapport au résultat pour "YES" et "NO" respectivement, puis les OR ensemble.

Bien que cela puisse entrer en collision à un moment donné, cela ne devrait pas arriver pour aucun ^ [AZ] {2,3} $ autre que "OUI" et "NON".

Pas de commentaire - 31 (contenu de la fonction: 26)

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

Solution assez simple. ;) Fonctionne pour toutes les chaînes UTF-8.

EXPLICATION: ' est, évidemment, la fonction. Tout d'abord, il vérifie si *(c'est l'entrée) est égal à |,,|+|"#|( |NO|). Si c'est le cas, il retourne |, |+|-%3|( |YES|) - sinon, il retourne simplement *.

C 54

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

Convertissez la chaîne en entier - "NON" et multipliez-la par la même valeur + "NON" - "OUI" pour obtenir 0 pour "NON" et "OUI" et différent de zéro pour toute autre chaîne de la plage spécifiée.

Toutes les valeurs sur la machine Windows 7 s'il y a des problèmes finaux.

Stax , 12 à 11 octets

ì≤ïøZ‼kESa←

Exécuter et déboguer

Traduit l'entrée en base 36, soustrait 852, puis remplace 0 par 43744. C'est l'un des meilleurs solutions de Konrad .

CoffeeScript - 36

Devrait revenir 1pour YESet NO, et atobtout ce que le non- sens brouillé produit pour tout le reste n'est pas une chaîne base64.

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

L'équivalent JavaScript ( pas le code JS du compilateur CS):

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

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

Voici un super boiteux. SO LAME, IL NE FONCTIONNE PAS MÊME

Python 2.7 - 79 octets

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

Nous obtenons d’abord la somme de (la valeur ascii de chaque caractère) * 100 ^ (la position de ce caractère dans la chaîne). Ensuite, nous multiplions (ce résultat - 7978) et (ce résultat - 836989) pour obtenir notre réponse finale. 7978 et 836989 sont les résultats pour "OUI" et "NON" du premier bit, donc pour OUI et NON, nous multiplions par 0.

Cela ne devrait pas avoir de collisions? Je n'ai pas le goût de tester contre 18 000 contre-exemples possibles, mais en cas de collision non intentionnelle, je peux ajouter un autre 0 100et il ne devrait y avoir aucune collision.

Déçu de ne pouvoir utiliser a lambdapour cela, mais comme je ne voulais pas faire le calcul complet deux fois, je devais le sauvegarder dans une variable.

S'il vous plaît ne laissez pas cela gagner. C'est super nul et je ne le mérite pas.