Neste desafio de código, você escreverá uma função de hash em 140 bytes 1 ou menos do código-fonte. A função hash deve receber uma sequência ASCII como entrada e retornar um número inteiro não assinado de 24 bits ([0, 2 24 -1]) como saída.
Sua função de hash será avaliada para cada palavra neste grande dicionário de inglês britânico 2 . Sua pontuação é a quantidade de palavras que compartilham um valor de hash com outra palavra (uma colisão).
A pontuação mais baixa ganha, empates quebrados pelo primeiro pôster.
Caso de teste
Antes de enviar, teste seu script de pontuação na seguinte entrada:
duplicate
duplicate
duplicate
duplicate
Se der uma pontuação diferente de 4, é de buggy.
Regras de esclarecimento:
- Sua função hash deve ser executada em uma única sequência, não em uma matriz inteira. Além disso, sua função hash pode não fazer nenhuma outra E / S além da sequência de entrada e do número inteiro de saída.
- Funções de hash embutidas ou funcionalidade semelhante (por exemplo, criptografia para embaralhar bytes) não são permitidas.
- Sua função de hash deve ser determinística.
- Ao contrário da maioria dos outros concursos, é permitido otimizar especificamente a entrada de pontuação.
1 Estou ciente de que o Twitter limita caracteres em vez de bytes, mas por simplicidade, usaremos bytes como limite para esse desafio.
2 Modificado a partir do wbritish-enorme do Debian , removendo quaisquer palavras não-ASCII.
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's
? O que...?D=340275
palavras eR=2^24
hash, um hash aleatório temD^2/(2*R) = 3450
pares esperados de colisão, alguns dos quais se sobrepõem. Há umaD^3/(6*R^2) = 23
tripla esperada de colisão e um número insignificante de colisões maiores, o que significa que essas triplas provavelmente são desarticuladas. Isso fornece as6829
palavras esperadas que compartilham um valor de hash, ~70
em triplos e o restante em pares. O desvio padrão é estimado em118
, portanto, obter<6200
um hash aleatório é aproximadamente um evento 5 sigma.Respostas:
Tudo bem, eu vou aprender um idioma de golfe.
CJam, 140 bytes, 3314 palavras em colisão
Define um bloco (função anônima). Para testar, você pode adicionar
qN%%N*N
a lista de palavras separada por nova linha no stdin e escrever uma lista separada por nova linha de hashes no stdout. Código Python equivalente:Pitão, 140 bytes,
35353396 palavras em colisãoDefine uma função chamada
y
. Para testar, você pode adicionarjmyd.z
a lista de palavras separada por nova linha no stdin e escrever uma lista separada por nova linha de hashes no stdout. Código Python equivalente:Limites teóricos
Quão bem podemos esperar fazer? Aqui está um gráfico de x, o número de palavras em colisão, vs. y, a entropia em bytes necessária para obter no máximo x palavras em colisão. Por exemplo, o ponto (2835, 140) nos diz que uma função aleatória obtém no máximo 2835 palavras colididas com probabilidade 1/256 ** 140, por isso é extremamente improvável que possamos fazer muito melhor do que isso com 140 bytes de código.
fonte
Python,
53334991Acredito que este seja o primeiro candidato a pontuar significativamente melhor do que um oráculo aleatório.
fonte
def H(s):n=int(s.encode('hex'),16);return n%...
economiza 5 bytes, no caso de você pode usá-los de alguma forma ...2**24 == 8**8
,.Python 2, 140 bytes, 4266 palavras em colisão
Eu realmente não queria começar com a coisa de bytes não imprimíveis, dada a sua tweetabilidade pouco clara, mas bem, eu não a iniciei. :-P
Python 2, 140 bytes imprimíveis,
466244714362 palavras colidindoInspirado na forma da solução de Kasperd, obviamente - mas com a adição importante de uma transformação afim no espaço do módulo e parâmetros totalmente diferentes.
fonte
n%(8**8-ord('…'[n%70]))
sem outras alterações de parâmetro, eu consegui chegar ao 4995, então parece que seu novo otimizador alcançou o meu. Agora isso fica mais interessante!CJam,
4125393737913677Essa abordagem divide domínio e codomain em 110 conjuntos disjuntos e define uma função de hash ligeiramente diferente para cada par.
Pontuação / Verificação
A seguinte porta para Python pode ser usada com o snippet de pontuação oficial:
fonte
h
naquele porto Python correspondem a um builtin CJam?b
(conversão básica).Python,
64466372Esta solução alcança uma contagem de colisões mais baixa do que todas as entradas anteriores e precisa apenas de 44 dos 140 bytes permitidos para o código:
fonte
%(2**24-1)
, então eu acho que pode ser bom para pedir esclarecimentos[0, 2**24-1]
que palavras no idioma inglês, seria matematicamente impossível criar um hash onde todos os valores desse intervalo eram possíveis.CJam, 6273
XOR cada caractere com 49 , reduza a sequência resultante via x, y ↦ 245x + y , e use o resíduo módulo 16.777.213 (o maior prime de 24 bits).
Pontuação
fonte
JavaScript (ES6), 6389
A função hash (105 bytes):
A função de pontuação (NodeJS) (170 bytes):
Chame como
node hash.js dictionary.txt
, ondehash.js
está o script,dictionary.txt
é o arquivo de texto do dicionário (sem a nova linha final) eF
é definido como a função de hash.Obrigado Neil por remover 9 bytes da função hash!
fonte
((...)>>>0)%(1<<24)
você provavelmente pode usar(...)<<8>>>8
.i
.Mathematica, 6473
O próximo passo ... em vez de somar os códigos de caracteres, nós os tratamos como os dígitos de um número base-151, antes de levá-los ao módulo 2 24 .
Aqui está um script curto para determinar o número de colisões:
Acabei de tentar todas as bases sistematicamente a partir
1
de então, e até agora a base 151 produziu o menor número de colisões. Vou tentar um pouco mais para diminuir ainda mais a pontuação, mas o teste é um pouco lento.fonte
Javascript (ES5), 6765
Esse é o CRC24 reduzido para 140 bytes. Poderia jogar mais, mas queria obter minha resposta em :)
Validador em node.js:
fonte
Python, 340053
Uma pontuação terrível de um algoritmo terrível, essa resposta existe mais para fornecer um pequeno script Python que exibe pontuação.
Pontuar:
fonte
Python,
639063766359Pode ser considerada uma modificação trivial na resposta de Martin Büttner .
fonte
[0, 2**24-1]
. A única coisa que não é permitida é a saída de qualquer número que não esteja dentro desse intervalo, por exemplo,-1
ou2**24
.Python, 9310
Sim, não é o melhor, mas pelo menos é alguma coisa. Como dizemos em criptografia, nunca escreva sua própria função de hash .
Isso tem exatamente 140 bytes de comprimento também.
fonte
Matlab,
3082886206848Ele cria o hash atribuindo um número primo a cada combinação de caracteres / posição ascii e calculando seu produto para cada módulo de palavra, o maior primo menor que 2 ^ 24. Observe que, para o teste, movi a chamada para primos do lado de fora para o testador diretamente antes do loop while e a passei para a função hash, porque a acelerou em um fator de 1000, mas essa versão funciona e é independente. Pode falhar com palavras com mais de 40 caracteres.
Testador:
fonte
double
explicitamente. Além disso, você poderia usarnumel
ao invés delength
. Não tenho certeza do que você faria com todos esses bytes extras!Ruby, 9309 colisões, 107 bytes
Não é um bom candidato, mas queria explorar uma ideia diferente de outras entradas.
Atribua os primeiros n primos às primeiras n posições da string, depois some todos os primos [i] ** (código ascii da string [i]) e mod 2 ** 24-1.
fonte
Java 8,
70546467Isso é inspirado (mas não copiado) pela função interna java.lang.String.hashCode; portanto, sinta-se livre para desabilitar de acordo com a regra nº 2.
Pontuar:
fonte
hashes
porMap<Integer, Integer> hashes = new HashMap<>()
e contar o número de palavras para cada hash, poderá contabilizá-las corretamente.Python,
699568626732Apenas uma função RSA simples. Bastante coxo, mas supera algumas respostas.
fonte
C ++:
711266946483647964126339 colisões, 90 bytesEu implementei um algoritmo genético ingênuo para minha matriz de coeficientes. Vou atualizar esse código, pois ele encontra os melhores. :)
Função de teste:
fonte
C #, 6251
6335As constantes 533 e 733
889 e 155dão a melhor pontuação de todas as que pesquisei até agora.fonte
tcl
88 bytes, colisões 6448/3233
Vejo que as pessoas estão contando o número de palavras em colisão ou o número de palavras colocadas em baldes não vazios. Dou as duas contagens - a primeira é de acordo com a especificação do problema e a segunda é o que mais pôsteres estão relatando.
fonte
proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}
... certo?Python 3, 89 bytes, 6534 colisões de hash
Todos os grandes números mágicos que você vê aqui são constantes de falsificação.
fonte
Colisões JavaScript, 121 bytes,
3268325032446354 (3185)Os parâmetros (13, 7809064, 380886, 2, 266324) são por tentativa e erro.
Ainda otimizável, eu acho, e ainda há espaço para adicionar parâmetros extras, trabalhando para uma otimização adicional ...
Verificação
3268> 3250 - Alterou o terceiro parâmetro de 380713 para 380560.
3250> 3244 - Alterou o terceiro parâmetro de 380560 para 380886.
3244> 6354 - Alterou o segundo parâmetro de 7809143 para 7809064 e descobriu que usei o método de cálculo errado; P
fonte
Aqui estão algumas construções semelhantes, que são bastante "semeadoras" e possibilitam a otimização incremental de parâmetros. Porra, é difícil ficar abaixo de 6k! Supondo que a pontuação tenha a média de 6829 e o padrão de 118, também calculei a probabilidade de obter pontuações tão baixas aleatoriamente.
Clojure A, 6019, Pr = 1: 299.5e9
Clojure B, 6021, Pr = 1: 266.0e9
Clojure C, 6148, Pr = 1: 254.0e6
Clojure, 6431, Pr = 1: 2.69e3 (algo diferente)
Esta foi a minha função hash ad-hoc original, possui quatro parâmetros ajustáveis.
fonte
r
é corrigido). Mas meu algoritmo de busca ainda é essencialmente força bruta, e não tenho certeza se a escolha inicial do multiplicador der
é importante ou não.f(n) % (8^8 - g(n))
.Ruby, 6473 colisões, 129 bytes
A variável @p é preenchida com todos os números primos abaixo de 999.
Isso converte valores ASCII em números primos e leva seu módulo de produto um primo grande. O fator de correção de 179 lida com o fato de que o algoritmo original foi usado para encontrar anagramas, onde todas as palavras que são rearranjos das mesmas letras obtêm o mesmo hash. Ao adicionar o fator no loop, faz com que os anagramas tenham códigos distintos.
Eu poderia remover o ** 0,5 (teste do sqrt para prime) às custas do pior desempenho para encurtar o código. Eu poderia até executar o localizador de números primos no loop para remover mais nove caracteres, deixando 115 bytes.
Para testar, o seguinte tenta encontrar o melhor valor para o fator de correção no intervalo de 1 a 300. Supõe-se que o arquivo de palavras esteja no diretório / tmp:
fonte
tcl
# 91 bytes, 6508 colisões91 bytes, 6502 colisões
O computador ainda está realizando uma pesquisa para avaliar se existe um valor que causa menos colisões do que a base
147875, que ainda é a gravadora.fonte