9
\$\begingroup\$

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.

Rules

  • 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
\$\endgroup\$

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.