Collision de hachage: “NON” signifie “OUI”

63

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.

dan04
la source
4
Le fait que nous puissions toujours utiliser les valeurs numériques ASCII de YESNOpour vérifier cette exception spécifique n'aide en rien .
Joe Z.
1
En lisant l'article, on ne se souvient plus du comique "pour des raisons": threewordphrase.com/pardonme.gif
Antonio Ragagnin

Réponses:

7

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.

Ilmari Karonen
la source
Comment avez-vous testé cela? Je viens de trouver un tas de collisions . Exemple: h('DXP') == h('KK') == 65884.
nneonneo
(Équivalent en Python de ce que vous avez écrit, à des fins de test lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983) :
nneonneo
@nneonneo: Évidemment, pas assez bien. Je pensais avoir généré l'ensemble complet d'entrées de trois lettres ou moins, les avoir toutes hachées et vérifier que l'ensemble des hachages avait un élément de moins que l'ensemble des entrées. Clairement, mon harnais de test avait un bug quelque part. :-( Je reviens à la version originale de 19 caractères jusqu'à ce que / si je ne puisse pas corriger la version la plus courte.
Ilmari Karonen
54

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

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

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.


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

Nneonneo
la source
Vous avez mon vote. : D
cjfaure
Malheureusement, cela ne fonctionne pas sur les versions récentes de Python en raison de la nouvelle fonctionnalité de randomisation de hachage.
dan04
@ dan04: Bizarre, je pensais avoir précisé que c'était uniquement pour Python 2.x. Je l'ai édité à nouveau.
nneonneo
Puis-je savoir comment vous avez trouvé ces nombres magiques? Je vois hash('YES'*9)a 34876679comme un facteur, tout hash('NO'*9)a 34876679+537105043un facteur. Mais comment avez-vous su que 537105043c'était un bon module? c'est-à-dire qu'il n'a pas fait d'autres collisions?
Antonio Ragagnin
@AntonioRagagnin: Ajouté cela à la réponse.
nneonneo
38

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 à $".
Heiko Oberdiek
la source
Où allons- 5457241et 20047venir? Comment calculez-vous ces chiffres? Merci d'avance.
AL le
@ n.1: YESdans l'hex est 594553. 0x594553 = 5850451. NOen hexadécimal est 4e4f. 0x4e4f = 20047.
nneonneo le
7

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.

dan04
la source
3
À moins que je ne comprenne mal: c'est du code golf, vous êtes autorisé à supposer que la saisie est exacte. Vous pouvez laisser tomber try:et la troisième ligne entière. Vous pouvez également économiser quelques bits en plaçant chaque ligne logique sur la même ligne, séparées par des points-virgules ( def h(s):r=int(s,36);return(r,44596)[r==852])
undergroundmonorail
1
@undergroundmonorail: le paramètre de chaîne pour la fonction de hachage n'est pas limité dans la question. Pour une certaine classe de chaînes (jusqu'à trois lettres majuscules), il existe une restriction concernant les valeurs de retour de la fonction de hachage. Cependant, peu importe ce qui est retourné pour les autres chaînes, si la valeur de retour est un entier.
Heiko Oberdiek
3
J'aime bien l'indexation booléenne de votre tableau
kratenko
6

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
$
Trauma numérique
la source
5

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)
onionpsie
la source
5

Javascript ( ES6 ) 54 octets

f=s=>[x.charCodeAt()for(x of s)].join('')^7879||897296
f('YES'); // 897296
f('NO'); // 897296
f('MAYBE'); // -824036582
Nderscore
la source
5

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?
Vieux curcuma
la source
Ne pouvez-vous pas aligner le BigInteger?
Mafu
@mafutrct - OUI !!! Je vous remercie.
OldCurmudgeon
5

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}:hnest 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
Dennis
la source
3

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.

Gaurang Tandon
la source
2
NaN peut être un nombre, mais ce n'est pas un "entier" dans le sens du mot.
Paŭlo Ebermann
2
@ PaŭloEbermann A partir de wiki , "Un entier est un nombre écrit sans composant fractionnaire". La question ne dit pas explicitement que l'entier doit être ^\d+$. Et JS traite NaNcomme un nombre. Vous pouvez le multiplier par un nombre, ajouter, diviser, soustraire comme avec des nombres. C'est une propriété spéciale de JavaScript. Il n'y a pas de mal à l'utiliser. C'est ce qu'on appelle la flexion des règles ;)
Gaurang Tandon
1
Je pourrais utiliser Object.is()et prétendre que c'est toujours une collision…
user2428118
1
@ user2428118 Merci d'avoir porté Object.is à ma connaissance. Je ne l'ai jamais su Mais j'aimerais que vous remarquiez que l'OP utilise l'opérateur d'égalité ( ==) à des fins de comparaison, ce qui garantira qu'aucune collision de hachage ne se produit pour une chaîne autre que "YES" ou "NO".
Gaurang Tandon
2
Ignorant le fait que la revendication NaNne compte pas comme collision semble pas cher, cette solution a des collisions avec des chaînes NApar NPet à YEQtraversYET
nderscore
2

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.

Kaya
la source
2

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
Konrad Borowski
la source
1
Agréable! Je ne savais pas qu'ils avaient ajouté d'autres bases pour l'analyse. Vous pouvez cependant couper beaucoup d'octets. :)a=>parseInt(0+a,36)-852||43744
nderscore
@nderscore: Merci pour la suggestion. Cela a beaucoup amélioré mon script.
Konrad Borowski
2

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;
  }
}
durron597
la source
1

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.

Loovjo
la source
0

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

Garandy
la source
Votre fonction de hachage aura beaucoup plus de collisions. Votre "fonction de hachage" ignore essentiellement de nombreux bits de la concaténation. Toutes les paires de chaînes qui ne diffèrent que par ces bits auront le même code de hachage.
Paŭlo Ebermann le
0

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

cjfaure
la source
2
Je n'ai jamais travaillé avec No Comment. Pourriez-vous expliquer votre solution, comme c'est souvent le cas avec des réponses opaques Golfscript, J ou APL?
Kaya
@Kaya Oh, oui, désolé, je vais éditer le post.
cjfaure
1
Aucune excuse nécessaire, j'étais simplement curieux de savoir comment cela fonctionnait.
Kaya
0

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.

Alchimiste
la source
-1

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 _;
}
Tony Ellis
la source
3
"La fonction doit avoir une valeur de retour entière" - je suppose que la vôtre renvoie le _lorsque l'entrée n'est pas "OUI" ou "NON".
Gaurang Tandon
-1

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.

métro monorail
la source
Ne répond pas à l'exigence "pas d'autres collisions": il n'y a que 18012 hachages uniques parmi les 18277 chaînes qui ne devraient pas avoir de collisions.
dan04
@dan Damn, donnez-moi une seconde
undergroundmonorail
1
@dan je ne peux pas le faire fonctionner. Peut-être qu'il y a quelque chose de fondamentalement faux avec l'algorithme. Je ne veux pas le supprimer parce que quelqu'un d'autre pourrait savoir ce qui ne va pas, mais je mettrai une note
undergroundmonorail
Cela fonctionne pour moi, h = lambda s: (hash (s) +997192582) * (hash (s) -480644903)
Lucas
de même que définir une fonction de hachage similaire à la votre mais avec 99 ** i * int (c, 36)
Lucas