Tarefa
Codifique uma string que consiste inteiramente de letras maiúsculas ( A-Z
) usando apenas zeros e uns, usando seu próprio esquema favorito. Mas a regra não é tão simples!
Regras
- Seu programa / função deve manipular corretamente qualquer sequência de entrada válida de comprimento 8 .
- Os resultados devem ter o mesmo comprimento para todas as entradas.
- Os resultados devem ser distintos para entradas distintas.
- Os resultados devem ser tão curtos quanto possível.
- Os resultados devem ser balanceados em zero um (ter um número semelhante ao dos zeros). Eles não precisam ser iguais (ou seja, perfeitamente equilibrados), mas sua pontuação será penalizada por isso.
Você não precisa fornecer um programa / função que decodifique sua codificação.
Entrada e saída
- Você pode optar por aceitar qualquer conjunto de 26 caracteres ASCII imprimíveis distintos em vez de
A-Z
. - Você pode optar por imprimir qualquer par de caracteres ASCII imprimíveis distintos em vez de
0
e1
. - Você não tem permissão para gerar um número inteiro em vez de uma sequência de bits, pois pode ter zeros à esquerda e não está claro se você realmente cumpriu a regra 2.
- Se você decidir se desviar do padrão (
A-Z
entrada e01
saída), deverá especificar os conjuntos de caracteres de entrada / saída no seu envio.
Pontuação
- Pontuação básica: tamanho do código ou 1 se o seu programa estiver vazio.
- Sanções
- Pena por comprimento: multiplicar
1.5 ** (encoded length - 42)
- Não há bônus por ser mais baixo; 42 é o comprimento mínimo para uma codificação perfeitamente equilibrada de cadeias de 8 comprimentos com tamanho de alfabeto 26.
- Penalidade por desequilíbrio: multiplique
2 ** max(abs(ones - zeros) for every valid input of length 8)
, ondeones
ezeros
são as contagens de 1 e 0 em cada saída, respectivamente. - Seu envio deve mostrar um exemplo de pior caso (entrada / saída) ou explicação teórica sobre o valor da penalidade.
- Pena por comprimento: multiplicar
- A pontuação mais baixa vence.
Submissão de exemplo
Esolang hipotético, 0 Bytes, Pontuação 74733.8906
Aqui está um esolang hipotético, em que um programa vazio imprime todos os códigos ASCII dos caracteres da entrada em binário.
Por exemplo, se você fornecer AAAAAAAA
como entrada, o programa imprimirá 1000001
8 vezes seguidas, ou seja 10000011000001100000110000011000001100000110000011000001
.
O alfabeto de entrada é escolhido para ser CEFGIJKLMNQRSTUVXYZabcdefh
. Dessa forma, todos os caracteres são convertidos em sete dígitos em binário e a contagem de zero e um difere apenas um por caractere (todos eles têm três 1 e quatro 0 ou vice-versa quando convertidos em binário).
O comprimento da saída é sempre 56 e o pior desequilíbrio ocorre nas entradas como CCCCCCCC
, onde os zeros aparecem 8 vezes mais do que aqueles.
Portanto, a pontuação dessa submissão é 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906
.
fonte
Respostas:
Stax , 11 bytes, 0 de penalidade, Pontuação 11
Este programa usa
[0-9A-P]
para entrada e[01]
saída.Execute e depure on-line - clique no botão Executar para iniciar. Os quatro primeiros casos de teste são executados em milissegundos. O quinto em segundos. O sexto em milênios.
A representação ascii correspondente deste programa é essa.
Ele se apóia fortemente na
|N
instrução, que obtém a permutação subsequente de uma matriz.Todas as saídas são permutações da string inicial. Tem 21 zeros e 21 uns. Portanto, todas as saídas têm 42 caracteres e são perfeitamente equilibradas.
fonte
Geléia , 19 bytes
Experimente online!
Explicação
fonte
Pyth,
201914 bytes, Dif. Máximo: 0, Comprimento: 64, Pontuação:149636.5528142154.7251104745.5869Experimente online!
Usa o alfabeto em minúsculas (
[a-z]
) em vez de maiúsculas. Pode usar maiúsculas, substituindoG
porrG1
, ao custo de 2 bytes.Eu poderia ter traduzido a resposta Python 3 do HyperNeutrino para obter uma pontuação melhor, mas, francamente, quero uma resposta que realmente funcione.
fonte
Python 2 ,
779645 bytes, Máx. (Dif.) = 0, Comprimento = 48, Pontuação = 7346,95Experimente online!
O número mágico
4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33
(na base 36), ou seu equivalente decimal382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271
, codifica todas as 252 permutações de 5 se0
51
s.O algoritmo primeiros convertidos
A-Z
em0-25
e tratá-lo como um número base-26, em seguida, adicionar56*252**4
.Em seguida, o número é convertido em um número base-252 de 5 dígitos e substitui pela permutação correspondente de 5 se
0
51
s.Depois disso, exclua os 2 primeiros bits, o que é garantido
01
. Em seguida, codificamos a string em uma string de 48 bits, que consiste exatamente em 24 se0
241
s.fonte
7346.953125
).JavaScript (ES8), pontuação 22186.623779296875
Para uma entrada de comprimento uniforme, sempre gera 3,5 * de zeros e uns, portanto, paga apenas a penalidade de 1,5 ** 14. Caracteres suportados:
'+-.3569:<GKMNSUVYZ\cefijlqrtx
.fonte
Gelatina , 16 bytes
Usa
+,-./0123456789:;<=>?@ABCD
para entrada e retorna uma lista de uns e zeros.Isso tenta criar uma lista de 538.257.874.440 combinações na memória, portanto você precisará de uma grande quantidade de RAM para executá-la como está ...
Experimente online! (testável; comprimento de entrada 3, comprimento de saída 18)
Como funciona
fonte
Python 3 ,
985135 bytes, Diferença máxima 0, Comprimento 42, pontuação 135Experimente online!
Cortesia de Bubbler
Código não destruído:
Como outras abordagens parecem bastante ineficientes, tentei otimizar o tempo. É claramente O (N) em N bits de codificação, o que é grande-O ideal.
Dica: tente pensar no triângulo de Pascal para este ( este diagrama o revela)
Saídas de amostra:
Tempo de execução: <0,013 s (aproximadamente constante para todas as entradas)
fonte
Perl 5 , 55 bytes, diferença máxima 0, comprimento 42, pontuação
5655Isso funciona, mas levará um tempo longo, mas factível (
ZZZZZZZZ
levou 2,5 dias no meu computador). Memória não é problema.Utilizações
A-Z
como entrada e1
eA
como caracteres de codificação. Eles estão sempre perfeitamente equilibrados. Ignora as primeiras26^7 = 8031810176
combinações balanceadas que representam cadeias menores que 8 caracteres, mas tudo bem, pois existem538257874440
disponíveis e eu uso208827064575
e208827064575 + 8031810176 < 538257874440
.No entanto, ele "conta" até a combinação de alvos, que levará muito tempo. Por isso, no link TIO, usei apenas uma string de entrada muito curta (que também é suportada) para demonstrar que a saída está correta. Trabalhará um pouco mais do que
AAAAAA
antes do tempo limite do TIO.ZZZZZZZZ
deve ser cerca de26^3 = 17576
vezes mais lento.Experimente online!
O decodificador é quase o mesmo:
Experimente online!
fonte
> <> , 75 bytes, Diferença máxima 0, Comprimento 42, pontuação 75
Experimente online!
Aviso justo, isso levará muito, muito, muito tempo para ser concluído, mesmo no
AAAAAAAA
caso trivial . Percorre cada representação binária de um contador até que o número binário (base 26 da entrada)1
seja alcançado com 21 s. Se você quiser testar um pouco o programa, substitua oab+
da terceira linha pela1
qual retornará o enésimo número binário com apenas um único1
, Experimente on-line!fonte
Python 3 , 75 bytes, Dif. 0, Comprimento 42, Pontuação 112
Experimente online!
Isso só funciona em teoria devido a restrições de memória. Existem
538257874440
strings zero-um balanceadas distintas de comprimento 42 e208827064575
entradas possíveis, portanto, algumas das saídas possíveis não serão usadas.-37 bytes graças a @recursive
fonte
int(s,26)
o valor do índice em vez desum(...)
alterar o conjunto de caracteres de entrada.[0-9A-P]
, não é? Na minha máquina, #int("123ABC",26) == 12855114
C ++, 146 bytes, 42 comprimento máximo, 0 desequilíbrio, pontuação 146
Funciona para qualquer caractere contínuo de 26 caracteres, mas avisa que demora um tempo inaceitável
fonte
#include<algorithm>
por#import<regex>
.