Este desafio foi publicado como parte do desafio de abril de 2018 do LotM , bem como para o segundo aniversário do Brain-flak
Eu estava pensando sobre qual seria a maneira mais eficiente de codificar programas de ataques cerebrais. O mais óbvio a ser feito, uma vez que existem apenas 8 caracteres válidos, é mapear cada caractere para uma sequência de 3 bits. Isso certamente é muito eficaz, mas ainda é muito redundante. Existem alguns recursos do código de quebra-cérebro que poderíamos aproveitar para encurtar a codificação.
As nilads, todas representadas por 2 colchetes correspondentes, realmente atuam como uma única unidade de informação em vez de 2. Se substituíssemos cada colchete por um caractere de byte único, isso tornaria as codificações muito menores sem perder dados.
Este é menos óbvio, mas os bytes de fechamento das mônadas também são redundantes. Pense que você poderia adivinhar o que os
'?'
caracteres representam no snippet a seguir?{(({}?<>?<>?
Se supusermos que a entrada é um código de falha cerebral válido, existe apenas uma opção para cada um desses pontos de interrogação. Isso significa que podemos usar inequivocamente um caractere de mônada próxima para representar todos os colchetes de fechamento. Isso tem o benefício adicional de manter o conjunto de caracteres pequeno, o que ajudaria muito se desejássemos usar uma codificação huffman. Como o caractere de mônada próxima provavelmente será o caractere mais comum por uma ampla margem, ele poderá ser representado por um único bit, o que é extremamente eficiente.
Esses dois truques nos permitirão compactar o código do cérebro através do seguinte algoritmo:
Substitua todos os colchetes de fechamento de uma mônada por
|
. Ou, em outras palavras, substitua todos os colchetes que não sejam precedidos por sua correspondência de abertura por uma barra. Tão...(({})<(()()())>{})
se tornaria
(({}|<(()()()||{}|
Substitua cada nilad pelo suporte de fechamento. Portanto, colchetes correspondentes sem nada neles usam o seguinte mapeamento:
() --> ) {} --> } [] --> ] <> --> >
Agora, nosso último exemplo se torna:
((}|<()))||}|
Remova os
|
caracteres finais . Como sabemos que o número total de barras deve ser igual ao número total de({[<
caracteres, se houver barras no final ausentes, podemos inferi-las. Então, um exemplo como:({({})({}[()])})
se tornaria
({(}|(}[)
Seu desafio para hoje é reverter esse processo.
Dada uma sequência de ataques cerebrais comprimidos contendo apenas os caracteres (){}[]<>|
, expanda-os para o código original de ataques cerebrais. Você pode supor que a entrada sempre será expandida para um ataque cerebral válido. Isso significa que nenhum prefixo da entrada jamais conterá mais |
de({[<
caracteres.
A entrada não conterá à direita |
caracteres . Estes devem ser inferidos a partir do contexto.
Como de costume, você pode enviar um programa completo ou uma função, e os formatos de entrada / saída são permitidos. E como esse é um código-golfe , seu código será pontuado pelo tamanho do código-fonte em bytes, quanto menor a pontuação, melhor.
Casos de teste
Aqui estão alguns casos de teste. Se você quiser mais, pode gerar seus próprios casos de teste com este script python e o Brain-Flak Wiki , que é a origem da maioria desses casos de teste.
#Compressed code
#Original code
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
fonte
Respostas:
Flacidez cerebral ,
952916818bytesSalva 360 bytes calculando os parênteses opostos relativamente ao invés do zero (por exemplo,
')'
= em'(' + 1
vez de(((5 * 2) * 2) * 2) + 1
)Salva 34 bytes com algumas substituições diretas do DJMcMayhem
Economizou 10 bytes sobrepondo o
>]}
código de manipulação118 bytes salvos deduplicando rolos
Economizou 40 bytes aproveitando a pilha vazia para simplificar o primeiro rolo
Economizou 48 bytes marcando EOF com -1, permitindo um código de rolo mais conciso
Salvei 36 bytes usando a lógica de ações igual em vez da minha
Economizou 98 bytes graças a Jo King que encontrou uma maneira mais eficiente de criar a saída
Experimente online!
Jogando golfe pela primeira vez no Brain-Flak, provavelmente há grandes melhorias, mas funciona. Muita cópia / pasta para lidar com cada tipo de colchete, e muito obrigado ao gerador inteiro automático e ao snippet Roll daqui .
Explicação aqui , o TIO o formata mais facilmente
Resposta bônus:
Flacidez cerebral comprimida 583 bytes
Experimente online!
(Observe que o link acima não é executado porque o TIO não possui um interpretador Compress-Brain-Flak. Você pode encontrar um transpiler para o Brain-Flak aqui )
Eu verifiquei que isso é válido ao transpilar para o Brain-Flak usando essa ferramenta, agora eficiente o suficiente para que o tempo limite seja improvável.
fonte
<>(<()>)
por(<>)
. Além disso, você pode mudar(<>{}<>)(<()>)
para(<(<>{}<>)>)
Retina 0.8.2 ,
10398 bytesExperimente online! O link inclui casos de teste. Editar: salvou 5 bytes com inspiração em @MartinEnder. Explicação:
Coloque um
;
colchete depois de cada fechamento e troque-os todos para abrir colchetes, e troque também|
s para;
s.Conte o número de colchetes abertos inigualáveis e adicione tantos
;
s.Copie cada colchete de abertura para a correspondência
;
.Vire os colchetes copiados e exclua os
;
.fonte
|
para algo assim!
. Ele nem sequer bytes custar se você traduzir>-}
para<-{
(que eu acho que dáz
para|
).z
mas descobri uma maneira de eliminar alguns bytes de qualquer maneira.TIS ,
670666 bytes-4 bytes para pular para frente para pular para trás
Código:
Layout:
Experimente online!
Duvido que seja o menor, mas não vejo uma maneira de diminuí-lo. Infelizmente, todos os
NOP
s parece ser necessário para o sincronismo, e eu não posso colocar a pilha, onde@14
atualmente é por causa da leitura a partirANY
de@11
.A estrutura desta solução é a seguinte:
Ao ver um colchete aberto, o aberto é enviado ao longo da coluna da esquerda para saída e o fechamento é enviado ao longo da coluna da direita para a pilha.
Ao ver uma chave de fechamento, o abrir e fechar são enviados ao longo da coluna esquerda para serem impressos.
Ao ver um tubo, a pilha é acionada e enviada para a saída.
No EOF,
@1
começará a leitura de@2
, em vez do fluxo de entrada de@0
.@2
produz um fluxo interminável de tubos, para que a pilha seja drenada.Quando a entrada e a pilha estiverem esgotadas, o programa será interrompido.
Aviso: devido às limitações do TIS, o tamanho da pilha é limitado a 15. Se algo estiver aninhado mais profundamente que isso, esta implementação produzirá um resultado incorreto.
fonte
JavaScript (ES6), 107 bytes
Recebe a entrada como uma matriz de caracteres. Retorna uma string.
Experimente online!
fonte
Haskell,
127121 bytesExperimente online!
Edite: -6 bytes usando a função @ Laikoni para encontrar o colchete correspondente .
fonte
Ruby , 104 bytes
Este é um programa completo que gera no console.
(i<5?a:$>)<<r[-i]
tem que ser um dos melhores campos de golfe que eu já fiz.Experimente online!
Ruby , 106 bytes
Esta é a minha primeira solução. Uma função lambda anônima que pega e retorna seqüências de caracteres.
Experimente online!
fonte
Flacidez cerebral ,
606 548 496 418 394390 bytesExperimente online!
Comecei isso jogando a resposta de Kamil Drakari , mas ela escapou de mim até o ponto em que decidi publicá-la como uma resposta separada.
Explicação:
E claro...
Flacidez cerebral comprimida, 285 bytes:
fonte
Java 10, 424 bytes
É meio demorado, mas não consegui descobrir como reduzi-lo ainda mais. Este é um bom desafio, no entanto.
Experimente online aqui .
Versão não destruída:
fonte
Python 2,
188184180177 177174173 bytesGuardado 4 bytes graças a DJMcMayhem.
Experimente online!
fonte
s
acabar vazio. Caso contrário, você terminará com os caracteres extras no lado errado.Python 3 , 122 bytes
Experimente online!
fonte
Haskell , 152 bytes
Experimente online! ou verifique todos os casos de teste .
p
implementa um analisador recursivo, que pode ser um extermínio para a gramática simples.fonte
m
para encontrar o suporte correspondente.Python 2 , 244 bytes
Experimente online!
Demorou mais de uma hora ou duas para fazer isso funcionar ...
fonte