O objetivo desse desafio é encontrar uma implementação incrivelmente curta da função a seguir p
, no idioma de sua escolha. Aqui está o código C implementando-o (veja
este link TIO que também imprime suas saídas) e uma página da Wikipedia que o contém.
unsigned char pi[] = {
252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,
233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,
249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,
5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,
235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,
181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,
21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,
50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,
223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,
224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,
167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,
173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,
7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,
225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,
32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,
89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182,
};
unsigned char p(unsigned char x) {
return pi[x];
}
O que é p
p
é um componente de dois padrões criptográficos russos, a função hash Streebog e a cifra de bloco Kuznyechik . Em este artigo (e durante reuniões ISO), os designers destes algoritmos reivindicado que eles gerada a matriz pi
, escolhendo as permutações de 8 bits aleatórios.
Implementações "impossíveis"
Existem permutações em 8 bits. Portanto, para uma dada permutação aleatória, não se espera que um programa que a implemente precise menos de 1683 bits.
No entanto, encontramos várias implementações anormalmente pequenas (que listamos aqui ), por exemplo, o seguinte programa C:
p(x){unsigned char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",l=0,b=17;while(--l&&x^1)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
que contém apenas 158 caracteres e, portanto, cabe em 1264 bits. Clique aqui para ver se funciona.
Falamos sobre uma implementação "impossivelmente" curta, porque, se a permutação fosse a saída de um processo aleatório (conforme reivindicado por seus designers), um programa desse tamanho não existiria (consulte esta página para mais detalhes).
Implementação de referência
Uma versão mais legível do código C anterior é:
unsigned char p(unsigned char x){
unsigned char
s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
if(x != 0) {
unsigned char l=1, a=2;
while(a!=x) {
a=(a<<1)^(a>>7)*29;
l++;
}
unsigned char i = l % 17, j = l / 17;
if (i != 0) return 252^k[i]^s[j];
else return 252^k[j];
}
else return 252;
}
A tabela k
é tal que k[x] = L(16-x)
, onde L
é linear no sentido em que L(x^y)==L(x)^L(y)
, e onde, como em C, ^
denota o XOR. No entanto, não conseguimos alavancar essa propriedade para reduzir nossa implementação. Não temos conhecimento de nenhuma estrutura s
que possa permitir uma implementação mais simples - porém sua saída está sempre no subcampo, ou seja, onde a exponenciação é feita no campo finito. Claro, você é absolutamente livre para usar uma expressão mais simples, caso encontre uma!s
O loop while corresponde à avaliação de um logaritmo discreto no campo finito com 256 elementos. Ele funciona através de uma pesquisa simples de força bruta: a variável dummy a
é configurada para ser um gerador do campo finito e é multiplicada por esse gerador até que o resultado seja igual a x
. Quando for o caso, temos esse l
log discreto x
. Esta função não está definida em 0, portanto, o caso especial correspondente à if
instrução.
A multiplicação pelo gerador pode ser vista como uma multiplicação por em que é então reduzida no módulo polinomial . O papel do é garantir que a variável permaneça em 8 bits. Como alternativa, poderíamos usar ; nesse caso, poderia ser um (ou qualquer outro tipo inteiro). Por outro lado, é necessário começar como precisamos ter quando for igual a 1.unsigned char
a
a=(a<<1)^(a>>7)*(256^29)
a
int
l=1,a=2
l=255
x
Mais detalhes sobre as propriedades de p
são apresentados em nosso artigo , com um resumo da maioria de nossas otimizações para obter a implementação curta anterior.
Regras
Propor um programa que implemente a função p
em menos de 1683 bits. Quanto mais curto o programa, mais anormal é, para um determinado idioma, mais curto é melhor. Se o seu idioma possuir Kuznyechik, Streebog ou p
como um componente interno, você não poderá usá-lo.
A métrica que usamos para determinar a melhor implementação é o tamanho do programa em bytes. Usamos o tamanho do bit em nosso artigo acadêmico, mas mantemos os bytes aqui por uma questão de simplicidade.
Se o seu idioma não tem uma noção clara da função, argumento ou de saída, a codificação é até você para definir, mas truques como codificar o valor pi[x]
como x
são, obviamente, proibida.
Já submetemos um trabalho de pesquisa com nossas descobertas sobre esse tópico. Está disponível aqui . No entanto, se for publicado em um local científico, teremos o prazer de reconhecer os autores das melhores implementações.
A propósito, obrigado a xnor por sua ajuda ao elaborar esta pergunta!
fonte
1683 bits at most
uma restrição estrita [sic?] Ou a meta?Respostas:
Conjunto AMD64 (78 bytes ou 624 bits de código de máquina)
Montagem x86 de 64 bits
Código de 64 bits desmontado
Montagem x86 de 32 bits
Código de 32 bits desmontado
fonte
uint8_t
args são estendidos em zero para 64 bits para o JRCXZ). Além disso, se você escrever um código dependente da posição, poderá inserir o endereço da tabela em um registrador com 5 bytes emmov ebx, imm32
vez de 6 bytescall
/pop
. Ou usá-lo como umdisp32
emmov al, [table + rax]
, mas que pode perder, pois você tem doisxlatb
e ummov
já. O truque da chamada + pop-shellcode vence contra o LEA relativo a RIP de 7 bytes com os dados após oret
, no entanto.CJam ,
726766.63 byteses*
repete algo no registro de data e hora atual, que é um número grande, e levaria muito tempo para terminar.Versão realmente testável, 64 bytes:
Experimente online!
Experimente tudo online!
Para executar este código (em uma máquina Linux), você precisa adicionar a linha
en_US.ISO-8859-1 ISO-8859-1
em/etc/locale.gen
e executarlocale-gen
. Então você pode usar:Ou você pode tentar esta versão UTF-8 equivalente a 72 bytes:
Explicação
Os caracteres na sequência são:
fonte
"Ý0$&Ü™ÖD�’\n˜×EO“N"
?Geléia
7159 bytesExperimente online!
Verifique todas as possibilidades
Agora reescrito usando uma versão reformulada da resposta inteligente do CJam de jimmy23013, portanto, não deixe de votar também nessa! Usa apenas 472 bits (28,0% da abordagem ingênua). @ jimmy23013 também salvou outro byte!
Explicação
Estágio 1
Etapa 2
Etapa 3
Abordagem original
Geléia ,
7166 bytesExperimente online!
Verifique todas as possibilidades
Um link monádico ou programa completo que utiliza um único argumento e retorna o valor relevante de
pi[x]
. São 536 bits, portanto menos de um terço do armazenamento ingênuo de pi.Salvo 3 bytes utilizando o método para encontrar
l
a partir resposta CJam de jimmy23013 isso não deixe de upvote que um também!Explicação
Estágio 1
Etapa 2
Etapa 3
fonte
C (gcc) ,
157 148 140139 bytesModesta melhoria em relação ao exemplo C.
Experimente online!
C (gcc) ,
150 142 127126 bytesEste depende das peculiaridades gcc e x86 e UTF-8.
Experimente online!
Obrigado a @XavierBonnetain pelo comportamento -1 e menos indefinido.
fonte
05AB1E ,
10110098979594 bytes-3 bytes graças a @Grimy .
Experimente online ou verifique todos os casos de teste .
Explicação:
Porta da função C de Xavier Bonnetain (versão de 1106 bits) a partir daqui , com o mesmo aprimoramento @ceilingcat feito em sua resposta C para economizar 3 bytes, por isso não deixe de votar nele!
Consulte esta dica 05AB1E (seções Como compactar números inteiros grandes? E Como compactar listas de números inteiros? ) Para entender por que
•α">η≠ε∍$<Θγ\&@(Σα•
é20576992798525946719126649319401629993024
;•α">η≠ε∍$<Θγ\&@(Σα•₅в
é[64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]
;Ƶ¹
é285
;•¾#kôlb¸ù,-ó"a·ú•
é930891775969900394811589640717060184
;•¾#kôlb¸ù,-ó"a·ú•₅в
é[189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]
; eƵ∞
é188
.fonte
s^
=>^
(XOR é comutativo). Na verdade, não és^_
o mesmo queQ
?i==0 || X==0 || X==1
.Stax ,
6564625958 bytesExecute e depure
Infelizmente, este programa usa algumas instruções que usam internamente algumas instruções stax obsoletas. Esqueci de atualizar a implementação deles. Isso faz com que algum aviso falso apareça, mas os resultados ainda estão corretos.
Isso é inspirado na excelente resposta de jimmy23013 . Algumas peças foram alteradas para se adequar melhor ao stax.
Os programas Stax gravados em ASCII imprimível têm uma representação alternativa que economiza um pouco mais de 1 bit por byte, pois existem apenas 95 caracteres ASCII imprimíveis.
Aqui está a representação ascii deste programa formatada para "legibilidade" com comentários.
Execute este
Versão modificada para executar para todas as entradas 0..255
fonte
S
para poder definido. Você pode obter o conjunto de potências de [18 38 36 48], indexar e reduzir em xor. (Eu não conheço Stax e não tenho certeza se seria mais curto.)S
operador não está na ordem certa para que isso funcione. por exemplo"abc"SJ
(conjunto de potências de "abc" associado a espaços) produz "a ab abc ac b bc c".Python 3 , 151 bytes
Experimente online!
Uma função que implementa a permutação. O código usa apenas caracteres ASCII de 7 bits.
Codifica
k
como um bytestring do Python 3, alterado^64
para o intervalo imprimível. Por outro lado,s
é codificado como os dígitos base-256 de uma constante numérica e os dígitos são extraídos como[number]>>[shift]*8&255
. Isso foi mais curto do que a codificaçãos
em uma sequência devido ao número de caracteres de escape necessário, mesmo com uma mudança ideal^160
para minimizá-los.O cálculo do log discreto é feito ao contrário. A atualização faz um
x=x*2^x//128*285
loop no grupo cíclico, simulando a multiplicação pela geração, até atingir a identidadex=1
. Iniciamos o log discreto eml=255
(a duração do ciclo) e o diminuímos a cada iteração. Para lidar com ox=0
caso e fazer com que ele não fique em loop para sempre, também encerramos quandol=0
, que faz ox=0
mapal=0
como especificado.O Python 2 perde por não ter boas
map(ord,...)
seqüências de bytes , por isso precisamos fazer (o ArBo salvou um byte aqui). Permite usar em/
vez de//
para a divisão inteira.Python 2 , 156 bytes
Experimente online!
fonte
JavaScript (ES6), 139 bytes
Semelhante à versão do Node.js, mas usando caracteres além do intervalo ASCII.
Experimente online!
JavaScript (Node.js) ,
149148 bytesCom base na implementação C de Xavier Bonnetain (que é apresentada aqui ).
Experimente online!
Codificação
Na resposta original de Xavier, as tabelas
s[]
ek[]
são armazenadas na seguinte sequência:Os primeiros 17 caracteres são as representações ASCII de
k[i] XOR 64
e os próximos 15 caracteres são as representações ASCII des[i-17] XOR 173
, ous[i-17] XOR 64 XOR 17 XOR 252
.k[i] XOR 64
s[i-17] XOR 173
Aqui está o que temos:
110010011001001
Nota: Esta é apenas uma nota lateral, não relacionada às respostas acima.
Experimente online!
fonte
C # (compilador interativo do Visual C #) , 141 bytes
Apenas uma porta da solução de exemplo, portada para C #.
Experimente online!
fonte
Python 3 , 182 bytes
Experimente online!
O Python não ganhará o primeiro prêmio aqui, mas este ainda é um golfe de 10 bytes do melhor programa Python daqui .
Python 3 , 176 bytes
Experimente online!
Como lambda, é seis bytes mais curto ainda. Dói-me ter de usar
if... else
, mas não vejo outra opção para curtos-circuitos, dado que 0 é uma resposta possível.Python 3 , 173 bytes
Experimente online!
Ainda mais curto em bytes (embora eu não tenha certeza sobre bits, porque isso não é mais puro ASCII), cortesia de ovs.
fonte
\x..
escapesFerrugem ,
170163 bytesExperimente online!
Esta é uma porta da minha solução em C, com uma sequência ligeiramente diferente, que não requer o xor 17. Espero que a maioria das soluções baseie a sequência "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "também pode ser aprimorado (apenas altere a string, remova o xor 17 e xor 173 em vez de 188).
Eu removi uma das pesquisas adicionando condicionalmente
17*17
al
, como fizemos (mais ou menos) na solução de código de máquina do ARM.A ferrugem possui inferência e fechamento de tipo, mas seus lançamentos (mesmo para booleanos ou entre números inteiros) são sempre explícitos, a mutabilidade deve ser marcada, ela não possui um operador ternário, operações inteiras, por padrão, pânico no estouro e operações de mutação (
l+=1
) retorna a unidade. Não consegui obter uma solução mais curta com os iteradores, pois o fechamento + o mapeamento ainda são bastante detalhados.Isso parece fazer do Rust uma péssima escolha para o golfe. No entanto, mesmo em uma linguagem que enfatiza a legibilidade e a segurança em detrimento da concisão, somos muito curtos.
Atualização: usou uma função anônima, por sugestão da manatwork.
fonte
let p=
para o Cabeçalho e não contá-lo. Não tem certeza sobre a;
chamada anônima: não é necessário: Experimente on-line! .05AB1E , 74 bytes
Porto da primeira resposta de Jelly de @NickKennedy . Eu estava trabalhando diretamente em uma porta da resposta CJam de @ jimmy23013 , mas já tinha 78 bytes e ainda precisava corrigir um erro, para que fosse maior. Definitivamente, isso ainda pode ser bastante praticado.
Experimente online ou verifique todos os casos de teste .
Explicação:
Consulte esta dica 05AB1E (seções Como compactar números inteiros grandes? E Como compactar listas de números inteiros? ) Para entender por que
Ƶf
é142
;•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•
é29709448685778434533295690952203992295278432248
,ƵŠ
é239
; e•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠв
é[19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
.fonte