Tips for Golfing in Brain-Flak

Question

Brain-flak is a stack-based turing-tarpit language, written collaboratively between me, DJMcMayhem, and 1000000000.

Some users are very experienced in the mysterious ways of Brain-Flak. So I thought it a good idea to set up this question as a way for us, and hopefully others too, to share our knowledge with the community and lower the bar of entry to this language "designed to be painful to use". And perhaps even teach those of us with more experience some new tricks.

So what tips do you have for golfing in brain-flak? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to brain-flak (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Answer 1

Use the Third Stack

If you have read the title you might be a bit confused. Surely there are only two stacks in Brain-Flak? However I assure you that it exists and it is one of the most powerful if not the most powerful tool in writing and golfing Brain-Flak.

---

What is the "Third Stack"?

Every Brain-Flak program uses the third stack in one way or another but most of the use goes on behind the scenes and it is often useful to simply ignore the fact that it exists. Each parenthesis in the program either adds or removes one item from the stack. Three of the open braces ([< all add an item to the stack while their three conjugates )]> all remove an item from the stack. The value of the item on the stack is the value of the current scope of the program and using nilads will modify this value in certain ways. The close parenthesis ) has the unique function of moving an element from the Third Stack to the current stack; a push.

Hopefully this is becoming clear to you. The Third Stack is some sort of stack that remembers the return values of code that has already been executed. Let's walk through an example of a simple program keeping track of the two normal stacks and the Third Stack.

Example

We will walk through the following program. This program pushes -3, 1, -2 to the stack.

(([()()()])(()))

We start with three open braces, which all push a zero to the third stack.

Our stacks now look like this, the Third Stack is the one on the right and the active stack has a ^ under it:

        0
        0
  0  0  0
  ^

(([()()()])(()))
   ^

Now we have three () nilads. These do not do anything to the normal two stacks, however they do each add one to the top of the Third Stack making our stacks look like:

        3
        0
  0  0  0
  ^

(([()()()])(()))
         ^

Now we encounter a ] as stated before close braces remove an item from the Third Stack, but ] has the function of subtracting the element it removes from the top of the stack. Thus our new stacks will look like:

       -3
  0  0  0
  ^

(([()()()])(()))
          ^

This makes sense; [...] does negation so ] should subtract downwards.

Now we must execute a ). As you likely recall ) is the place in the program where stuff gets pushed to the stack so we will be moving the top of the Third Stack to the current stack, in addition we will be adding the -3 to the next element in the third stack.

 -3  0 -3
  ^

(([()()()])(()))
           ^

Once again we encounter one of our three open braces so we will add another element to our Third Stack.

        0
 -3  0 -3
  ^

(([()()()])(()))
            ^

As we said earlier () will increment the top of our third stack by one.

        1
 -3  0 -3
  ^

(([()()()])(()))
              ^

And ) will move the top of the Third Stack onto the active stack and add downwards

  1
 -3  0 -2
  ^

(([()()()])(()))
               ^

The last ) moves the Third Stack onto the active stack and since there are no elements left on the Third Stack for it to add, does nothing else.

 -2
  1
 -3  0
  ^

(([()()()])(()))
                ^

The program is over so we terminate and output.

---

This example is intended to give you a feel for what the Third Stack is and does. It does not include all of the operations, but hopefully you can figure out what each of them does on its own. If you are still struggling I have included a "cheatsheet" at the bottom of this answer to help you along.

Ok, So what?

Ok, now you understand the Third Stack, but "So what"? You were already using it even if you didn't call it the "Third Stack", how does thinking in terms of the Third Stack help you golf?

Lets look at a problem. You want to take the Triangle of a number. This is the sum of all numbers less than n.

One approach might be to create an accumulator on the offstack and add to it as you count down. This creates code that looks like this:

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

Try it Online!

This code is pretty compact and one might think that it can't get much smaller. However if we approach it from a third stack point of view it become clear that this is grossly inefficient. Instead of putting our accumulator on the offstack we can put it on the third stack with a ( and retrieve it at the end we use ). We will once again loop through all the numbers, but this time we don't have to do much of anything to increment our Third Stack, the program does it for us. This looks like:

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

Try it Online

This code is less than half the size of the pretty well golfed version we made before. In fact a computer search has proven that this program is the shortest possible program that can perform this task. This program can be explained using the "sum of all runs" approach, but I think it is a lot more intuitive and clear when explained using a Third Stack approach.

When do I use the Third Stack?

Ideally whenever you begin work on a new problem in Brain-Flak you should think to yourself how would I do this with the Third Stack in mind. However as a general rule of thumb whenever you have to keep track of some type of accumulator or have a running total it is a good idea to try putting that on your third stack instead of the two real stacks.

Another time that it might be a good idea to consider using your third stack is when you don't have any space to store some value on the other two stacks. This can be particularly useful when you are doing manipulations on two existing stacks and you want to save a value for later use without having to keep track of where it is.

Limitations of the Third Stack

The Third Stack is very powerful in a lot of ways but it comes with its own limitations and drawbacks.

Firstly, the maximum stack height for the Third Stack at any given point is determined at compile time. This means that if you want to use an amount of space on the stack you have to allocate that space when you are writing the program.

Secondly the Third Stack is not Random Access. This means that you cannot perform any operations on any value but the top most value. In addition you cannot move values around on the stack (say swap the first two elements).

Conclusion

The Third Stack is a powerful tool and I would consider it essential to every Brain-Flak user. It takes some getting used to and requires a shift in the way your think about programming in Brain-Flak, but when used properly it makes all the difference between a decent and an amazing when it comes to golfing.

Cheatsheet

Here is a list of operations and how they affect the Third Stack

 Operation  |                 Action
====================================================
   (,[,<    | Put a zero on top of the Third Stack
----------------------------------------------------
     )      | Add the top of the Third Stack to the
            | second element and move it to the 
            | active stack
----------------------------------------------------
     ]      | Subtract the top of the Third Stack
            | from the second element and pop it
----------------------------------------------------
     >      | Pop the top of the Third Stack
----------------------------------------------------
     ()     | Add one to the top of the Third Stack
----------------------------------------------------
     {}     | Pop the top of the active stack and
            | add it to the top of the Third Stack
----------------------------------------------------
     []     | Add the stack height to the Third
            | Stack
----------------------------------------------------
   <>,{,}   | Nothing

Answer 2

Finding modulus/remainder

Finding n modulo m is one of the basic arithmetic operations, important for many challenges. For cases m > 0 and n >= 0, the following 46-byte snippet may be used. It assumes that n is on top of the active stack with m the next one down, and replaces them with n mod m. It leaves the rest of the stacks intact.

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

This annotated version shows the stack contents at some points in the program. ; separates the two stacks and . marks the active stack.

. n m;
({}(<>))<>
{   . m; r 0   (r = n - km)
    (({}))
    . m m; r 0
    {({}[()])<>}
    {}
}
m-n%m-1 m; . 0
{}<>([{}()]{})
. n%m;

Answer 3

Push-Pop Redundancy

This is a big one. It is also a little bit of a nuanced one.

The idea is that if you push something and then pop it without doing anything you should not have pushed it at all.

For example, if you want to move something to the offstack and then add one to it you might write the following code:

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

This can be simpler like this:

({}<>())

The first program picks up the item moves it, picks it up again and adds one, while the second one does both in one fell swoop.

That example was simple however it can get a lot more complex. Take for instance:

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

The reduction is less clear here but the 4th pop in the program can be reduced with the 2nd push, like so:

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

This is the most powerful tool in my golfing repertoire but it takes some practice to get good at it. Once you have been doing these for a while you will be able to spot these almost instantly.

Answer 4

Optimise your integers

Integers are tedious to represent in Brain-Flak. Fortunately we have a question that will help Golf a Brain-Flak Integer for you. (Note that the question is designed to push the integer to the stack, so push-pop redundancy probably applies to more realistic programs.)

Answer 5

Push extra loop counters

Frequently, you'll want to do something like

Perform X operation on every element in the stack

or

Perform X operation on every pair of adjacent elements in the stack

When the input may contain '0's, or the result of operation X may give a 0, this is really inconvenient. Because you'll need to do:

([])
{

  {}

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

}

To do X to each element, and then later

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

To reverse the array again.

Even worse, if we're operatiing on pairs of adjacent elements, we'll need to do ([][()]) in place of ([]). This is really inconvenient. Here's the trick: While you're doing X to each element, push a 1 over onto the alternate stack right above the X(element). Then, while you're reversing it, you can simply do

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

This is 8 bytes shorter, so when you factor in the extra code to push 1, you'll end up saving 4-6 bytes. For a more concrete example, compare the task of getting deltas of an array. Without this trick, you'd need:

([][()]){

    {}

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

    ([][()])

}{}{}<>

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

For 62. With this trick, you'll have

([][()]){

    {}

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

    ([][()])

}{}{}<>

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

For 58. If used the right way (for example, reversing first, and removing two ([][()]) from later), this could save even more in speficic scenarios.

Answer 6

Take advantage of the 'Stack-Height' nilad

Especially in kolmogorov-complexity challenges, or challenges where you always know the size of the input, you can take advantage of the 'Stack-Height' nilad [] to create integers.

Let's work through this with a hypothetical challenge: output CAT. The non-golfy way is to use the online integer golfer to push 67, 65, and 84. This gives:

(((((()()()()){}){}){}()){}())

(((((()()()()){}){}){}){}())

((((((()()()){}()){}){})){}{})

(Newlines for clarity). This is 88 bytes, and not that great. If we instead push the consecutive differences between values, we can save a lot. So we wrap the first number in a push call, and subtract 2:

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

Then, we take this code, wrap it in a push call, and add 19 to the end:

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

This is 62 bytes, for a whopping 26 byte golf!

Now here is where we get to take advantage of the stack-height nilad. By the time we start pushing 19, we know that there are already 2 items on the stack, so [] will evaluate to 2. We can use this to create a 19 in fewer bytes. The obvious way is to change the inner ()()() to ()[]. This only saves two bytes though. With some more tinkering, it turns out we can push 19 with

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

This saves us 6 bytes. Now we are down to 56.

You can see this tip being used very effectively on these answers:

• Hello World V1

• Hello World V2

• Magic The Gathering, Friend or Foe

• Output The Missing Integer

• Diagonal Alphabet (my personal favorite)

Answer 7

Use the wiki

We have a wiki! It has some short comings, but it is helpful resource. It has lists of useful, well golfed, stack clean programs that you can paste into your code. If you want to do something you think someone might have done before there is a good chance it is on the wiki.

Answer 8

Better looping

Here's an easy one:

A fairly common construct is:

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

Where you want to loop n times but still keep the n. However this can be written as:

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

to save 2 bytes.

Another fairly common paradigm is

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

Which will loop and accumulate the entire stack. Due to some fancy maths this is the same as:

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

Answer 9

Check your negatives

Sometimes you can golf a few bytes by strategically choosing what to negate with the [...] monad.

A simple example is in nested [...]s. For example [()()()[()()]] could just be [()()()]()()

Say you want to check whether a value is any of the start brackets (<{[. The initial attempt is to push the difference between each character and loop over subtracting it

({}<(((((       #Push the differences between start bracket characters
(((()()()()){}){}){})   #Push 32
[()])                   #Push 31
[((()()())()){}{}])     #Push 20
){})><>)                #Push 40
<>({<(([{}]<>{}))>(){[()](<{}>)}<>})

However, you can save 4bytes by pushing the negative versions of the differences instead!

({}<(((((       #Push the differences between start bracket characters
((([()()()()]){}){}){}) #Push -32
())                     #Push -31
((()()())()){}{})       #Push -20
){})><>)                #Push -40
<>({<(({}<>{}))>(){[()](<{}>)}<>})

Generally, this doesn't save you very much, but it also costs very little effort to change around what the [...] is surrounding. Be on the lookout for situations where you can push the negative of a counter instead of the positive to save on incrementing multiple times instead of decrementing later. Or swapping out (a[b]) with ([a]b) to make the difference between two numbers negative instead of positive.