Choque de hash: "NO" significa "SÍ"

63

Este Code Golf se inspiró en el reciente artículo del Daily WTF ¡ No puedes manejar lo verdadero! , que presenta una comparación de cadenas escrita como:

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

Imagine el problema que le habría causado al equipo de Steve si el String.hashCodemétodo de Java se implementara de una manera tal "YES".hashCode() == "NO".hashCode(). Entonces, el desafío que propongo aquí es:

Escriba, en la menor cantidad de caracteres posible, una función hash (la llamaré h) con un parámetro de cadena y un valor de retorno entero, tal que h("YES")sea ​​igual a h("NO").

Por supuesto, esto sería trivial con una función como def h(s): return 0, que genera una colisión hash para cada cadena. Para hacer este desafío más interesante, debe cumplir con la siguiente regla adicional:

De los otros 18 277 cuerdas posibles que constan de tres o menos letras mayúsculas (ASCII ^[A-Z]{0,3}$), tiene que haber no hay colisiones hash.

Aclaración (señalado por Heiko Oberdiek): la cadena de entrada puede contener caracteres que no sean A-Z, y su código debe ser capaz de codificar cadenas arbitrarias. (Sin embargo, puede suponer que la entrada es una cadena de caracteres en lugar de un puntero nulo o un objeto de algún otro tipo de datos). Sin embargo, no importa cuál sea el valor de retorno para las cadenas que no coinciden ^[A-Z]{0,3}$, siempre que Es un número entero.

Además, para ofuscar la intención de esta función:

Su código no debe incluir ninguna de las letras 'Y', 'E', 'S', 'N' u 'O' (en mayúsculas o minúsculas) dentro de caracteres o literales de cadena.

Por supuesto, esta restricción no se aplica a las palabras reservadas, por lo que else, return, etc están muy bien.

dan04
fuente
44
De alguna manera no ayuda que podamos usar los valores numéricos ASCII de YESNOpara verificar esta excepción específica.
Joe Z.
1
Al leer el artículo no se puede recordar el cómic "por razones": threewordphrase.com/pardonme.gif
Antonio Ragagnin

Respuestas:

7

GolfScript: 19 caracteres (24 caracteres para funciones con nombre)

26base.2107=59934*+

Este es el cuerpo de la función. Asignarlo a una función con nombre hrequiere cinco caracteres más:

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

(Se puede omitir el punto y coma final, si no le importa dejar una copia del código en la pila).

El núcleo de la función hash es 26base, que calcula la suma (26 n - k · a k ; k = 1 .. n ), donde n es el número de caracteres en la entrada y a k denota el código ASCII de la k -ésima Carácter de entrada. Para entradas que consisten en letras mayúsculas ASCII, esta es una función hash sin colisiones. El resto del código compara el resultado con 2107 (el código hash de NO) y, si son iguales, agrega 59934 para obtener 2701 + 59934 = 62041, el código hash de YES.

Por ejemplo, salida, vea esta demostración en línea con casos de prueba.

Ilmari Karonen
fuente
¿Cómo probaste esto? Acabo de encontrar un montón de colisiones . Ejemplo: h('DXP') == h('KK') == 65884.
nneonneo
(Python equivalente de lo que ha escrito, para mis propósitos de prueba: lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983)
nneonneo
@nneonneo: Obviamente, no lo suficientemente bien. Yo pensaba que me genera el conjunto completo de tres letras-o-menos insumos, HASHED todos ellos y comprobar que el conjunto de hashes tenía un elemento menor que el conjunto de entradas. Claramente, mi arnés de prueba tenía un error en alguna parte. :-( Volveré a la versión original de 19 caracteres hasta / a menos que pueda arreglar la versión más corta.
Ilmari Karonen
54

Python 2.x de 32 bits (19)

hash(w*9)%537105043

RSA usa un módulo de semiprime, y eso lo hace seguro, por lo que usar uno con mi algoritmo hash seguramente lo hará aún mejor. 1

Esta es una función matemática pura, funciona para todas las cadenas (demonios, funciona para cualquier objeto Python hashable), ¡y no contiene ningún tipo de condición o carcasa especial! Python de 32 bits normalmente se puede llamar como python-32en la mayoría de los sistemas que tienen ambos instalados 2 .

He probado esto y devuelve 18,278 valores diferentes para las 18,279 cadenas mayúsculas de 3 letras o menos. Asignar esto a una función requiere 11 bytes más:

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

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

Python 2.x de 64 bits (19)

hash(w*2)%105706823

El mismo trato que el anterior.


Para llegar a estos números, se utilizó un poco de matemática modular. Estaba buscando una función fy un módulo ntal que hash(f('YES')) % n == hash(f('NO')) % n. Esto es equivalente a una prueba que ndivide d = hash(f('YES')) - hash(f('NO')), es decir, solo tenemos que verificar los factores de dvalores adecuados de n.

Lo ideal nes cerca de 20000 ** 2 para reducir la posibilidad de una colisión de paradoja de cumpleaños. Encontrar un adecuado nresulta ser un poco de prueba y error, jugar con todos los factores de d(generalmente no hay muchos) y diferentes opciones para la función f. Tenga en cuenta que la prueba y el error solo son necesarios porque quería hacer lo nmás pequeño posible (para jugar al golf). Si eso no fuera un requisito, podría elegir dcomo mi módulo, que generalmente es lo suficientemente grande.

Tenga en cuenta también que no puede realizar este truco usando solo f(s) = s(la función de identidad) porque el carácter más a la derecha de la cadena tiene esencialmente una relación lineal (en realidad una XORrelación) con el hash final (los otros caracteres contribuyen de una manera mucho más no lineal) ) Por lo tanto, la repetición de la cadena garantiza que las diferencias entre las cadenas se amplifiquen para eliminar el efecto de cambiar solo el carácter más a la derecha.


1 Esto es una tontería patente.
2 El hash de cadenas de Python depende de la versión principal (2 frente a 3) y el bitness (32 bits frente a 64 bits). No depende de la plataforma AFAIK.

nneonneo
fuente
Tienes mi voto. : D
cjfaure
Desafortunadamente, esto no funciona en versiones recientes de Python debido a la nueva función de aleatorización de hash.
dan04
@ dan04: Extraño, pensé que había especificado que esto era solo para Python 2.x. Lo he editado de nuevo.
nneonneo
¿Puedo saber cómo encontraste estos números mágicos? Veo hash('YES'*9)tiene 34876679como factor, mientras que hash('NO'*9)tiene 34876679+537105043como factor. Pero, ¿cómo sabías que 537105043era un buen módulo? es decir, no hizo otras colisiones?
Antonio Ragagnin
@AntonioRagagnin: Agregó eso a la respuesta.
nneonneo
38

Perl, 53 49 40 bytes

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

Prueba:

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

Los valores hash para YESy NOson los mismos y hay 18279 cadenas ^[A-Z]{0,3}$, que están libres de colisión, excepto la única colisión para YESy NO.

Sin golf:

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

Versión anterior, 49 bytes.

Como el nuevo algoritmo es ligeramente diferente, mantengo la versión anterior.

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

Prueba:

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

Sin golf:

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

Ediciones:

  • El uso "\0"como byte de relleno ahorra 4 bytes en comparación con $".
Heiko Oberdiek
fuente
¿De dónde 5457241y de dónde 20047vienes? ¿Cómo se calculan estos números? Gracias por adelantado.
AL
@ n.1: YESen hexadecimal es 594553. 0x594553 = 5850451. NOen hexadecimal es 4e4f. 0x4e4f = 20047.
nneonneo
7

Python: 63

Una solución increíblemente pobre:

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

Funciona interpretando cadenas alfanuméricas como números de base 36 y devolviendo 0 para todo lo demás. Hay un caso especial explícito para verificar un valor de retorno de 852 (NO), y devolver 44596 (YES) en su lugar.

dan04
fuente
3
A menos que malinterprete: es un código de golf, puede asumir que la entrada es precisa. Puedes deshacerte try:y toda la tercera línea. También puede guardar algunas picaduras al tener todas las líneas lógicas en la misma línea real, separadas por punto y coma ( def h(s):r=int(s,36);return(r,44596)[r==852])
undergroundmonorail
1
@undergroundmonorail: el parámetro de cadena para la función hash no está restringido en la pregunta. Para una determinada clase de cadenas (hasta tres letras mayúsculas) existe una restricción con respecto a los valores de retorno de la función hash. Sin embargo, no importa qué se devuelve para otras cadenas, si el valor devuelto es un entero.
Heiko Oberdiek
3
Me gusta la indexación booleana de su matriz allí
kratenko
6

Pure Bash, 29 bytes (cuerpo de la función)

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

Esto simplemente trata la cadena de entrada como un número base 36 y la convierte a decimal, luego trata el NOcaso especial .

Salida:

$ h A
10
$ h B
11
$ h CAT
15941
$ h NO
44596
$ h SÍ
44596
$ h ZZZ
46655
PS
Trauma digital
fuente
5

Ruby, 51 bytes

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

código de prueba:

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
}

salida:

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

tested 17576
duplicate : "YES" = "NO" (0)
onionpsia
fuente
5

Javascript ( ES6 ) 54 bytes

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

Java - 94 77

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

Desenrollado:

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

Narrativa - para f(s) = BigInteger(s.getBytes()):

  • f("YES") xor f("NO") = 5835548
  • Entonces f("YES") xor 5835548 = f("NO")
  • ¿Entonces f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)tengo razón?
OldCurmudgeon
fuente
¿No puedes alinear el BigInteger?
mafu
@mafutrct - ¡SÍ! Gracias.
OldCurmudgeon
5

CJam, 15 bytes

q42b_*81991617%

Funciona como la solución de GolfScript a continuación. Pruébalo en línea.


GolfScript, 17 bytes

42base.*81991617%

Este enfoque se basa en las respuestas de nneonneo e Ilmari Karonen .

Cómo funciona

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.

Elegir un algoritmo

Comenzamos con {b base}:h, es decir, la cadena de entrada se considera un número base-b. Mientras b > 25, hes inyectiva.

Obtenemos una colisión para las cadenas "SÍ" y "NO" si modificamos hde la siguiente manera:, {x base n}:hdonde nes un divisor de "YES" h "NO" h -.

Desafortunadamente, esto significa que también tendremos una colisión por, por ejemplo, YETy NP. Para evitar esto, tenemos que modificar el número de base-b de una manera no lineal antes de tomar el módulo.

La forma más corta de lograr esto en GolfScript es multiplicar el número base-b consigo mismo (es decir, cuadrarlo). hes ahora {base b .* n %}:h.

Todo lo que queda por hacer es encontrar valores adecuados para by n. Podemos lograr esto por la fuerza bruta:

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

Los valores más cortos posibles para b nson:

37 92176978
42 81991617

Pruebas

$ 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
fuente
3

JavaScript (ES6) - 38 caracteres (33 cuerpo de función char)

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

Casos de prueba:

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

Explicación:

Antes que nada, permíteme presentarte NaN- "No es un número" - en JavaScript. Es un numero:

typeof NaN  // number

Al igual que:

typeof 42   // number

Su propiedad especial es que nunca se iguala a sí mismo . Mi función devuelve 1si la cadena es YESo NO, y NaNpara cualquier otra cadena.

Por lo tanto, esto no rompe las reglas, porque no habría colisión de hash para ninguna otra cadena;) (se NaN !== NaNmuestra arriba en casos de prueba).

Y mi sueño se hace realidad: ¡derrotar a Bash, Perl y Ruby en la longitud del código!

Código sin golf:

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

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

Si ese valor es "WUVT"o "Tk8=", regrese 1. De lo contrario, regrese

+s // parseInt(s, 10)

cual seria NaN.

Gaurang Tandon
fuente
2
NaN puede ser un número, pero no es un "entero" en ningún sentido de la palabra.
Paŭlo Ebermann
2
@ PaŭloEbermann De wiki , "Un número entero es un número que se escribe sin un componente fraccional". La pregunta no dice explícitamente que el entero tiene que ser ^\d+$. Y JS trata NaNcomo un número. Puedes multiplicarlo por un número, sumar, dividir, restar como con los números. Es una propiedad especial de JavaScript. No hay daño en usarlo. Eso es lo que llamamos flexión de reglas ;)
Gaurang Tandon
1
Podría usar Object.is()y afirmar que sigue siendo una colisión ...
user2428118
1
@ user2428118 Gracias por traer Object.is a mi conocimiento. Nunca lo supe Pero me gustaría que tenga en cuenta que el OP utiliza el operador de igualdad ( ==) para la comparación, lo que garantizará que no ocurra una colisión hash para ninguna cadena aparte de "SÍ" o "NO".
Gaurang Tandon
2
Ignorando el hecho de que alegando NaNque no cuenta como colisión parece barato, esta solución tiene colisiones con cuerdas NAa través NPy YEQpor medioYET
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 función hash concatena los valores ordinales de los caracteres ASCII, la declaración de impresión asegura que las dos entradas deseadas colisionen.

Kaya
fuente
2

ECMAScript 6 (30 bytes)

Intenté evitar la asignación de variables, el retorno y la palabra clave de función, y esta parece ser una excelente manera de evitar todas esas tonterías (también se parece a la programación funcional, en cierto modo). A diferencia de otras soluciones, no depende de btoao atob, que no es ECMAScript 6, sino HTML5. 0+es necesario, por lo que podría analizar cadenas arbitrarias.

a=>parseInt(0+a,36)-852||43744
Konrad Borowski
fuente
1
¡Agradable! No sabía que agregaron otras bases para parseInt. Sin embargo, puede cortar muchos bytes. :)a=>parseInt(0+a,36)-852||43744
nderscore
@nderscore: Gracias por la sugerencia. Realmente mejoró mucho mi script.
Konrad Borowski
2

Java - 45 (¿o 62?)

No tengo idea de cómo calificar de manera justa dado lo que uno necesita para ejecutar un programa en Java, ¿debo incluir la definición de la función? Siéntase libre de editar y ajustar mi puntaje adecuadamente. Actualmente estoy anotando de la misma manera que la respuesta @OldCurmudgeon. Agregue 17 para int h(String t){}si es necesario:

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

Sin golfista con arnés de prueba:

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

Y el más flojo es ...

Transportador, 145 caracteres

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

Básicamente este programa hace algún tipo de base 26 en los caracteres. Después de eso, comprueba si el hash es igual a 12999 (El código hash de YES) y si es así imprime 404 (el código hash de NO), de lo contrario, solo imprimirá el código hash.

Conveyor es un lenguaje creado por mí que actualmente se encuentra en etapas beta, pero puede encontrar un intérprete junto con algunos ejemplos y código fuente aquí: https://github.com/loovjo/Conveyor

Loovjo
fuente
0

C # 4.5 (112 bytes)

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

Versión de trabajo (?) Del intento del monorraíl subterráneo, en C #. Concatena los bytes de la cadena en un entero de 32 bits (solo funciona con hasta 4 caracteres), luego OR el resultado contra el resultado de "SÍ" y "NO" respectivamente, luego OR juntos.

Si bien puede colisionar en algún momento, no debería suceder para ningún ^ [AZ] {2,3} $ que no sea "SÍ" y "NO".

Garandy
fuente
Tu función hash tendrá muchas más colisiones. Su "función hash" esencialmente ignora muchos bits en la concatenación. Todos los pares de cadenas que solo difieren en esos bits tendrán el mismo código hash.
Paŭlo Ebermann
0

Sin comentarios - 31 (contenido de la función: 26)

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

Solución bastante simple. ;) Funciona para todas y cada una de las cadenas UTF-8.

EXPLICACIÓN: ' es, obviamente, la función. Primero, verifica si *(es entrada) es igual a |,,|+|"#|( |NO|). Si es así, devuelve |, |+|-%3|( |YES|); de lo contrario, solo devuelve *.

cjfaure
fuente
2
Nunca he trabajado con Sin comentarios, ¿le sería posible explicar su solución como se hace a menudo con respuestas opacas de Golfscript, J o APL?
Kaya
@Kaya Oh, sí, lo siento, editaré la publicación.
cjfaure
1
No me disculpo, solo tenía curiosidad de cómo funcionaba.
Kaya
0

C 54

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

Convierta la cadena a entero - "NO" y multiplíquelo por el mismo valor + "NO" - "SÍ" para obtener 0 para "NO" y "SÍ" y distinto de cero para cualquier otra cadena en el rango especificado.

Todos los valores en la máquina con Windows 7 si hay alguna preocupación endian.

Alquimista
fuente
-1

CoffeeScript - 36

Debería regresar 1para YESy NO, y cualquier tontería confusa que atobproduzca para todo lo demás que no sea una cadena base64.

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

El equivalente de JavaScript ( no el código JS del compilador CS):

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

    if( _ === "`D" || _ === "4" )
        return 1;
    else
        return _;
}
Tony Ellis
fuente
3
"La función debe tener un valor de retorno entero" - Supongo que el suyo devuelve el _cuando la entrada no es "SÍ" o "NO".
Gaurang Tandon
-1

Aquí hay uno súper cojo. TAN LO QUE NO FUNCIONA INCLUSO

Python 2.7 - 79 bytes

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

Primero obtenemos la suma de (valor ascii de cada personaje) * 100 ^ (la posición de ese personaje en la cadena). Luego multiplicamos (ese resultado - 7978) y (ese resultado - 836989) para obtener nuestra respuesta final. 7978 y 836989 son los resultados para "SÍ" y "NO" del primer bit, por lo que para SÍ y NO estamos multiplicando por 0.

Esto no debería tener ninguna colisión? No tengo ganas de probar contra 18000 posibles contraejemplos, pero si hubo una colisión involuntaria, puedo lanzar otro 0 sobre eso 100y realmente no debería haber ninguna colisión.

Decepcionado porque no podía usar un lambdapara esto, pero no quería hacer el cálculo completo dos veces, así que tuve que guardarlo en una variable.

Por favor, no dejes que esto gane. Es súper cojo y no lo merezco.

metro subterráneo
fuente
No cumple con el requisito de "no hay otras colisiones": solo hay 18012 hashes únicos del conjunto de 18277 cadenas que no deberían tener colisiones.
dan04
@dan Maldición, dame un segundo
undergroundmonorail
1
@dan No puedo hacer que funcione. Tal vez hay algo inherentemente mal con el algoritmo. No quiero eliminarlo porque alguien más puede saber lo que está mal, pero pondré una nota
undergroundmonorail
Esto funciona para mí, h = lambda s: (hash (s) +997192582) * (hash (s) -480644903)
Lucas
como definió una función hash similar a la suya pero con 99 ** i * int (c, 36)
Lucas