Brain-Flak is a stack-based esoteric language with eight commands:

()     Evaluates to 1
<>     Switch active stack; evaluates to 0
[]     Evaluates to height of current stack
{}     Pop current stack; evaluates to the popped number
(...)  Execute block and push the result; evaluates as result
<...>  Execute block; evaluates as 0
[...]  Execute block; evaluates as negation of result 
{...}  While top of active stack is nonzero, execute block

Write a program or function to detect and remove one common type of push-pop redundancy that often occurs when writing Brain-Flak code.

Finding Redundancy

To determine whether a push and pop are truly redundant, we must understand which scopes use the return value of instructions:

  • The return value of any top-level instruction is ignored.
  • (...) will always use the return values of its children.
  • <...> will always ignore the top-level instruction of its children.
  • {...} will pass the return values of its children to the enclosing scope; that is, their return values will be used if and only if {...} itself is in a scope that uses its return value.
  • [...] theoretically works like {...} in this sense; however, you may assume that [...] is always in a scope that cares about return value, thus treating it like (...).

The type of redundancy we are interested in occurs in any substring of the form (A)B{} satisfying the following:

  • A is a balanced string; that is, the parentheses around A are matched.
  • (A) is in a scope that ignores its return value.
  • B does not contain [], <>, or either half of the {...} monad.
  • The {} immediately following B pops the value pushed by (A). That is, B has an equal number of {} and ...), and no prefix of B has more {} than ...).

Note that B is typically not a balanced string.

Removing Redundancy

To remove this redundancy, we temporarily introduce a symbol 0 to the language, which evaluates to 0. With this symbol, a redundant string (A)B{} can be safely replaced by 0BA. Since Brain-Flak does not have a 0 symbol, we must make simplifications to remove it:

  • A 0 with a sibling can be removed entirely, as can any top-level 0s. (If there are two 0s as the only children of a monad, only one of them can be removed.)
  • [0] and <0> can be simplified to 0.
  • If you encounter a (0), find the matching {}; replace the (0) and matching {} with 0s.
  • {0} will never happen. If I'm wrong about this, you may have undefined behavior in this case.


  • Input is a string taken by any reasonable method.
  • Input is guaranteed to be valid Brain-Flak code consisting only of brackets.
  • Any [...] monads in the input will be in scopes that do not ignore their return values.
  • Output is the result of using this algorithm (or another algorithm with the same result) to remove push-pop redundancies in the input program.
  • The input might not contain any redundancy; in that case, the input program should be output unchanged.
  • If your solution is in Brain-Flak, it should hopefully not detect any redundancy in its own code.
  • This is , so the shortest program (in bytes) in each language wins.

Test cases

With redundancy (with redundant push and pop marked):

Shortest redundancy
({}){} -> {}
^  ^^^

First example from tips post
({}<>)({}()) -> ({}<>())
^    ^ ^^

Second example from tips post
({}<({}<>)><>)(<((()()()){}[((){}{})])>) -> (<((()()()){}[((){}<({}<>)><>{})])>)
^            ^                 ^^

Inside the zero monad
({}<({}{})>{}) -> ({}({}{}))
    ^    ^ ^^

Inside a loop
{({}{})([{}])} -> {([{}{}])}
 ^    ^  ^^

Stack height pushed
([][]())({}()) -> ([][]()())
^      ^ ^^

Loop result pushed
({({}[()])}{})(({})) -> (({({}[()])}{}))
^            ^  ^^

Two redundancies
({}<({}{})>)({}{}) -> ({}{}{})
^   ^    ^ ^ ^^^^

Discovered redundancy
(({})){}({}()) -> ({}())
^^  ^^^^ ^^

Chained redundancy
(<(()()())>)(({}){}{}({})) -> (()()()({}))
  ^      ^         ^^

No redundancy (output should be the same as input):

-empty string-
(({}<>)({}()))         - unlike the second test case, the pushed value is used again
(({}){})               - standard code for doubling the top value on the stack
({}{})<>{}             - push and pop not on same stack
(()){{}{}}             - loop starts between push and pop
({(({}[()]))}{})([]{}) - stack height is used after push

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.