Considere que você possui uma função de hash que pega cadeias de comprimento e retorna cadeias de comprimento e tem a propriedade agradável de que é resistente a colisões , ou seja, é difícil encontrar duas cadeias diferentes com o mesmo hash .
Agora você deseja criar uma nova função de hash que pega cadeias de comprimento arbitrário e as mapeia para cadeias de comprimento , enquanto ainda é resistente a colisões.
Para sua sorte, já em 1979 foi publicado um método agora conhecido como a construção Merkle – Damgård que alcança exatamente isso.
A tarefa desse desafio será implementar esse algoritmo; portanto, primeiro examinaremos uma descrição formal da construção de Merkle – Damgård, antes de seguir um exemplo passo a passo que deve mostrar que a abordagem é mais simples do que pode aparecer a princípio.
Dado um número inteiro , uma função de hash conforme descrito acima e uma sequência de entrada de comprimento arbitrário, a nova função de hash faz o seguinte:
- Defina , o comprimento de e divida em pedaços de comprimento , preenchendo o último pedaço com zeros à direita, se necessário. Isso produz muitos pedaços rotulados como.
- Adicione um pedaço inicial e final e , em que é uma string que consiste em zeros é em binário, preenchido com zeros à esquerda no comprimento .
- Agora, iterativamente, aplique ao bloco atual anexado ao resultado anterior : , em que . (Esta etapa pode ficar mais clara depois de analisar o exemplo abaixo.)
- A saída de é o resultado final .
A tarefa
Escreva um programa ou função que tenha como entrada um número inteiro positivo , uma função de hash como caixa preta e uma string não vazia e retorne o mesmo resultado que nas mesmas entradas.
Isso é código-golfe , então a resposta mais curta em cada idioma vence.
Exemplo
Digamos , então nossa função hash dada pega cadeias de comprimento 10 e retorna cadeias de comprimento 5.
- Dada a entrada de , obtemos os seguintes blocos: , , e . Observe que precisava ser preenchido com o comprimento 5 com um zero à direita.
- é apenas uma sequência de cinco zeros é cinco em binário ( ), preenchido com dois zeros à esquerda.
- Agora os pedaços são combinados com :
- é a nossa saída.
Vamos dar uma olhada na aparência dessa saída, dependendo de algumas opções 1 para :
- Se , ou seja, apenas retorna cada segundo caractere, obtemos:
Portanto, precisa ser a saída se esse for fornecido como função de caixa preta. - Se simplesmente retornar os 5 primeiros caracteres de sua entrada, a saída de será . Da mesma forma, se retornar os últimos 5 caracteres, a saída será .
- Se multiplicar os códigos de caracteres de sua entrada e retornar os cinco primeiros dígitos desse número, por exemplo, , então .
1 Por simplicidade, os não são realmente resistentes a colisões, embora isso não importe para testar sua submissão.
omgPzzles0
. Exemplo de entrada bem escolhido!Respostas:
Haskell ,
919086 bytesExperimente online!
Explicação
Apenas atribui a stringn vezes) a
"00...0"
('0'
a
A funçãon ), n caracteres de
?
implementa a aplicação recursiva deh
:c
é o hash que obtivemos até agora (comprimentoz
é o restante da string. Sez
estiver vazio, simplesmente retornamosc
, caso contrário, pegamos os primeirosz
(possivelmente preenchendo com zeros dea
), acrescentamosc
e aplicamosh
. Isso fornece o novo hash e, em seguida, chamamos?
recursivamente esse hash e os caracteres restantes dez
.A funçãon .
!
é a que realmente resolve o desafio. É precison
,h
es
(implícita) como entradas. Nós computamosa?s
, e tudo o que precisamos fazer é anexarn
em binário e aplicarh
novamente.mapM(:"1")a!!n
retorna a representação binária defonte
let
em um guarda é mais curto do que usarwhere
: Experimente on-line!mapM(\_->"01")a
pode sermapM(:"1")a
.R ,
159154 bytesExperimente online!
Que nojo! Responder a desafios de string em R nunca é bonito, mas isso é horrível. Esta é uma resposta instrutiva sobre como não escrever código R "normal" ...
Agradecimentos ao nwellnhof por corrigir um erro, a um custo de 0 bytes!
Agradecimentos a J.Doe por trocar o alias do operador para alterar a precedência, bom para -4 bytes.
A explicação abaixo é para a versão anterior do código, mas os princípios permanecem os mesmos.
fonte
0*(n-(?s)%%n)
que não funciona se n divide s uniformemente. Mas0*-((?s)%%-n)
deve funcionar.seq
tem1
comofrom
argumento por padrão.C (gcc) , 251 bytes
Experimente online!
Não é tão limpo quanto a solução do bash e é altamente improvável.
A função está
f
assumindoH
como uma função que substitui sua entrada de string pelo hash da string,n
como na descrição, ex
na string de entrada e no buffer de saída.Descrição:
fonte
Ruby , 78 bytes
Experimente online!
Como funciona:
fonte
Gelatina , 23 bytes
Experimente online!
AceitaH na linha acima, s como argumento à esquerda, e n como argumento correto.
fonte
Bash , 127-ε bytes
Experimente online!
Isso funciona como um programa / função / script / snippet. H deve ser resolvido por um programa ou função que executará o hash. N é o argumento. Chamada de exemplo:
Descrição:
Isso cria uma sequência de
$1
zeros. Isso funciona chamando printf e solicitando que imprima um número inteiro preenchido com uma largura extra de argumento . Esse argumento extra que passamos é$1
o argumento para o programa / função / script que armazena n.Isso apenas copia Z, nossa cadeia zero, para R, nossa cadeia resultante, em preparação para o loop de hash.
Isso faz um loop na entrada de cada
$1
(n) caractere que carrega os caracteres lidos em c. Se a entrada terminar, c simplesmente ficará muito curto. Ar
opção garante que quaisquer caracteres especiais na entrada não sejam interpretados por bash. Esse é o-ε
título - quer
não é estritamente necessário, mas faz com que a função corresponda com mais precisão à entrada.Isso concatena os n caracteres lidos da entrada para R junto com os zeros para preenchimento (muitos zeros por enquanto).
Isso usa uma string here como entrada para a função hash. O conteúdo
${R::2*$1}
é uma substituição de parâmetro do bash um tanto esotérica que lê: R, começando de 0, apenas 2n caracteres.Aqui o loop termina e terminamos com:
Aqui, o mesmo truque de seqüência de caracteres de formato é usado para preencher 0 o número.
bc
é usado para convertê-lo em binário, definindo a base de saída (obase) como 2. O resultado é passado para a função / programa de hash cuja saída não é capturada e, portanto, é mostrada ao usuário.fonte
r
bandeira. Achei que 1 byte realmente não importa, mas se pressionado eu poderia raspar.read
comando?Pitão , 24 bytes
Como Pyth não permite que H seja usado para um nome de função, eu o uso
y
.Experimente online! Exemplo é com a versão "cada segundo caractere" de H.
fonte
Perl 6 ,
7968 bytesExperimente online!
Explicação
fonte
Limpo , 143 bytes
Experimente online!
fonte
Python 2 ,
126113 bytesExperimente online!
13 graças à triggernometria .
Sim, isso é uma abominação, por que não posso simplesmente usar um built-in para dividir uma string em pedaços ...? :-(
fonte
while
loop é o melhor componente que eu poderia esperar. 104 bytes'0'*~-n
em vez de'0'*(len(s)%n)
é mais curto (e realmente correto para entradas mais curtas).Programming Puzz
(16 caracteres). Substituindo'0'*(len(s)%n)
por'0'*~-n
correções que salvam 7 bytes.Python 2 ,
106102 bytesPela primeira vez, a função supera a lambda. -4 bytes para manipulação simples de sintaxe, graças a Jo King.
Experimente online!
fonte
Japonês , 27 bytes
Tente!
Eu não encontrei nenhum recurso para o Japt assumir funções diretamente como entrada, portanto, isso pega uma string que é interpretada como código Japt e espera que ela defina uma função. Especificamente,H que recebe caracteres em índices ímpares, enquanto este é o exemplo "multiplique os códigos de caracteres e use os 5 dígitos mais altos".
OvW
pega a terceira entrada e a interpreta como Japt e depois ag
chama. Substituir isso porOxW
permite a entrada como uma função Javascript, ou se a função já estava (de alguma forma) armazenada em W, poderia ser apenasW
e salvar 2 bytes. O link acima tem o exemplo trabalhado deDevido à maneira como Japt recebe entradas,s será n será H será
U
,V
eW
Explicação:
fonte
GolfScript , 47 bytes
Experimente online!
fonte
OK , 41 bytes
Experimente online!
fonte