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:
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
(({}|<(()()()||{}|
Replace every nilad with it's closing bracket. Therefore, matched brackets with nothing in them use the following mapping:
() --> ) {} --> } [] --> ] <> --> >
Now our last example becomes:
((}|<()))||}|
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
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}