Expand compressed brain-flak

Question

This challenge was posted as part of the April 2018 LotM challenge, as well as for Brain-flak's 2nd birthday

---

I was thinking about what the most efficient way to encode brain-flak programs would be. The obvious thing to do, since there are only 8 valid characters, is to map each character to a 3-bit sequence. This is certainly very effective, but it's still very redundant. There are some features of brain-flak code that we could take advantage of to shorten the encoding.

• The nilads, which are all represented by 2 matched brackets, really act as a single unit of information rather than 2. If we replaced each bracket with a single byte character, this would make the encodings much smaller without losing any data.

• This one is less obvious, but the closing bytes of the monads are redundant too. Think you could guess what the '?' characters represent in the following snippet?

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

  If we assume the input is valid brain-flak code, then there is only one option for each of those question marks. This means that we can unambiguously use a close monad character to represent every closing bracket. This has the added benefit of keeping the character set small, which would greatly help if we wanted to use a huffman encoding. Since the close monad character will most likely be the most common character by a wide margin, it could be represent by a single bit, which is hugely efficient.

These two tricks will let us compress brain-flak code via the following algorithm:

1. Replace every closing bracket of a monad with |. Or in other words, replace every closing bracket that is not preceded by it's opening match with a bar. So...

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

   would become

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

2. Replace every nilad with it's closing bracket. Therefore, matched brackets with nothing in them use the following mapping:

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

   Now our last example becomes:

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

3. Remove trailing | characters. Because we know that the total number of bars should equal the total number of ({[< characters, if there are bars at the end missing, we can infer them. So an example like:

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

   would become

   ({(}|(}[)
   

Your challenge for today is to reverse this process.

Given a string of compressed brain-flak containing only the characters (){}[]<>|, expand it into the original brain-flak code. You can assume that the input will always expand to valid brain-flak. This means that no prefix of the input will ever contain more | than ({[< characters.

The input will not contain trailing | characters. These must be inferred from context.

As usual, you can submit either a full program or a function, and input/output formats are permissive. And since this is a code-golf, your code will be scored by the length of the source code in bytes, the smaller the score the better.

Test cases

Here are some test cases. If you would like more, you can generate your own test cases with this python script and the Brain-Flak Wiki, which is where the majority of these test cases come from.

#Compressed code
#Original code

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


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

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


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

Answer 1

Brain-Flak, 952 916 818 bytes

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

Saved 360 bytes by calculating opposing brackets relatively rather than from scratch (e.g. ')' = '(' + 1 instead of (((5 * 2) * 2) * 2) + 1)

Saved 34 bytes with some direct replacements from DJMcMayhem

Saved 10 bytes by overlapping the >]} handling code

Saved 118 bytes by deduplicating rolls

Saved 40 bytes by taking advantage of the empty stack to simplify the first roll

Saved 48 bytes by marking EOF with -1, enabling more concise roll code

Saved 36 bytes by using the stock equals logic instead of my own

Saved 98 bytes thanks to Jo King finding a more efficient way to build the output

Try it online!

First time golfing in Brain-Flak, so there are probably some really big improvements, but it works. Lots of copy/paste to handle each bracket type, and big thanks to the automatic integer generator and the Roll snippet from here.

Explanation here, TIO formats it more easily

Bonus answer:

Compressed Brain-Flak 583 bytes

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

Try it online!

(Note that the above link does not run because TIO doesn't have a Compressed Brain-Flak interpreter. You can find a transpiler to Brain-Flak here)

I have checked that this is valid by transpiling to Brain-Flak using this tool, now efficient enough that timing out is unlikely.

Answer 2

Retina 0.8.2, 103 98 bytes

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

Try it online! Link includes test cases. Edit: Saved 5 bytes with inspiration from @MartinEnder. Explanation:

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

Put a ; after every close bracket and change them all to open brackets, and change the |s to ;s too.

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

Count the number of unmatched open brackets and add that many ;s.

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

Copy each opening bracket to its matching ;.

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

Flip the copied brackets and delete the ;s.

Answer 3

TIS, 670 666 bytes

^{-4 bytes for jumping forward to jump back}

Code:

@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

Layout:

6 3
CCCCCCCCCCCCCCCCSC
I0 ASCII -
O0 ASCII -

Try it online!

I doubt this is smallest, but I don't see a way to make it smaller. Unfortunately, all the NOPs seem necessary for timing, and I can't put the stack where @14 currently is because of the read from ANY in @11.

The structure of this solution is as follows:

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

Upon seeing an open brace, the open is sent along the left column to be output, and the close is sent along the right column to the stack.

Upon seeing a close brace, the open and close are both sent along the left column to be output.

Upon seeing a pipe, the stack is popped and sent to output.

Upon EOF, @1 will begin reading from @2, instead of the input stream from @0. @2 produces an endless stream of pipes, so the stack will be drained.

Once both the input and the stack are exhausted, the program halts.

Warning: due to the limitations of TIS, the stack size is limited to 15. If anything is nested deeper than that, this implementation will produce an incorrect result.

Answer 4

JavaScript (ES6), 107 bytes

Takes input as an array of characters. Returns a string.

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``

Try it online!

Answer 5

Brain-Flak, 606 548 496 418 394 390 bytes

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

Try it online!

I started this by golfing Kamil Drakari's answer, but it got away from me to the point where I decided to post it as a separate answer.

Explanation:

{ #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

And of course...

Compressed Brain-Flak, 285 bytes:

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

Answer 6

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

Try it online!

Edit: -6 bytes by using @Laikoni's function to find the matching bracket.

Answer 7

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

This is a full program that outputs to the console. (i<5?a:$>)<<r[-i] has got to be one of the coolest golfs I have ever done.

Try it online!

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}

This is my first solution. An anonymous lambda function that takes and returns strings.

Try it online!

Answer 8

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;}

It's kind of lengthy, but I couldn't figure out how to shorten it further. This is a nice challenge though.

Try it online here.

Ungolfed version:

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
}

Answer 9

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

Saved 4 bytes thanks to DJMcMayhem.
Try it online!

Answer 10

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

Try it online!

Answer 11

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)

Try it online! or verify all test cases. p implements a recursive parser, which might be over kill for the simple grammar.

Answer 12

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

Try it online!

It took way more than an hour or two to get this working...