Este desafío se publicó como parte del desafío LotM de abril de 2018 , así como para el segundo cumpleaños de Brain-flak

Estaba pensando en cuál sería la forma más eficiente de codificar programas de ataque cerebral. Lo obvio, ya que solo hay 8 caracteres válidos, es asignar cada carácter a una secuencia de 3 bits. Esto es ciertamente muy efectivo, pero aún es muy redundante. Hay algunas características del código brain-flak que podríamos aprovechar para acortar la codificación.

• Los nilads, todos representados por 2 paréntesis coincidentes, realmente actúan como una sola unidad de información en lugar de 2. Si reemplazamos cada paréntesis con un solo carácter de byte, esto haría que las codificaciones sean mucho más pequeñas sin perder ningún dato.

• Este es menos obvio, pero los bytes de cierre de las mónadas también son redundantes. ¿Crees que podrías adivinar qué '?'representan los personajes en el siguiente fragmento?

   {(({}?<>?<>?
  

  Si asumimos que la entrada es un código válido de brain-flak, entonces solo hay una opción para cada uno de esos signos de interrogación. Esto significa que podemos usar inequívocamente un carácter de mónada cercano para representar cada paréntesis de cierre. Esto tiene el beneficio adicional de mantener pequeño el conjunto de caracteres, lo que sería de gran ayuda si quisiéramos usar una codificación huffman. Dado que el carácter de mónada cercana probablemente será el personaje más común por un amplio margen, podría representarse con un solo bit, lo que es muy eficiente.

Estos dos trucos nos permitirán comprimir el código brain-flak a través del siguiente algoritmo:

1. Reemplace cada soporte de cierre de una mónada con |. O, en otras palabras, reemplace cada corchete de cierre que no esté precedido por su partido de apertura con una barra. Asi que...

   (({})<(()()())>{})
   

   se convertiría

   (({}|<(()()()||{}|
   

2. Reemplace cada nilad con su soporte de cierre. Por lo tanto, los corchetes coincidentes sin nada en ellos usan la siguiente asignación:

   () --> )
   {} --> }
   [] --> ]
   <> --> >
   

   Ahora nuestro último ejemplo se convierte en:

   ((}|<()))||}|
   

3. Eliminar |caracteres finales . Como sabemos que el número total de barras debe ser igual al número total de ({[<caracteres, si faltan barras al final, podemos inferirlas. Entonces un ejemplo como:

   ({({})({}[()])})
   

   se convertiría

   ({(}|(}[)
   

Su desafío para hoy es revertir este proceso.

Dada una cadena de ataques cerebrales comprimidos que contiene solo los caracteres (){}[]<>|, amplíelos al código original de ataques cerebrales. Puede suponer que la entrada siempre se expandirá a una falla mental válida. Esto significa que ningún prefijo de la entrada contendrá más |que ({[<caracteres.

La entrada no contendrá |caracteres finales . Estos deben inferirse del contexto.

Como de costumbre, puede enviar un programa completo o una función, y los formatos de entrada / salida son permisivos. Y dado que este es un código de golf , su código se puntuará por la longitud del código fuente en bytes, cuanto menor sea la puntuación, mejor.

Casos de prueba

Aquí hay algunos casos de prueba. Si desea más, puede generar sus propios casos de prueba con este script de Python y el Wiki Brain-Flak , de donde proviene la mayoría de estos casos de prueba.

#Compressed code
#Original code

())))
(()()()())


([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

({(}|(}[)|||}
({({})({}[()])}{})


(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}

Cerebro-Flak , 952 916 818 bytes

{(({})[(((()()()()()){}){}){}])((){[()](<{}>)}{}){{}(({})()<>)(<>)}{}(<>)<>(({})[(((()()()){}){}()){({}[()])}{}])((){[()](<{}>)}{})({}<>{})<>(({})[((((()()()()()){}){})){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[(((((()()()()()){}){}){}())){}{}])((){[()](<{}>)}{})({}<>{}){{}(<(<>({})()()<>)>)}{}<>(({})[(((()()()()()){}){}){}()])((){[()](<{}>)}{}){{}(({})[()])(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}(<>)}{}(<>)<>(({})[(((((()()()()()){})){}{}())){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[((((()()()()()){}){})()){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[(((((()()()()()){}){}){}())()){}{}])((){[()](<{}>)}{})({}<>{}){{}<>(<(({})[()()])(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}>)}{}<>(({})[(((((()()()()()){}){})()){}{}){}])((){[()](<{}>)}{}){{}{}(<(<>{}<>)>)}{}(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}<>}{}{({}<>)<>}<>

Ahorró 360 bytes calculando paréntesis opuestos relativamente en lugar de hacerlo desde cero (por ejemplo, ')'= en '(' + 1lugar de (((5 * 2) * 2) * 2) + 1)

Guardado 34 bytes con algunos reemplazos directos de DJMcMayhem

Se guardaron 10 bytes superponiendo el >]}código de manejo

Ahorró 118 bytes al deduplicar rollos

Ahorró 40 bytes aprovechando la pila vacía para simplificar el primer rollo

Ahorró 48 bytes marcando EOF con -1, lo que permite un código de rollo más conciso

Ahorré 36 bytes usando la lógica de stock igual en lugar de la mía

Ahorró 98 bytes gracias a que Jo King encontró una manera más eficiente de construir la salida

Pruébalo en línea!

Golf por primera vez en Brain-Flak, por lo que probablemente haya algunas mejoras realmente grandes, pero funciona. Un montón de copiar / pegar para manejar cada tipo de soporte, y muchas gracias al generador de enteros automático y el fragmento de rollo desde aquí .

Explicación aquí , TIO lo formatea más fácilmente

Respuesta extra:

Brain-Flak comprimido 583 bytes

{((}|[((()))))|}|}|}||(){[)|(<}|||}|{}((}|)>|(>||}(>|>((}|[((()))|}|})|{(}[)|||}||(){[)|(<}|||}|(}>}|>((}|[(((()))))|}|}||}}||(){[)|(<}|||}|(}>}|>((}|[((((()))))|}|}|})||}}||(){[)|(<}|||}|(}>}|{}(<(>(}|))>||||}>((}|[((()))))|}|}|})||(){[)|(<}|||}|{}((}|[)||(>|>(<(}<{(}>|>|}||||>{(}>|>|}(>||}(>|>((}|[((((()))))|}||}})||}}||(){[)|(<}|||}|(}>}|>((}|[(((()))))|}|}|)|}}||(){[)|(<}|||}|(}>}|>((}|[((((()))))|}|}|})|)|}}||(){[)|(<}|||}|(}>}|{}>(<((}|[))||(>|>(<(}<{(}>|>|}||||>{(}>|>|}|||}>((}|[((((()))))|}|}|)|}}|}||(){[)|(<}|||}|{}}(<(>}>||||}(>|>(<(}<{(}>|>|}||||>{(}>|>|}>|}{(}>|>|>

Pruébalo en línea!

(Tenga en cuenta que el enlace anterior no se ejecuta porque TIO no tiene un intérprete Compressed Brain-Flak. Puede encontrar un transpilador para Brain-Flak aquí )

He comprobado que esto es válido al transpirar a Brain-Flak con esta herramienta, ahora lo suficientemente eficiente como para que el tiempo de espera sea poco probable.

Retina 0.8.2 , 103 98 bytes

[])}>]
$&;
T`])}>|`[({<;
r`(.*)((;)|(?<-3>.))*
$&$.1$*;
(?<=(.)((;)|(?<-3>.))*);
;$1
T`;-{`_>-}`;.

Pruébalo en línea! El enlace incluye casos de prueba. Editar: guardado 5 bytes con la inspiración de @MartinEnder. Explicación:

[])}>]
$&;
T`])}>|`[({<;

Coloque un ;corchete después de cada cierre y cámbielos a todos para abrir los corchetes, y cambie los |s a ;s también.

r`(.*)((;)|(?<-3>.))*
$&$.1$*;

Cuente el número de paréntesis abiertos sin igual y agregue esa cantidad de ;s.

(?<=(.)((;)|(?<-3>.))*);
;$1

Copie cada paréntesis de apertura en su correspondencia ;.

T`;-{`_>-}`;.

Voltee los corchetes copiados y elimine el ;s.

TIS , 670 666 bytes

^{-4 bytes para saltar hacia adelante para saltar hacia atrás}

Código:

@0
MOV UP RIGHT
@1
MOV ANY ACC
SUB 41
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
MOV ACC DOWN
@2
NOP
MOV 124 LEFT
@3
MOV ANY DOWN
@4
MOV UP ACC
JGZ O
MOV 40 LEFT
JLZ (
MOV 41 LEFT
JRO 3
O:SUB 21
MOV ACC DOWN
JRO -8
(:MOV 41 RIGHT
@5
MOV ANY DOWN
@6
MOV ANY DOWN
@7
MOV UP ACC
JGZ O
MOV 60 LEFT
JLZ <
MOV 62 LEFT
JRO 3
O:SUB 31
MOV ACC DOWN
JRO -8
<:MOV 62 RIGHT
@8
MOV ANY DOWN
@9
MOV ANY DOWN
@10
S:MOV UP ACC
JGZ O
MOV 91 LEFT
JLZ [
MOV 93 LEFT
JRO 3
O:SUB 31
MOV ACC DOWN
JRO -8
[:MOV 93 RIGHT
@11
MOV ANY DOWN
@12
MOV ANY DOWN
@13
MOV UP ACC
JEZ |
MOV 123 LEFT
JLZ {
MOV 125 LEFT
JRO 2
|:MOV DOWN LEFT
JRO -7
{:MOV 125 RIGHT
@14
MOV ANY DOWN
@15
MOV UP DOWN
@16
MOV UP LEFT

Diseño:

6 3
CCCCCCCCCCCCCCCCSC
I0 ASCII -
O0 ASCII -

Pruébalo en línea!

Dudo que sea más pequeño, pero no veo una manera de hacerlo más pequeño. Desafortunadamente, todos los NOPs parecen necesarios para el tiempo, y no puedo poner la pila donde @14está actualmente debido a la lectura desde ANYadentro @11.

La estructura de esta solución es la siguiente:

Input
  |
  V
  0    1:synchro  2:EOF
  3    4:parens     5
  6    7:angles     8
  9   10:squares   11
 12   13:curlies   14
 15      stack     16
  |
  V
Output

Al ver un paréntesis abierto, el abierto se envía a lo largo de la columna izquierda para que salga, y el cierre se envía a lo largo de la columna derecha a la pila.

Al ver una llave de cierre, tanto la apertura como el cierre se envían a lo largo de la columna izquierda para su salida.

Al ver una tubería, la pila se abre y se envía a la salida.

En EOF, @1comenzará a leer desde @2, en lugar de la secuencia de entrada desde @0. @2produce un flujo interminable de tuberías, por lo que la pila se drenará.

Una vez que la entrada y la pila están agotadas, el programa se detiene.

Advertencia: debido a las limitaciones de TIS, el tamaño de la pila está limitado a 15. Si hay algo anidado más profundo que eso, esta implementación producirá un resultado incorrecto.

JavaScript (ES6), 107 bytes

Toma la entrada como una matriz de caracteres. Devuelve una cadena.

a=>a.map(c=>(n=(S='|()[]{}<>').indexOf(c))?n&1?(s=[S[n+1],...s],c):S[n-1]+c:s.shift(),s=[]).join``+s.join``

Pruébalo en línea!

Haskell, 127 121 bytes

(""#)
(u:t)#('|':b)=u:t#b 
s#(c:b)|elem c")>]}"=m c:c:s#b|q<-m c:s=c:q#b
s#b=b++s
m c="> < ] [)(} {"!!mod(fromEnum c-6)27

Pruébalo en línea!

Editar: -6 bytes usando la función de @ Laikoni para encontrar el paréntesis correspondiente .

Ruby , 104 bytes

a=[];$<.chars{|c|r="|[{(<>)}]";i=r.index(c);i<1||(i<5?a:$>)<<r[-i];$>.<<i<1?a.pop: c};$><<a.reverse.join

Este es un programa completo que sale a la consola. (i<5?a:$>)<<r[-i]tiene que ser uno de los mejores campos de golf que he hecho.

Pruébalo en línea!

Ruby , 106 bytes

->s{a=[];(s.chars.map{|c|r="|>)}][{(<";d=r[-i=r.index(c)];i<5||a<<d;i<1?a.pop: i<5?d+c:c}+a.reverse).join}

Esta es mi primera solución. Una función lambda anónima que toma y devuelve cadenas.

Pruébalo en línea!

Brain-Flak , 606 548 496 418 394 390 bytes

{((({})))(<>)(((((((([(())()()()]){}){}){}())(()))(((())()())()){}{})){}[()])({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}<><{}>){({}({})<>)(<>)}{}({}<>)(<>)(((((((([(())()()()]){}){}){}())(()))(((())()){}()){})){})({<(({}<>{}[()]))>[()]{()(<{}>)}{}<>}{}<>){(<({}(<()>)<>({})<{({}<>)<>}>)>)<>{({}<>)<>}}{}({}()<>){{}({}<>)((<>))}{}{}<>(<({}(<()>)<><{({}<>)<>}>)>)<>{({}<>)<>}{}<>}{}{({}{}<>)<>}<>

Pruébalo en línea!

Comencé esto jugando al golf con la respuesta de Kamil Drakari , pero se me escapó hasta el punto en que decidí publicarla como una respuesta separada.

Explicación:

{ #While input on stack
	((({})))(<>)	#Preserve copy of the character
	(((((		#Push the differences between start bracket characters
	((([(())()()()]){}){}){}())	#Push -31, 1
	(()))				#Push -30, 1
	(((())()())()){}{})		#Push -19, 1
	){}[()])			#Push -39
	({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}<><{}>)	#If the character is any of the start brackets
	{({}({})<>)(<>)}{}					#Push the current character + TOS to the other stack

	({}<>)(<>)
	(((((		#Push the differences between end bracket characters
	((([(())()()()]){}){}){}())	#Push -31, 1
	(()))				#Push -30, 1
	(((())()){}()){})		#Push -19, 1
	){})				#Push -40
	({<(({}<>{}[()]))>[()]{()(<{}>)}{}<>}{}<>)	#If the character is any of the end brackets
	{(<({}(<()>)<>({})<{({}<>)<>}>)>)<>{({}<>)<>}}{}	#Push the character + TOS to the output

	({}()<>)	#If the character is not a |
	{{}({}<>)((<>))}{}	#Move current character to the other stack and push a zero
	{}		#Pop the top value of the stack, either the | or a 0
	<>(<({}(<()>)<><{({}<>)<>}>)>)<>{({}<>)<>}{}<>	#And push top of other stack to the output
}{}
{({}{}<>)<>}<>	#Reverse output and append the excess end brackets

Y por supuesto...

Brain-Flak comprimido, 285 bytes:

{(((}|||(>|(((((((([()|)))||}|}|})|()||((()|))|)|}}||}[)||({<((}>}[)||||){[)|(<}|||}>|}><}||{(}(}|>|(>||}(}>|(>|(((((((([()|)))||}|}|})|()||((()|)|})|}||}|({<((}>}[)||||[)|{)(<}|||}>|}>|{(<(}(<)||>(}|<{(}>|>|||||>{(}>|>||}(})>|{}(}>|((>|||}}>(<(}(<)||><{(}>|>|||||>{(}>|>|}>|}{(}}>|>|>

Java 10, 424 bytes

s->{int i=0;for(var c:s.toCharArray()){if("(<[{".indexOf(c)>-1)i++;if(c=='|')i--;}for(;i-->0;)s+='|';s=s.replace(")","()").replace(">","<>").replace("]","[]").replace("}","{}");char[]c=s.toCharArray(),r=new char[124];r[40]=41;r[60]=62;r[91]=93;r['{']='}';var o="";for(;++i<c.length ;){if(c[i]=='|'){c[i]=o.charAt(0);o=o.substring(1);}if("(<[{".indexOf(c[i])>-1&")>]}".indexOf(i+1<c.length?c[i+1]:0)<0)o=r[c[i]]+o;}return c;}

Es un poco largo, pero no pude descubrir cómo acortarlo aún más. Sin embargo, este es un buen desafío.

Pruébelo en línea aquí .

Versión sin golf:

s -> { // lambda taking a String argument and returning a char[]
    int i = 0; // used for counting the number of '|'s that have been removed at the end of the input
    for(var c : s.toCharArray()) { // look at every character
        if("(<[{".indexOf(c) > -1) // if it's an open monad character
            i++; // we will need one more '|'
        if(c == '|') // if it's a close monad character
            i--; // we will need one '|' less
    }
    for(; i-- > 0; ) // add as many '|'
        s += '|';    // as necessary
    s = s.replace(")", "()").replace(">", "<>").replace("]", "[]").replace("}", "{}"); // replace compressed nilads with their uncompressed versions
    char[] c = s.toCharArray(), // from now on working on a char[] is more efficient since we will only be comparing and replacing
    r = new char[124]; // map open monad characters to their counterparts:
    r[40] = 41;   // '(' to ')'
    r[60] = 62;   // '<' to '>'
    r[91] = 93;   // '[' to ']'
    r['{'] = '}'; // '{' to '}'
    var o = ""; // we use this String as a kind of stack to keep track of the last open monad character we saw
    for(; ++i < c.length ;) { // iterate over the length of the expanded code
        if(c[i] == '|') { // if the current character is a close monad character
            c[i] = o.charAt(0); // replace it with the top of the stack
            o = o.substring(1); // and pop the stack
        }
        if("(<[{".indexOf(c[i]) > -1 // if the current character is an open monad/nilad character
         & ")>]}".indexOf(i+1 < c.length ? c[i+1] : 0) < 0) // and it's not part of a nilad (we need to test for length here to avoid overshooting)
            o = r[c[i]]+o; // using the mapping we established, push the corresponding character onto the stack
    }
    return c; // return the uncompressed code
}

Python 2, 188 184 180 177 174 173 bytes

p,q='([{<',')]}>'
d,s,a=dict(zip(p,q)),[],''
for c in input():
 if c in d:a+=c;s+=[c]
 elif'|'==c:a+=d[s.pop()]
 else:a+=dict(zip(q,p))[c]+c
for c in s[::-1]:a+=d[c]
print a

Guardado 4 bytes gracias a DJMcMayhem.
Pruébalo en línea!

Python 3 , 122 bytes

D='()<>[]{} '
def f(x):
 a=s=''
 for c in x:i=D.find(c);a+=i<0and s[0]or D[i-(i&1):i+1];s=D[i+1][i&1:]+s[i<0:]
 return a+s

Pruébalo en línea!

Haskell , 152 bytes

fst.p
m c="> < ] [)(} {"!!mod(fromEnum c-6)27
p(c:r)|elem c")]}>",(s,t)<-p r=(m c:c:s,t)|c/='|',(s,'|':t)<-p$r++"|",(u,v)<-p t=(c:s++m c:u,v)
p e=("",e)

Pruébalo en línea! o verificar todos los casos de prueba . pimplementa un analizador recursivo, que podría ser más de matar para la gramática simple.

Python 2 , 244 bytes

s=input()
B='([{<'
C=')]}>'
Z=zip(B,C)
P=sum(map(s.count,B))-s.count('|')
for i,j in Z:s=s.replace(j,i+j)
s+=P*'|'
b=[0]
for i in s:[b.pop()for j,k in Z if j==b[-1]<k==i];b+=[i][:i in B];s=i=='|'and s.replace(i,C[B.find(b.pop())],1)or s
print s

Pruébalo en línea!

Tomó más de una o dos horas para que esto funcionara ...