Este Code Golf foi inspirado no recente artigo do Daily WTF, You Can't Handle the True! , que apresenta uma comparação de cadeias escrita como:
String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())
Imagine o problema que teria causado à equipe de Steve se o String.hashCode
método de Java fosse implementado de uma maneira assim "YES".hashCode() == "NO".hashCode()
. Então, o desafio que proponho aqui é:
Escreva, no menor número de caracteres possível, uma função hash (eu a chamarei
h
) com um parâmetro de string e um valor de retorno inteiro, de modo queh("YES")
seja igual ah("NO")
.
Obviamente, isso seria trivial para uma função como def h(s): return 0
, que faz uma colisão de hash para cada string. Para tornar esse desafio mais interessante, você deve respeitar a seguinte regra adicional:
Dos outros 18 277 cordas possíveis constituídos por três ou menos letras maiúsculas (ASCII
^[A-Z]{0,3}$
), deve haver nenhum colisões de hash.
Esclarecimento (apontado por Heiko Oberdiek): A sequência de entrada pode conter caracteres diferentes de A-Z
, e seu código deve ser capaz de hash seqüências arbitrárias. (No entanto, você pode supor que a entrada seja uma cadeia de caracteres em vez de um ponteiro nulo ou um objeto de outro tipo de dados.) No entanto, não importa qual é o valor de retorno para cadeias que não coincidem ^[A-Z]{0,3}$
, desde que é um número inteiro.
Além disso, ofuscar a intenção desta função:
Seu código não deve incluir nenhuma das letras 'Y', 'E', 'S', 'N' ou 'O' (em maiúsculas ou minúsculas) entre caracteres literais ou caracteres.
Claro, esta restrição não se aplica ao idioma palavras-chave, assim else
, return
, etc. são muito bem.
YESNO
para verificar esta exceção específica.Respostas:
GolfScript: 19 caracteres (24 caracteres para a função nomeada)
Este é o corpo da função. A atribuição a uma função nomeada
h
leva mais cinco caracteres:(O ponto e vírgula final pode ser omitido, se você não se importa de deixar uma cópia do código na pilha.)
O núcleo da função hash é
26base
, que calcula a soma (26 n - k · um k ; k = 1 .. n ), onde n é o número de caracteres na entrada e um k indica o código ASCII do k -ésimo caractere de entrada. Para entradas que consistem em letras ASCII maiúsculas, essa é uma função de hash sem colisão. O restante do código compara o resultado a 2107 (o código hash deNO
) e, se forem iguais, adiciona 59934 para gerar 2701 + 59934 = 62041, o código hash deYES
.Por exemplo, saída, consulte esta demonstração online com casos de teste.
fonte
h('DXP') == h('KK') == 65884
.lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983
)Python de 32 bits 2.x (19)
O RSA usa um módulo semiprime, e isso o torna seguro; portanto, usar um com meu algoritmo de hash certamente deve torná-lo ainda melhor! 1 1
Esta é uma função matemática pura, funciona para todas as strings (inferno, funciona para qualquer objeto Python hashável) e não contém condicionais ou letras especiais! 32-bit Python geralmente pode ser chamado como
python-32
na maioria dos sistemas que têm ambos instalados 2 .Eu testei isso e ele retorna 18.278 valores diferentes para as 18.279 seqüências de letras maiúsculas ou menos de 3 letras. Atribuir isso a uma função leva mais 11 bytes:
e
h('YES') == h('NO') == 188338253
.Python de 64 bits 2.x (19)
O mesmo acordo que acima.
Para chegar a esses números, um pouco de matemática modular foi usada. Eu estava procurando por uma função
f
e um módulon
como essehash(f('YES')) % n == hash(f('NO')) % n
. Isso é equivalente ao teste quen
divided = hash(f('YES')) - hash(f('NO'))
, ou seja, só precisamos verificar os fatores ded
para valores adequados den
.O ideal
n
é cerca de 20.000 ** 2 para reduzir a chance de uma colisão de paradoxos no aniversário. Encontrar um adequadon
acaba por ser um pouco de tentativa e erro, jogando com todos os fatoresd
(geralmente não existem muitos) e diferentes opções para a funçãof
. Observe, porém, que a tentativa e o erro são necessários apenas porque eu queria fazern
o menor possível (para jogar golfe). Se isso não fosse um requisito, eu poderia apenas escolherd
como meu módulo, que geralmente é suficientemente grande.Observe também que você não pode fazer esse truque usando just
f(s) = s
(a função de identidade) porque o caractere mais à direita da string tem essencialmente um relacionamento linear (na verdade, umXOR
relacionamento) com o hash final (os outros caracteres contribuem de uma maneira muito mais não-linear) ) A repetição da sequência garante, portanto, que as diferenças entre as sequências sejam amplificadas para eliminar o efeito de alterar apenas o caractere mais à direita.1 Isso é um absurdo de patentes.
O hash de cadeia de caracteres 2 Python depende da versão principal (2 vs 3) e bitness (32 bits vs 64 bits). Não depende da plataforma AFAIK.
fonte
hash('YES'*9)
tem34876679
como fator, enquanto quehash('NO'*9)
tem34876679+537105043
como fator. Mas como você sabia que esse537105043
era um bom módulo? ou seja, não fez outras colisões?Perl,
534940 bytesTeste:
Os valores de hash para
YES
eNO
são os mesmos e existem 18279 seqüências de caracteres^[A-Z]{0,3}$
, livres de colisão, exceto a única colisão paraYES
eNO
.Ungolfed:
Versão antiga, 49 bytes
Como o novo algoritmo é um pouco diferente, eu mantenho a versão antiga.
Teste:
Ungolfed:
Editar% s:
"\0"
como byte de preenchimento economiza 4 bytes em comparação com$"
.fonte
5457241
e20047
vem? Como você calcula esses números? Desde já, obrigado.YES
em hexadecimal é594553
. 0x594553 = 5850451.NO
em hexadecimal é4e4f
. 0x4e4f = 20047.Python: 63
Uma solução incrivelmente ruim:
Ele funciona interpretando seqüências alfanuméricas como números da base 36 e retornando 0 para todo o resto. Há um caso especial explícito para verificar o valor de retorno 852 (NO) e retornar 44596 (YES).
fonte
try:
e toda a terceira linha. Você também pode salvar algumas mordidas por ter cada linha lógica na mesma linha real, separados por ponto e vírgula (def h(s):r=int(s,36);return(r,44596)[r==852]
)Pure Bash, 29 bytes (corpo da função)
Isso simplesmente trata a sequência de entrada como um número base 36 e converte em decimal, depois lida com o
NO
caso especial .Resultado:
fonte
Ruby, 51 bytes
código de teste:
resultado :
fonte
Javascript ( ES6 ) 54 bytes
fonte
Java -
9477Desenrolado:
Narrativa - para
f(s) = BigInteger(s.getBytes())
:f("YES") xor f("NO") = 5835548
f("YES") xor 5835548 = f("NO")
f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)
estou certo?fonte
CJam, 15 bytes
Funciona como a solução GolfScript abaixo. Experimente online.
GolfScript, 17 bytes
Essa abordagem baseia-se nas respostas de nneonneo e Ilmari Karonen .
Como funciona
Escolhendo um algoritmo
Começamos com
{b base}:h
, ou seja, a string de entrada é considerada um número base-b. Contanto queb > 25
,h
seja inativo.Temos uma colisão para as seqüências de caracteres "SIM" e "NÃO" se modificarmos
h
da seguinte maneira :,{x base n}:h
onden
é um divisor de"YES" h "NO" h -
.Infelizmente, isso significa que também teremos uma colisão para, por exemplo,
YET
eNP
. Para evitar isso, precisamos modificar o número da base-b de maneira não linear antes de executar o módulo.A maneira mais curta de conseguir isso no GolfScript é multiplicar o número da base-b por si mesmo (por exemplo, ao quadrado).
h
é agora{base b .* n %}:h
.Tudo o que resta fazer é encontrar valores adequados para
b
en
. Podemos fazer isso com força bruta:Os menores valores possíveis para
b n
são:Testando
fonte
JavaScript (ES6) - 38 caracteres (corpo da função de 33 caracteres)
Casos de teste:
Explicação:
Antes de mais, deixe-me apresentar-lhe
NaN
- "Não é um número" - em JavaScript. É um número:Assim como:
Sua propriedade especial é que nunca se iguala . Minha função retorna
1
se a string forYES
orNO
eNaN
para qualquer outra string.Portanto, isso não quebra as regras, porque não haveria colisão de hash para nenhuma outra string;) (
NaN !== NaN
mostrada acima nos casos de teste).E meu sonho se torna realidade: derrotar Bash, Perl e Ruby no tamanho do código!
Código Ungolfed:
Se esse valor for
"WUVT"
ou"Tk8="
, retorne1
. Senão, voltaro que seria
NaN
.fonte
^\d+$
. E JS trataNaN
como um número. Você pode multiplicá-lo por um número, adicionar, dividir, subtrair da mesma forma que com números. É uma propriedade especial do JavaScript. Não há mal nenhum em usá-lo. Isso é o que chamamos de flexão de regras ;)Object.is()
e alegar que ainda é uma colisão…==
) para comparação, o que garantirá que não ocorra colisão de hash para nenhuma sequência além de "SIM" ou "NÃO".NaN
não conta como colisão parece barato, esta solução tem colisões com cordasNA
atravésNP
eYEQ
atravésYET
Python 92
A função de hash concatena os valores ordinais dos caracteres ASCII, a instrução print garante que as duas entradas desejadas colidem.
fonte
ECMAScript 6 (30 bytes)
Tentei evitar a atribuição de variáveis, o retorno e a palavra-chave da função, e isso parece uma ótima maneira de evitar toda essa bobagem (também parece uma programação funcional, de certa forma). Diferente de outras soluções, ele não depende de
btoa
ouatob
, que não é o ECMAScript 6, mas o HTML5.0+
é necessário, para que ele possa analisar seqüências de caracteres arbitrárias.fonte
a=>parseInt(0+a,36)-852||43744
Java - 45 (ou 62?)
Não tenho ideia de como pontuar corretamente, considerando o que é necessário para executar um programa em Java, preciso incluir a definição de função? Sinta-se livre para editar e ajustar minha pontuação adequadamente. Atualmente, estou marcando da mesma maneira que a resposta @OldCurmudgeon. Adicione 17
int h(String t){}
se for necessário:Ungolfed with harness test:
fonte
E o mais frouxo é ...
Transportador, 145 caracteres
Basicamente, este programa faz algum tipo de base 26 nos caracteres. Depois disso, verifica se o hash é igual a 12999 (o código de hash de YES) e, se sim, imprime 404 (o código de hash de NO); caso contrário, ele apenas imprime o código de hash.
Transportador é uma linguagem feita por mim que está atualmente em estágios beta, mas um intérprete, juntamente com alguns exemplos e código fonte, pode ser encontrado aqui: https://github.com/loovjo/Conveyor
fonte
C # 4.5 (112 bytes)
Versão de trabalho (?) Da tentativa de undergroundmonorail, em C #. Concatiza os bytes na cadeia de caracteres em um número inteiro de 32 bits (funciona apenas até 4 caracteres), em seguida, ORs resulta no resultado de "YES" e "NO", respectivamente, e os ORs juntos.
Embora possa colidir em algum momento, isso não deve acontecer para nenhum ^ [AZ] {2,3} $ que não seja "SIM" e "NÃO".
fonte
Sem comentário - 31 (conteúdo da função: 26)
Solução bastante simples. ;) Funciona para toda e qualquer sequência UTF-8.
EXPLICAÇÃO:
'
é, obviamente, a função. Primeiro, ele verifica se*
(sua entrada) é igual a|,,|+|"#|
(|NO|
). Se for, ele retorna|, |+|-%3|
(|YES|
) - caso contrário, apenas retorna*
.fonte
C 54
Converta a string em número inteiro - "NO" e multiplique pelo mesmo valor + "NO" - "YES" para obter 0 para "NO" e "YES" e diferente de zero para qualquer outra string no intervalo especificado.
Todos os valores na máquina Windows 7, se houver alguma preocupação com endian.
fonte
Stax ,
1211 bytesExecute e depure
Traduz a entrada como base-36, subtrai 852 e substitui 0 por 43744. É uma porta da excelente solução da Konrad .
fonte
CoffeeScript - 36
Deve retornar
1
paraYES
eNO
, e qualquer absurdo ilusório queatob
produz para todo o resto que não seja uma string base64.O equivalente a JavaScript ( não o código JS do compilador CS):
fonte
_
quando a entrada não for "SIM" ou "NÃO".Aqui está um super manco. TÃO MANGA QUE NÃO FUNCIONA
Python 2.7 - 79 bytesPrimeiro, obtemos a soma de (valor ascii de cada caractere) * 100 ^ (posição desse caractere na string). Em seguida, multiplicamos (esse resultado - 7978) e (esse resultado - 836989) para obter nossa resposta final. 7978 e 836989 são os resultados para "SIM" e "NÃO" do primeiro bit, portanto, para SIM e NÃO, multiplicamos por 0.
Isso não deve ter colisões? Não me apetece testar contra 18000 possíveis contra-exemplos, mas, se houve uma colisão não intencional, posso dar outro 0 nisso
100
e, na verdade , não deve haver colisão.Desapontado por não poder usar um
lambda
para isso, mas não queria fazer todo o cálculo duas vezes, então tive que salvá-lo em uma variável.Por favor, não deixe isso vencer. É super manco e eu não mereço.
fonte