Implementar un hash de longitud variable

10

Mi amigo y yo tenemos este juego que jugamos con palabras. Es un pasatiempo divertido e implica "cancelar" letras en una palabra hasta que no quede nada. Estoy realmente cansado de que sea mucho más rápido que yo, así que es tu trabajo implementarlo y dejarme finalmente vencerlo. Obviamente, dado que tengo que hacer que el programa sea lo más fácil de ocultar posible, tiene que ser lo más pequeño posible.

¿Cómo funciona este juego?

El juego es un algoritmo bastante simple. Reduce una cadena alfabética hasta que no se puede reducir más, lo que la convierte en una especie de hash. El juego real que hacemos los humanos es muy difícil de implementar, pero se puede simplificar en el siguiente algoritmo:

Empiezas doblando el alfabeto por la mitad y alineando las dos piezas de la siguiente manera:

a b c d e f g h i j k l m
z y x w v u t s r p q o n

Luego, comenzando desde el medio, asigna los enteros positivos a la mitad superior y los negativos a la parte inferior:

a  b  c  d  e f g h i j k l m
13 12 11 10 9 8 7 6 5 4 3 2 1

z   y   x   w   v  u  t  s  r  p  q  o  n
-13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1

Luego toma su cadena (la usaremos hello world) e ignora los caracteres no alfabéticos, traduzca:

h e l l  o w   o  r  l d
6 9 2 2 -2 -10 -2 -5 2 10

Luego sumas los valores de las letras. Los que se alinearon en el diagrama anterior (por ejemplo, dy w, ly o) se cancelan, mientras que los otros van a sumar.

sum(6 9 2 2 -2 -10 -2 -5 2 10 )=12

12 es el número para b, entonces el hash de hello worldesb

Para una palabra que anula por completo (por ejemplo love), que la salida "0 carácter": -. Tenga en cuenta que en la entrada, -todavía se tendrá en cuenta. Solo importa en la salida.

Si la magnitud del número es mayor que 13, entonces comienzas a duplicar los a's y los z' s. Básicamente, tomas tantos a's z' o 'caben en el número y tomas lo que queda en la última letra de la siguiente manera:

code golf: 43.

Se adapta a 3 ay le quedan 4:

aaa 4: j
result: aaaj

Sugerencia: Esta parte es básicamente divmodexcepto que se redondea hacia cero, no -infinity(por ejemplo, -43 se convertiría en 3 z's y' a ' -4que es pasí zzzp).

Nota: el guión no viene si el a's o el z' s encajan perfectamente, solo si es exactamente 0.

Aclaraciones:

  • El hash es caso en sensible
  • Las lagunas estándar no están permitidas
  • I / O puede estar en cualquier formato que no sea demasiado extravagante, stdin, stdout, arg de línea de comandos, función, etc.
  • Este es el por lo que gana el tamaño más corto en bytes .

Ejemplos:

hello world  -->  b

love  -->  -

this is an example -->  aak

hello *&*(&(*&%& world  -->  b

good bye --> ae

root users --> zzs
Maltysen
fuente
3
loveestá vacío ...
Justin

Respuestas:

4

CJam, 46 bytes

Pruébelo en línea o pruebe el conjunto de pruebas en línea .

lel{'n-_W>+_zE<*}%:+{_De<C~e>___0>-'n+'-?o-}h;

Explicación

El algoritmo funciona de la forma esperada: lea la entrada, convierta a minúsculas, asigne cada carácter a un valor, sume los valores e imprima caracteres y ajuste la suma en consecuencia hasta que la suma sea cero. Probablemente la optimización más interesante (aunque solo ahorra dos bytes) es que en su lugar se utilizan asignaciones de caracteres negadas, ya que esto evita intercambiar argumentos de sustracción para corregir el signo al calcular el valor asignado y evita el intercambio nuevamente al asignar a una letra debido a la resta de un valor negado que es reemplazable por adición.

lel             "Read a line of input and convert all letters to lowercase.";
{               "Map each character:";
  'n-_W>+         "Map each character to its negated value by subtracting 'n'
                   and incrementing if the result is nonnegative.";
  _zE<*           "If the value is out of the letter range, use 0 instead.";
}%
:+              "Compute the sum of the mapped character values.";
{               "Do...";
  _De<C~e>        "Compute the sum clamped to the letter range.";
  __              "If the clamped sum is nonzero, ...";
  _0>-'n+         "... then produce the clamped sum mapped back to a letter by
                     decrementing if it is positive and adding 'n', ...";
  '-              "... else produce '-'.";
  ?
  o               "Output the character produced above.";
  -               "Subtract the clamped sum out of the sum.";
}h              "... while the sum is nonzero.";
;               "Clean up.";
Runer112
fuente
4

Pyth, 79 78 77 65 61 58

J+\-GK+0fTr13_14=ZsX@JzJKMe,pk*G/H13%H13@JxK?g\aZ>Z0_g\z_Z
orlp
fuente
Puedes usar en @Jzlugar de f}YJzHay probablemente más, pero debo dormir ahora. Buena suerte;)
FryAmTheEggman
@FryAmTheEggman ¡Genial, no estaba al tanto de la intersección de @!
orlp
2

Clip 10 , 87

Fr+`m[y?cAyg#Ay-v,-RRZ]0]}m.U`[Fx?x?<x0,:-/xR'z*m'm%xR!!%xR],:/xR'a*m'n%xR!!%xR]]'-[R13
Ypnypn
fuente
1

R, 258 bytes

function(s){a=13;r=data.frame;z=strsplit(gsub("[^a-z]","",tolower(s)),"")[[1]];d=r(l=rev(letters),h=c(-1*a:1,1:a));m=merge(r(l=z),d);n=sum(m$h);q=abs(n);v=rep(ifelse(n>0,"a","z"),q%/%a);paste0(paste(v,collapse=""),d$l[d$h==sign(n)*q%%a],ifelse(n==0,"-",""))}

Este tiene que ser el código R más grosero de la historia. Pensé que R podría ser una opción decente ya que tiene un vector de todas las letras "a" a "z" como una variable global incorporada. Pero resulta que el resto es un desastre.

Ungolfed + explicación:

function(s) {
    a <- 13              # Store the value associated with a
    r <- data.frame      # Store the `data.frame` function

    # Split the input into a vector, ignoring case and non-letters
    z <- strsplit(gsub("[^a-z]", "", tolower(s)), "")[[1]]

    # Create a data frame where the first column is the letters
    # z through a and the second is the associated scores
    d <- data.frame(l=reverse(letters), h=c(-1*a:1, 1:a))

    # Merge the split vector with the data frame of scores
    m <- merge(data.frame(l=z), d)

    # Get the total score for the input
    n <- sum(m$h)
    q <- abs(n)

    # Pad the output with a or z as necessary
    v <- rep(ifelse(n > 0, "a", "z"), q %/% a)

    # Collapse the vector of a's or z's into a string
    out1 <- paste(v, collapse="")

    # Look up the letter associated with remainder
    out2 <- d$l[d$h == sign(n)*q%%a]

    # If n = 0, we still want a dash
    out3 <- ifelse(n == 0, "-", "")

    # Return the concatenation of all pieces of the output
    paste0(out1, out2, out3)
}

Esto crea un objeto de función sin nombre que acepta una cadena como entrada y devuelve el valor hash asociado. Para llamarlo, asígnele un nombre, por ejemplo f=function(s){...}.

Ejemplos:

> f("this is an example")
[1] "aak"

> f("root users")
[1] "zzs"

> f("love")
[1] "-"

> f("People like grapes.")
[1] "aaag"

Pruébalo en línea!

Preguntas? Con mucho gusto le daré más explicaciones. Sugerencias? ¡Las sugerencias son más que bienvenidas!

Alex A.
fuente
1

Haskell, 171 bytes

import Data.Char
m=13
l=zip['a'..'z'][-i|i<-[-m..m],i/=0]
p 0="-"
p n|n>m='a':p(n-m)|n<(-m)='z':p(n+m)|1<2=[c|(c,i)<-l,i==n]
f n=p$sum[y|Just y<-[lookup(toLower x)l|x<-n]]

Prueba de funcionamiento:

> map f ["hello world", "love", "this is an example", "hello *&*(&(*&%& world", "good bye", "root users"]
["b","-","aak","b","ae","zzs"]

Cómo funciona: les una tabla de búsqueda de letras al valor correspondiente. Busque todos los caracteres de la cadena de entrada y descarte los que no se encuentran. Suma la lista resultante. Dependiendo de la suma pimpresa -o tal vez primero algunos as y zs y finalmente (inversa) busca la letra l.

nimi
fuente
1

R - 200

function(s){l=letters
N=setNames
x=strsplit(tolower(s),'')[[1]]
n=(13:-13)[-14]
v=sum(N(n,l)[x[x%in%l]])
o=''
while(v){d=min(max(v,-13),13)
o=paste0(o,N(l,n)[as.character(d)])
v=v-d}
if(o=='')o='-'
o}
flodel
fuente
+1, definitivamente mejor que mi respuesta R. ¡Buen trabajo!
Alex A.