Implementar um hash de comprimento variável

10

Meu amigo e eu temos esse jogo que brincamos com palavras. É um passatempo divertido e envolve "cancelar" letras em uma palavra até que não haja mais nada. Estou realmente cansado de ele ser muito mais rápido do que eu, então é seu trabalho implementá-lo e me deixar finalmente vencê-lo. Obviamente, como eu tenho que tornar o programa o mais fácil possível de ocultar, ele deve ser o menor possível.

Como esse jogo funciona?

O jogo é um algoritmo bastante simples. Reduz uma sequência alfabética até que não possa mais ser reduzida, tornando-a uma espécie de hash. O jogo real que nós humanos fazemos é muito difícil de implementar, mas pode ser simplificado no seguinte algoritmo:

Você começa dobrando o alfabeto ao meio e alinhando as duas peças da seguinte maneira:

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

Então, começando do meio, você atribui os números inteiros positivos à metade superior e o negativo à 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

Então você pega sua string (nós estaremos usando hello world) e ignorando quaisquer caracteres não alfabéticos, traduza-a:

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

Então você soma os valores das letras. Os que alinharam no diagrama anterior (por exemplo, de w, le o) irá cancelar para fora, enquanto os outros vão somar.

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

12 é o número para b, então o hash de hello worldéb

Para uma palavra que anula completamente fora (por exemplo love), você saída "0 caráter": -. Observe que, na entrada, -ainda será desconsiderado. Só importa na saída.

Se a magnitude do número é maior do que 13, então você começa a dobrar-se sobre os a's eo z' s Você basicamente ter como muitos a's ou zde ajuste para o número e tomar tudo o que está à esquerda para a última carta assim:

code golf: 43.

Cabe 3 ae tem 4 sobras:

aaa 4: j
result: aaaj

Dica: Esta parte é, basicamente, divmodexcepto que arredonda para zero, não -infinity(por exemplo, -43 iria tornar-se 3 z's e um e -4que é ppor isso zzzp).

Nota: o traço não vem se os a's z' se encaixam perfeitamente, apenas se for exatamente 0.

Esclarecimentos:

  • O hash é caso em sensível
  • As brechas padrão não são permitidas
  • A E / S pode estar em qualquer formato que não seja muito estranho, stdin, stdout, arg da linha de comando, função etc.
  • Esse é o para que o menor tamanho em bytes seja alcançado.

Exemplos:

hello world  -->  b

love  -->  -

this is an example -->  aak

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

good bye --> ae

root users --> zzs
Maltysen
fonte
3
loveestá vazia ...
Justin

Respostas:

4

CJam, 46 bytes

Experimente online ou tente a suíte de testes online .

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

Explicação

O algoritmo funciona como o esperado: leia a entrada, converta para minúscula, mapeie cada caractere para um valor, some os valores e imprima caracteres e ajuste a soma de acordo até que a soma seja zero. Provavelmente, a otimização mais interessante (embora salve apenas dois bytes) é que, em vez disso, são utilizados mapeamentos de caracteres negados, pois isso evita a troca de argumentos de subtração para corrigir o sinal ao calcular o valor mapeado e evita a troca novamente ao mapear de volta para uma letra devido ao subtração de um valor negado sendo substituível por adição.

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
fonte
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
fonte
Você pode usar em @Jzvez de f}YJzProvavelmente há mais, mas preciso dormir agora. Boa sorte;)
FryAmTheEggman
@FryAmTheEggman Legal, eu não estava ciente da interseção de @!
orlp 25/03
2

Clipe 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
fonte
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,"-",""))}

Esse deve ser o código R mais bruto de todos os tempos. Imaginei que R poderia ser uma escolha decente, pois possui um vetor de todas as letras "a" a "z" como uma variável global interna. Mas o resto é uma bagunça.

Ungolfed + explicação:

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

Isso cria um objeto de função sem nome que aceita uma string como entrada e retorna o valor de hash associado. Para chamá-lo, dê um nome, por exemplo f=function(s){...}.

Exemplos:

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

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

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

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

Experimente online!

Questões? Felizmente, darei qualquer outra explicação. Sugestões? Sugestões são mais que bem-vindas!

Alex A.
fonte
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]]

Execução de teste:

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

Como funciona: lé uma tabela de pesquisa de letras para o valor correspondente. Pesquise todos os caracteres da sequência de entrada e descarte aqueles não encontrados. Soma a lista resultante. Dependendo da soma pimpressa, -ou talvez primeiro, se aou se, zfinalmente, (inversa) procurar a letra l.

nimi
fonte
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}
modelo
fonte
+1, definitivamente melhor do que minha resposta em R. Bom trabalho!
Alex A.