Skip to main content
nicuveo u/nicuveo avatar

Antoine Leblanc

u/nicuveo

Feed options
Hot
New
Top
View
Card
Compact

[2024 Day 7 (Part 1)] [Brainfuck] A step by step guide to Brainfuck

Hey everyone! For the last few years i've been doing a few days of the advent of code in brainfuck, as a challenge. You might remember my 2022 day 09 part 1 deep dive for instance. I am back this year, and so far i've managed to get days 2, 3, 7, and 14 working in Brainfuck. But 7 was by far the biggest challenge, so i thought i'd write this deep dive, in an attempt to show how to approach a problem in such a restrictive language. :)

Tl;dr: brainfuck is fun! And no problem is unsolvable if approached step by step. You can find my solutions on github and watch me do day 7 live on twitch.

But what is Brainfuck?

Ok, yeah, i guess i should start by explaining that. Brainfuck is a minimalistic esoteric programming language. A brainfuck program has access to a "tape" of memory (in practice: a big static array of pre-allocated memory), and there are only eight instructions:

  • >: move to the next cell in the memory (the next byte in most implementations)

  • <: move to the previous cell in the memory

  • +: increase the value of the current cell by one

  • -: decrease the value of the current cell by one

  • [: if the current cell is 0, jump to the closing ]

  • ]: if the current cell is not 0, jump back to the opening [

  • ,: read one byte from the standard input

  • .: write one byte to the standard output

And that's it. And that's enough.

So... how do you do anything with it? Well, the only method of control flow is the "loop", the brackets: the only thing you can test is whether a cell is 0 or not. So, if your tape contains two numbers a and b:

[ a, b ]
     ^

To add them together, you can do something like this:

[    while the current cell (b) is not 0
-    decrease b by one
<    move back to a
+    increase a by one
>    move back to b
]

You end up with:

[ a+b, 0 ]
       ^

But, as you can see, that operation is destructive: a and b no longer exist. So, if you want to compute their sum while keeping a copy of them, you have to duplicate them. Since non-brainfuck symbols are considered comments, the following code is valid: i'll use the notation a : ~b~ : c to represent the program's memory, with ~ indicating our current position. In other snippets that are not raw brainfuck, i'll go back to the [ a, b, c ] notation.

we have `a : ~b~`

[        while the current cell (b) is not 0
-        decrease b by one
>        move one cell to the right
+        increase it by one
>        move one cell to the right
+        increase it by one
<<       move back to b
]

we have now copied b twice in the two cells on its right:
we have `a : ~0~ : b : b`

>>       move to the second copy of b
[        while it's not empty
-<<+>>   move the value back to where b was
]

we're now at `a : b : b : ~0~`

<<<      move back to a
[        while a is not 0
-        decrease a by one
>>+      increase the third cell by one
>+       increase its neighbour by one
<<<      move back to a
]

we're now at `~0~ : b : a+b : a`
the only thing to do is to move a back where it was

>>>
[-<<<+>>>]
<

and at last we have `a : b : ~a+b~`

Or, in short:

[->+>+<<] >> [-<<+>>] <<< [->>+>+<<<] >>> [-<<<+>>>] <

Now let's solve some advent of code with this!

I am a fraud and a hack

Bit of an exaggeration, but, yes, before i start deep-diving into my solution for day 7 part 1, two important disclaimers. First, i cheat a bit. Brainfuck doesn't have functions, obviously, so i have a big library of snippets to copy and paste for whenever i want to do something non-trivial, like, for instance, multiplying two 32-bit integers. I wrote it once, and i now just use the snippet. And, a few years ago, i went a bit further, and i wrote my own transpiler, witch can inline said snippets automatically for me. So, while i did write all of the brainfuck in the solution, i wrote most of it only once. I think you'll agree that being able to rewrite the previous example as dup2 add is a lot more convenient.

The second big disclaimer is that i have only implemented numeric operations on 32 bit ints, that only require four cells in memory. I do have a snippet for 64 bit int addition, but no multiplication or comparison or even printing to the output. And as as result... my solution for day 7 only works on inputs in which each line total fits within an int32. Fixing this by implementing proper int64 multiplication and comparison in brainfuck is left as an exercise to the reader for future me.

What makes day 7 so challenging

The big challenge with AOC problems is that it's very difficult to work with dynamic amounts of data, in Brainfuck. For instance, imagine tackling day 1: you'd need to read both lists in memory to be able to determine the minimum of each. But, unless you hardcode the size of the lists... How do you something as basic as "going to the first element of the list"? You'd need to string the correct number of < or >. Unless you know for sure that neither list contains a 0, you can't use [] to test where you are in memory. If you find the first element, then... to do anything with it, you need free memory on the side to be able to copy it before analyzing it...

To summarize: the memory isn't random access. You have to keep track of where you are in it, and there's no "other" memory you can use for that purpose, there's no "stack pointer" you can manipulate. So, any program that needs to navigate dynamically sized memory needs to make use of "sentinel" values to be able to figure out where it is...

That's why problems like day 3, which can be tackled one character at a time and don't require reading all the input ahead of time are a LOT easier to deal with. In my experience, the easiest way to deal with memory, is to use the buffer like a stack: push values by moving right in the buffer and use the unused space further to the right as temporary buffer. It's fine while we only have simple values.

For day 7, we have to maintain two lists for each line. Two lists of dynamically changing size. It's fine. It's fiiine. I'm fine. It's fi-

Reading numbers

So, how do we approch solving day 7? Line by line, obviously. We reserve some space at the "bottom of the stack", i.e. the leftmost part of the memory, for the accumulated total, and we write the code for each line in a loop. As long as each line doesn't touch that part of the memory, and just updates it accordingly, then we're fine.

For each line, the easiest approach is to do treat each number one by one: given a list of all possible values so far, and given the next number of the list, we create a new updated list of numbers. When that's done, we compare each element with the expected total. If any of them did match, we add the total of the line to our reserved grand total. But that's easier said than done... The biggest challenge is keeping track of the two lists.

But let's process step by step. Since i'm using my snippets, i can write "functions" that will be inlined. We can start by dealing with a simple process: how do we parse numbers from the input? First, we need to be able to decide if a number is a digit. To do so, we can simply apply 48 - to a character we read from the input; that's the ASCII value of '0'. It is then enough to "just" check if the resulting byte is less than ten.

In my higher-level language:

def is_digit() [C] -> [C,B]
  dec('0')
  ltc_(10)
}

In raw Brainfuck:

decrease the cell by 48
------------------------------------------------
duplicate the cell
[->+>+<<]>>[<<+>>-]
push a 10 on top of the stack
++++++++++
swap them
>[-]+[-<[->>+<<]<[->+<]>>>[-<<<+>>>]<]
check that the top byte is less than the second one
[                              while that top byte is not 0
  <[->>+>+<<<]>>>[-<<<+>>>]<   duplicate the second byte
  [>+<[-]]+>[-<->]<            check whether that second byte is 0
  [-<[-]+<+>>]<<               if it is set both bytes to 1
  ->-                          decrease both bytes by one
]<
now we are back on what was the second byte (the 10)
it is now non-zero only if the digit was strictly less than 10
we make that cell a "boolean" (0 or 1)
[>+<[-]]>[-<+>]<

Now, you'll notice that this isn't optimal: the price of using macros is that ltc_(10) is translated as dupc pushc(x) gtc, which gtc itself being translated as swapc ltc, for a very simple reason: i have manually implemented ltc, i haven't implemented gtc. :)

With this, we can now parse one individual number from the input.

In my higher-level language:

def impure read_number() [] -> [I,B] {
  pushi(0)               // add four bytes of 0 to the stack
  push_read              // push one character from the input to the stack
  while (is_digit) {     // while our previously defined is_digit returns yes
    c_to_i               // convert that digit to an int
    swapi                // swap new digit with previous total
    pushi(10)            // push a 10 to the stack
    muli                 // multiply the old total by this 10
    addi                 // add the two ints
    push_read            // read the new character from the input
  }
  inc('0')               // increase the character back by 48
  pushc(' ')             // push a 32
  eqc                    // compare the two
}                        // returns the number and a boolean to indicate if we ended on a space

In raw brainfuck... this includes an integer multiplication and an integer addition, so:

pushi(0)
>[-]>[-]>[-]>[-]

push_read
>,

is_digit
------------------------------------------------[->+>+<<]>>[-<<+>>]<>[-]+++
+++++++>[-]+[-<[->>+<<]<[->+<]>>>[-<<<+>>>]<]<[<[->>+>+<<<]>>>[-<<<+>>>]<[>
+<[-]]+>[-<->]<[-<[-]+<+>>]<<->-]<[>+<[-]]>[-<+>]<

while
[[-]<

c_to_i
[>>>+<<<-]>>>

swapi
>[-]++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<] <[->+<]<[->+<]<[->+<]>>>>>>
>>>[-<<<<<<<<<+>>>>>>>>>]<]<

pushi(10)
>[-]>[-]>[-]>[-]++++++++++

muli
>[-]++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>>
>>[-<<<<<<<<<+>>>>>>>>>]<]<>[-]>[-]>[-]>[-]++++++++++<<<<<<<[->>>>>>>>+>+<<
<<<<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>
>>>>[-<<<<<<<<<+>>>>>>>>>]<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>>>>>[-<<<<<<<
<<+>>>>>>>>>]<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]
<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<<<<<<<<[->>>
>>>>>+>+<<<<<<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<<<<<<<<[->>>>>>>>+>+<<<<<
<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>>>>
>[-<<<<<<<<<+>>>>>>>>>]<>[-]++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->
+<]<[->+<]<[->+<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<]<[->>+<<]<<<<[->>>>>>[->+
>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<
<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>
>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-
<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>
>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<
<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>-<<<<<<]>>>>>>[-<<<<<<+>>
>>>>]<[-]<<[-]<[-]<[-]<>[-]++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++>[-]+[-<[->>+<<]<[->+<]>>>[-<<<+>>>]<]<[<[->>+>+<<<]>>>[-<<<+>>>]<[>+<
[-]]+>[-<->]<[-<[-]+<+>>]<<->-]<[>+<[-]]>[-<+>]<[>+<[-]]+>[-<->]<[[-]<>[-]+
+++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>>>>[-<
<<<<<<<<+>>>>>>>>>]<]<>[-]]<>[-]>[-]>[-]>[-]>[-]++++++++[-<[->>+<<]<[->+<]<
[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>
>>>>>>>[-<<<<<<<<<<<<<+>>>>>>>>>>>>>]<]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>
>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>
>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<>[-]>[-]>[-]>[-][->>+<<]<<<<[->>>
>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+
>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->
>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<
<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[
-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]
<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<
<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>-<<<<<<]>>>>>>[-<<
<<<<+>>>>>>]<[-]<<[[-]>+<]<[[-]>>+<<]<[[-]>>>+<<<]<[[-]>>>>+<<<<]>>>>[[-]<<
<<+>>>>]<<<<[[-]<>[-]++++++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]
<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>>>>>>>>[-<<<<<<<<<<<<<+>>>>
>>>>>>>>>]<]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[
-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>
[-<<<<<+>>>>>]<>[-]++++++++++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+
<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>
>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>]<]<<<<<[->>>>>>+<<<<<<]
>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<<<]>>[-<<<<<<+>>>
>>>]<<<<<<<[->>>>>>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<<<<<<<
]>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<<<]>>[-<<<<<<+>>
>>>>]<<<<<<<[->>>>>>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<<<<<<
<]>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<<<]>>[-<<<<<<+>
>>>>>]<<<<<<<[->>>>>>+<<<<<<]>>>>[->>+<<]>>[-<<<<<<+>>>>>>]<<<>[-]++++++++[
-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[
->+<]<[->+<]>>>>>>>>>>>>>[-<<<<<<<<<<<<<+>>>>>>>>>>>>>]<]<>[-]>[-]>[-]>[-]+
>[-]++++[-<[->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>>
>>[-<<<<<<<<<+>>>>>>>>>]<]<[->>+<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]
+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>
+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>
>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-
]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<
[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<
<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[
-<<->>][-]<<<]<<<<[->>>>>>-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[-]<<<<<[->>>>+>+<
<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+
<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<>[-]>[-]>[-
]>[-][->>+<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-
<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[
>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-
<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->
+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<
<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-
<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>
>>>>-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[-]<<[[-]>+<]<[[-]>>+<<]<[[-]>>>+<<<]<[[
-]>>>>+<<<<]>>>>[[-]<<<<+>>>>]<<<<]<>[-]++++++++[-<[->>+<<]<[->+<]<[->+<]<[
->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>>>>>>>>>>>>>[
-<<<<<<<<<<<<<+>>>>>>>>>>>>>]<]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<

addi
<<<<[->>>>>>+<<<<<<]>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][
-]<<<]>>[-<<<<<<+>>>>>>]<<<<<<<[->>>>>>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->
]<[-<<+>>][-]<<<<<<<]>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>]
[-]<<<]>>[-<<<<<<+>>>>>>]<<<<<<<[->>>>>>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<-
>]<[-<<+>>][-]<<<<<<<]>>>>[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>
][-]<<<]>>[-<<<<<<+>>>>>>]<<<<<<<[->>>>>>+<<<<<<]>>>>[->>+<<]>>[-<<<<<<+>>>
>>>]<<<

push_read
>,

read_number
------------------------------------------------[->+>+<<]>>[-<<+>>]<>[-]+++
+++++++>[-]+[-<[->>+<<]<[->+<]>>>[-<<<+>>>]<]<[<[->>+>+<<<]>>>[-<<<+>>>]<[>
+<[-]]+>[-<->]<[-<[-]+<+>>]<<->-]<[>+<[-]]>[-<+>]<

end while
]<

inc('0')
++++++++++++++++++++++++++++++++++++++++++++++++

pushc(' ')
>[-]++++++++++++++++++++++++++++++++

eqc
<[->-<]>[-<+>]<[>+<[-]]>[-<+>]<[>+<[-]]+>[-<->]<

I think this snippet explains my use of macros: it's convenient not to have to re-type or even just copy-paste this muli. :)

Main loop

Before looking at the way we deal with each line, let's talk briefly about the overall structure of our program. We do not know how many numbers there are per line, so we can't keep track of how much of a line we've read by just decreasing some counter. Instead, you will note that read_number "outputs a boolean", it sets one cell of the memory to 0 or 1, depending on whether the character we read that broke the loop was a space or not. We use this to tell our loop code that there are more numbers to read: the end of the line will be signaled by a newline, which will not match a space, and our line function can use that to know when to wrap things up.

For convenience, we make one additional assumption: that no line total is 0. That way, if we try to read a line total, but the value we get is 0, it means we've only been reading 0, which is how Brainfuck implementations signal the end of the input.

Our structure therefore looks like this:

def impure main() {
  pushi(0)                     // grand total
  pushi(1)                     // set the "more lines to read" flag to 1
  while (nei_(0)) {            // while that flag isn't 0
    popi                       // remove said number
    process_line               // process the line (which sets the flag)
  }
  popi                         // we're done, pop the flag
  printi endl                  // print the int
}

def impure process_line() {
  read_number                  // read the line total
  popc                         // discard the "space" flag
  if (nei_(0)) {               // are we on a valid line
     ???                       // TODO
  }

The if block is implemented as such; given condition, a macro that moves one cell to the right (i.e. pushes a value to the stack), and block the content of the if block:

condition  // push the "boolean" on the stack
[          // if true
  [-]      // set it back to 0
  <        // move back to where the stack was
  block    // do the main block of the if
  >[-]     // push a 0 on stack to terminate the loop
]          // we end the block on a 0, this always exits
<          // move back to the top of the stack

The while block is implemented similarly, but repeats the condition at the end of the [] loop.

Memory layout

Now, let's think about how we're gonna structure the data of a line inside our memory. When we enter the if in process line, we have this:

[ total, line ]
         ^^^^

Each of those are four bytes int (they should be eight, see disclaimer above), so in practice:

[ 0, 0, 0, 0, 0, 0, 0, 0 ]
                       ^

What we want to do, if expressed in pseudo-code, is roughly this:

reserve space for a list "new"
reserve space for a list "old"
read one number from the input, and put it in the "old" list
while the "read_number" continue flag is true:
  read a new number from the input
  update the continue flag accordingly
  while the "old" list isn't empty:
     move one value from it to the top of the stack
     compute that value added to the new number
     compute that value multiplied by the new number
     put both new numbers in the "new" list
  swap the now-empty "old" list and the "new" list
set a new "valid" boolean on top of the stack to true
while the "old" list isn't empty:
  compare the rightmost value of the list with the line total
  update the "valid" boolean by "and"ing it with the result of that comparison
multiply the line total by the "valid" boolean
add this result to the grand total

But, as discussed before, it's non-trivial to keep track of dynamic lists. Here, however, we can make an assumption: none of the numbers in the lists will ever be 0. If that's the case, we can use 0 as a delimiter in memory, allowing us to test whether we're on a 0 or not as a way to know we have reached the end of a list. Consequently, our memory layout after reading a number from the input is going to be something like this:

[ total, 0, [new list], 0, [old list], 0, line, new number, continue ]

We need to keep the line total on the "right", because we will need to compare it to the values of the list after we're done processing the line, and doing comparisons requires some free buffer space, which in our "stack" approach we have on the right.

But before we look at the implementation, one last thing:

Rolling in the deep

A series of macros we will make heavy use of is the "roll" family of macros, which rotate the values of the stack.

[ a, b, c, d, e, f, g ]
                    ^

roll4(1) // rotate by 1 the top 4 values of the stack

[ a, b, c, g, d, e, f ]
                    ^

roll5(2) // rotate by 2 the top 5 values of the stack

[ a, b, e, f, c, g, d ]
                    ^

Those allow us to easily manipulate the shape of the stack, bringing values we need to the top. From an implementation persepective, it's not too complicated: it's just a generalized swap, using one buffer cell. For instance, a rollc5(2) would be translated as:

>[-]++              // push a 2 on the stack
[                   // while that counter isn't 0
  -                 // decrease it by one
  <                 // move back to the top of the stack
  [->>+<<]          // move the top value of the stack to the first free cell on the right
  <[->+<]           // move the 2nd value to where the 1st was
  <[->+<]           // move the 3rd value to where the 2nd was
  <[->+<]           // move the 4th value to where the 3rd was
  <[->+<]           // move the 5th value to where the 4th was
  >>>>>>            // go back to the buffer cell where the 1st value is stored
  [<<<<<<+>>>>>>-]  // move it to the bottom
  <                 // go back to the counter
]<                  // and we're done!

With this out of the way, finally:

Processing the numbers

Let's start with the first loop of our pseudo-code: processing the numbers one by one.

// [ total, line ]
//          ^^^^

push_read popc     // ignore the ":" after the line total
pushi(0)           // put a first zero list delimiter on the stack
pushi(0)           // and another one
read_number        // read the first number of the list
popc               // ignore the continue flag, assuming there's gonna be more numbers
pushi(0)           // put another 0 after the first number

// [ total, line, 0, 0, first number, 0]
//                                    ^

rolli5(4)          // bring the line total to the top of the stack

// [ total, 0, 0, first number, 0, line ]
//                                 ^^^^
// which is equivalent to:
// [ total, 0, [new list], 0, [old list], 0, line ]
//                                           ^^^^

pushi(1)           // push a continue flag on the stack
while (eqi_(1)) {  // while it's a one
  popi             // pop the continue flag
  read_number      // read the new number and the new continue flag
  b_to_i           // convert the continue flag to an int for convenience

  // [ total, 0, [new list], 0, [old list], 0, line, new number, continue ]
  //                                                             ^^^^^^^^

  while (rolli5(4) nei_(0)) {
    // bring the fifth number of the stack to the top
    // if the old list isn't empty, it will bring its top value to the top
    // otherwise it brings the delimiting zero to the top
    // if non-zero, we execute this block
    // [ total, 0, [new list], 0, [old list-1], 0, line, new number, continue, old number ]
    //                                                                         ^^^^^^^^^^

    // compute the two new numbers
    dupi
    rolli4(3)
    dupi
    dupi
    rolli6(1)
    rolli3(1)
    addi
    rolli3(1)
    muli

    // [ total, 0, [new list], 0, [old list-1], 0, line, new number, continue, sum, product ]
    //                                                                              ^^^^^^^

But now comes the hard part. We have to insert those two new numbers in the new list. Which means we have to move them. But how? We can't even swap numbers without needing some buffer space? The trick i have found is to move two numbers at a time: the value we want, and a 0, so that we a buffer with us. That way, we can swap things around without destroying them, and we can even use that 0 for other purposes, such as indicating whether we've reached a 0 or not. For instance:

def impure move_left() {
  // [a, b, 0]
  //        ^
  <<<< swapi
  // [b, a, 0]
  //     ^
  [              // if the first byte of a isn't 0
    [>>>>+<<<<-] // move it four to the right
    >>+<<        // increase the THIRD byte of the 0 by 1
  ]
  >>[<<+>>-]     // move the non-zero signal to the now free least significant digit of a
  <<<            // move to the second byte of a
  [              // if it isn't 0
    [>>>>+<<<<-] // we move it four bytes to the right
    >+<          // and we increase the non-zero signal
  ]<             // then we move to the next byte
  [              // if it isn't 0
    [>>>>+<<<<-] // we move it four bytes to the right
    >>+<<        // and we increase the non-zero signal
  ]<             // we move to the next byte
  [              // if it isn't 0
    [>>>>+<<<<-] // rinse and repeat
    >>>+<<<
  ]
  >>>
  // [b, r, a]
  //     ^
  // `b` has moved left of `a`, and had carried its "0" with it
  // the least significant byte of that buffer cell now contains "true"
  // (i.e. a non-zero value) if and only if `a` is non-zero
}

This allows us to move some value b to the left until we move it past a 0. We can therefore do the following:

// [ total, 0, [new list], 0, [old list-1], 0, line, new number, continue, sum, product ]
//                                                                              ^^^^^^^

pushi(0)
rolli7(2)
// [ total, 0, [new list], 0, [old list-1], product, 0, 0, line, new number, continue, sum ]
//                                                                                     ^^^

<<<<<<<<<<<<<<<<<<<<
+ [ [-] move_left ]
// [ total, 0, [new list], product, 0, 0, [old list-1], 0, line, new number, continue, sum ]
//                                  ^

That + [ [-] move_left ] moves product and its buffer cell until said buffer is empty, indicating that we just went past a 0, meaning we've made it to the new list! product has now been succesfully added. But... now we need to move back. If we knew for a fact that all bytes in the old-list were non-zero it would be easy, but... no, we need to go back until we find a real zero, on the other side. How do we do that? Well, we have this extra 0 laying right there, and it's not like we need it here, maybe we could just...

def impure move_zero_right() {
  // [0, a]
  //  ^
  >>>>                    // move to the least significant byte of a
  [                       // if it's non-zero
    [<<<<+>>>>-]          // move it four bytes to the left
    <<<<<+>>>>>           // increase the non-zero signal (in an empty byte of the 0)
  ]
  <<<<<[->>>>>+<<<<<]     // move the signal to where we were
  >>>>                    // move to the second least significant byte of a
  [                       // if it's non-zero
    [<<<<+>>>>-]          // you know the drill by now
    >+<
  ]
  <
  [
    [<<<<+>>>>-]
    >>+<<
  ]
  <
  [
    [<<<<+>>>>-]
    >>>+<<<
  ]
  >>>
  // [a, r]
  //     ^
  // the "0" has moved to the right of `a`, and now contains "true"
  // (i.e. a non-zero value) if and only if `a` is non-zero
}

With it:

// [ total, 0, [new list], product, 0, 0, [old list-1], 0, line, new number, continue, sum ]
//                                  ^
>>>>                                // move to the next zero
+ [ [-] move_zero_right ]           // move it to the right until we hit the zero on the other side
>>>>>>>>>>>>>>>>
// [ total, 0, [new list], product, 0, [old list-1], 0, 0, line, new number, continue, sum ]
//                                                                                     ^^^

And now we can rinse and repeat for the sum:

rolli6(1)
// [ total, 0, [new list], product, 0, [old list-1], sum, 0, 0, line, new number, continue ]
//                                                                                ^^^^^^^^

<<<<<<<<<<<<<<<< + [ [-] move_left ]
// [ total, 0, [new list], product, sum, 0, 0, [old list-1], 0, line, new number, continue ]
//                                       ^

>>>> + [ [-] move_zero_right ] >>>>>>>>>>>>
// [ total, 0, [new list], product, sum, 0, [old list-1], 0, 0, line, new number, continue ]
//                                                                                ^^^^^^^^

And we're almost done! We have successfully handled the combination of one number from the old list with a new number, computing the two new possible values, and putting them in a new separate list! Now we just need to clean things up, to be able to handle the next "old" number, at the beginning of our loop.

// we had the following structure before the beginning of the loop
// [ total, 0, [new list], 0, [old list], 0, line, new number, continue ]
//                                                             ^^^^^^^^
// but we currently have:
// [ total, 0, [new list], 0, [old list], 0, 0, line, new number, continue ]
//                                                                ^^^^^^^^
// so we just need to:
rolli4(3)
popi
// loop closing bracket goes here, omitted to reduce indentation

Moving the lists

And now, when our loop exits, we have fully handled the new number! If our "old" list was [3, 4] and our new number was 2, our "old" list is now empty, and our "new" list contains [8, 6, 6, 5]. Success! Now we just need to close our bigger loop: we need to get ready to process the next number on the line.

Just a tiny problem: the "new" list needs to become "old". At a glance it might look easy:

// we have [ total, 0, [list], 0, 0, line, new number, continue ]
// we want [ total, 0, 0, [list], 0, line, continue ]

It's just moving a 0 to the left! That's easy, we can reuse our move_left snippet, or maybe make it simpler! There's one issue though... Once we've moved the zero on the other side... how do we move back? Again, if all the values in the list were one-cell wide, we could easily just use [] to test whenever we reach the zero, but they are four-cells wide, and we can't! We need a buffer cell on the way back too!

The logical conclusion is that we obviously need to move TWO zeroes to the left, so that we can have one on the way back! We just need one more function...

def impure move_two_zeroes_left() {
  // [a, 0, 0]
  //     ^
  <<<<
  [[>>>>>>>>+<<<<<<<<-]>+<]<
  [[>>>>>>>>+<<<<<<<<-]>>+<<]<
  [[>>>>>>>>+<<<<<<<<-]>>>+<<<]<
  [[>>>>>>>>+<<<<<<<<-]>>>>+<<<<]
  >>>>[-<+>]<
  // [r, 0, a]
  //  ^
}

At this point that last one should feel perfectly readable i'm sure!

So now, we're out of the "old list" loop: that means that the number we tried to get out of it was a 0. That means we have:

// [ total, 0, [list], 0, line, new number, continue, 0 ]
//                                                    ^

popi
swapi
popi
// [ total, 0, [list], 0, line, continue ]
//                              ^^^^^^^^

pushi(0)
pushi(0)
rolli5(2)
// [ total, 0, [list], 0, 0, 0, line, continue ]
//                                    ^^^^^^^^

<<<<<<<<<<<<<<<< + [ [-] move_two_zeroes_left ]
// [ total, 0, 0, 0, [list], 0, line, continue ]
//          ^

>>>>>>>> + [ [-] move_zero_right ] >>>>>>>>
// [ total, 0, 0, [list], 0, 0, line, continue ]
//                                    ^^^^^^^^

rolli3(2)
popi
// [ total, 0, 0, [list], 0, line, continue ]
//                                 ^^^^^^^^

AND FINALLY WE'RE DONE. We now just need to do one last thing...

Reducing the line

When continue is 0, we exit our line loop: there are no more digits to process. The only thing left to do is to decide whether any of the numbers in the list matches the line total. It doesn't matter in this case that the operations are destructive: the list has served its purpose, and doesn't need to survive this part of the process. No need for inline brainfuck, we can deal with this purely with macros.

// when we exit the loop, it means continue was 0
// [ total, 0, 0, [list], 0, line, continue ]
//                                 ^^^^^^^^

popi
// [ total, 0, 0, [list], 0, line ]
//                           ^^^^

// we use the 0 as our accumulator, that will be increased by one
// every time a number in the list is equal to the line total
// [ total, 0, 0, [list], accum, line ]
//                               ^^^^

// this puts the first number of the list on the top of the stack
// and loops while that isn't a 0
while (rolli3(2) nei_(0)) {
  // [ total, 0, 0, [list], accum, line, candidate ]
  //                                     ^^^^^^^^^

  // duplicate the two numbers, compare them, make the result into an int32
  dupi2 eqi b_to_i
  // [ total, 0, 0, [list], accum, line, candidate, is same ]
  //                                                ^^^^^^^

  // add the result to the accumulator and discard what we don't need
  rolli4(3) addi rolli3(1) popi
  // [ total, 0, 0, [list], accum, line ]
  //                               ^^^^
}

When that loop is done, it means we've compared all the numbers. We simply transform our accumulator into a "boolean", 0 or 1, we multiply it to the line total, and we finally add it to the grand total. When that's done, we just push a continue flag on the stack like the main loop expects, and... we're done!

// [ total , 0 , accum , line , 0 ]
//                              ^
popi
swapi
i_to_b b_to_i
// [ total , 0 , line , accum (0 or 1) ]
//                      ^^^^^
muli
swapi
popi
// [ total , line result ]
//           ^^^^^^^^^^^
addi
pushi(1)
// [ total , 1 ]
//           ^

Conclusion

This is again what main looks like, once completed:

def impure main() {
  pushi(0)                     // grand total
  pushi(1)                     // set the "more lines to read" flag to 1
  while (nei_(0)) {            // while that flag isn't 0
    popi                       // remove said number
    process_line               // process the line (which sets the flag)
  }
  popi                         // we're done, pop the flag
  printi endl                  // print the int
}

And that's it. We're done! printi, like muli, is... quite monstrous, and something i just re-use. It's also out of scope for this already lengthy deep-dive. It is left as an additional exercise to the reader!

My goal with this was to demonstrate that Brainfuck isn't impossible to write: like with everything else, complicated results can be achieved by just doing things step by step, and in increasing order of complexity: first we figure out how to add two numbers together, then we figure out how to move in the memory of the program, and then... things start to click together! I know the formatting here flattens the loops, so i know it might not be the most readable... I hope it was interesting nonetheless! Thank you for reading. :)


The Monad Problem
The Monad Problem

[2022 Day 09 part 1][Brainf*ck] a detailed explanation

Ok, this is my last one. The resulting file is monstrous: 296261 instructions, that took six and a half hours to run after compiled by an optimizing compiler, and i had to tune the compiler's option for it not to segfault... Turns out bubble-sorting 11k+ elements in brainf*ck is slow, who would have thought? :D

Since this is (probably) my last attempt at solving something with brainf*ck for the year, i thought i'd write a quick something about how i wrote this monstrosity, and how to write brainf*ck programs in general.

Structure

Our program is made of three parts: first, we have to iterate over the list of instructions, and create a list of points in memory that represents all the places the tail of the rope has been. To deduplicate them, the simplest solution is to then sort them, and then traverse the list while keeping a counter of how many different items we encounter.

The main reason why we have to do things in distinct phases like this (instead of inserting each point into a set as we execute the instructions and then returning the size of the set) is because of two major constraints of our language:

  • operations are destructive: the only way to do some kind of if is with [, the "start of loop" instruction, that skips to the end of the loop if the current cell is 0; meaning that any kind of test must alter (or at least first duplicate) the data it is operating on

  • there's no arbitrary indexing of the data: all your data layout must take into account the fact that you will need temporary buffers alongside it

Finding all the points

Main loop

This was, surprisingly, the easiest part of this. At the core of it is a loop over the input, that we will process line by line. Stripped of everything else, that loop looks something like this:

,[
  stuff goes here
,] 

, is the operation that reads one character from the input and sets the current cell to its value. If it fails to read (if we have encountered an EOF for instance), it will set the cell to 0. So, here, we read a character before entering the loop, and before finishing it. This means this loop will continue until we read an EOF. If, in the body of it, we read everything up to and including the newline, then this loop will execute its body once per line of the input.

Decoding the instruction

When we enter the loop's body, our cursor is on a cell that contains the first character of the line: either L, R, U, or D. We are going to need to branch based on which character it is. To do so, we are going to need to find a way to have a cell that contains something different from 0 for each character we want to identify. The easiest solution is to do something like dec('D') not: decrease the cell by the value of the character D, and then invert the value of the cell:

decrease by 'D': "dec(D)"
--------------------------------------------------------------------
cell is now 0 if it contained 'D' before

invert its value: "not"
assuming the next cell to the right is 0 set it to 1 and come back
>+<   
[ if the cell is not 0
  >-< set the next cell to 0
  [-] set the current cell to 0 so that the loop ends immediately
]
if our current cell was 0 the loop didn't go and next cell is 1
if our current cell was not 0 it did and the next cell is 0
copy the result back
>[-<+>]<

The problem is that this, again, destroyed the original character from the input: we can't compare it with 'R' or 'U' or anything else now. So we need to first duplicate it before doing this test:

duplicate a cell ("dupc") assuming two empty cells to the right
[ until it's zero
  -  decrease it by 1
  >+ increase the next cell
  >+ and the one after
  << and go back to our current cell
]
now both cells to the right contain our original value:
we can move the second one back to where our value started
>>
[ until the second copy is zero
  -   decrease it by 1
  <<+ increase the original cell
  >>  come back
]
< reset the cursor to the newly created copy

With that we have everything we need to do our branching! I'll be using the name of macros we have already introduced instead of inlining them to keep this concise:

,[
  // test if R
  dupc // duplicate the current cell
  dec('R') not // make the new cell 1 if the original was R
  [ // if this new cell is 1
    [-] // set it to 0 so that this loop is an if
    // do something with the rest of the line
  ]
  < // go back to the cell where the instruction is

  // test if L
  dupc dec('L') not [ [-]
    // handle L here
  ]<

  // test if U
  dupc dec('U') not [ [-]
  ]<

  // test if D
  dupc dec('D') not [ [-]
  ]<
,]

Reading the instruction count

I'll focus on only one of the four branches, since they're all basically the same (which is part of the reason why the resulting code is so big). Our first challenge is going to be reading the argument to the direction: an integer. In practice, my program uses my macros to represent that value as a 4-cells 32-bit integer, but for the purpose of this let's use a single cell (which, in practice, is enough; i could probably simplify my program).

The core of our loop is going to be: multiply our accumulator by ten, and add the value of the current character: repeat until we encounter a newline.

// leave an empty cell for our accumulator
>
// skip the white space between instruction and number
,
// read the first character of our number
// and loop while it's not a newline
, dupc dec('\n') not
[ [-]<
  // we are now on the character we just read
  // our accumulator is one cell to the left
  // we swap them ("swapc")
  // "swapc" is just a convenient alias for "rollc2(1)":
  // roll the two top 2 characters by 1
  [->+<]<   // copy current to next
  [->+<]>>  // copy previous to current
  [-<<+>>]< // copy next to previous

  // we now have the accumulator in the current cell
  // and the current digit in the previous
  // multiply the accumulator by ten
  > ++++++++++ mulc
  // then add those two together back in the previous cell
  [-<+>]

  // the current cell is now 0, the result is in our accumulator    
  // read and test next character at end of loop
  , dupc dec('\n') not
]<

I'm not gonna inline mulc here, but, in short: while the second character is not empty, decrease it and add the first one to an accumulator. After this loop, we have consumed the entire input line up to and including the newline character, and our current cell contains the argument of our command!

Updating the head

Now, we can loop over our argument, and apply our current instruction (let's say 'R'). The loop itself is fairly straightforward:

// while the argument to R is not 0
[
  // decrease it by 1
  -
  // copy it far away to free some local memory
  [->>>>>>>>>>+<<<<<<<<<<]
  // do the thing
  // copy the argument back
  >>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<
]

For the purpose of keeping track of the head and tail of the rope, we will use the 16 previous cells of the memory: we use a 32-bit integer for each of head x, head y, tail x, tail y. In practice, all coordinates will fit into 16-bit integers, but i only have macros for 32-bit integers; this part of the code isn't slow, so the slight overhead is not a big issue. To avoid having negative coordinates, we will assume the starting point is some big enough value; i used (500, 500), which is why my transpiled program starts with four pushi(500). So, when we have to process an instruction, our memory tape looks like this:

00: 00 // head x (highest byte)
01: 00 // head x
02: 01 // head x
03: f4 // head x (lowest byte)
04: 00 // head y (highest byte)
05: 00 // head y
06: 01 // head y
07: f4 // head y (lowest byte)
08: 00 // tail x (highest byte)
09: 00 // tail x
0a: 01 // tail x
0b: f4 // tail x (lowest byte)
0c: 00 // tail y (highest byte)
0d: 00 // tail y
0e: 01 // tail y
0f: f4 // tail y (lowest byte) <-- we are here
...
1?: ?? // somewhere further in the tape: the arg counter we moved away

Since we're processing a R instruction, we need to increase the 'x' coordinate of the head by 1. The problem is that adding 1 to a 32-bit integer requires some available buffer, and our four int32s are tightly packed; in practice we know that the two highest bytes are gonna be 0, so we could use that, but for the sake of correctness, let's do this the hard way: we're gonna roll the stack, like most stack-based programming languages do:

rollc(16,12)
pushi(1) addi
rollc(16, 4)

rollc(16,12) will rotate all 16 previous cells by 12: one by one, we will move the previous cells of the memory so that [head x, head y, tail x, tail y] becomes [head y, tail x, tail y, head x] (in practice, it's a bunch of <[->+<], moving cells to the next one). We then add a 1 to the stack (>>>>+) and then add those two int32s together (i'm not gonna inline it here: what makes it complicated is detecting overflow on each byte so that we can do bit carry properly; it's implemented here). When that's done, we re-roll the stack again to restore the stack to its previous order.

Updating the tail

We then need to update the tail: our stack is now the same as described in the previous section, but the head has been updated to reflect the current command. Likewise, i'm not going to inline every macro, since int32 macros are quite large, but the logic of thinking of the tape as a stack is the key, here.

First, we need to check the distance between the head and the tail:

// first, duplicate all four top bytes so that we can transform
// them without destroying the ones we keep across loops 
dupi4
// state of the stack: [hx, hy, tx, ty]
swapi
// [hx, hy, ty, tx]
rolli3(1)
// [hx, tx, hy, ty]
subi abs // absolute value of the difference
// [hx, tx, dy]
rolli3(1)
// [dy, hx, tx]
subi abs // absolute value of the difference
// [dy, dx]
maxi // get the maximum value

As an example of how large this can get: abs is "simple"; it's:

// is the current int x less than 0?
if (lti_(0)) {
  // replace it by 0 - x
  pushi(0) subi
}

fully expanded, it becomes this:

dupi
  <<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>
  >>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[-> >>>+>+<<<<<]>>>>>[-
  <<<<<+>>>>>]<
pushi(0)
  >[-]>[-]>[-]>[-]
swapi
  >[-]++++[-<[ ->>+<<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]<[->+<]>
  >>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<]<
lti
  subi
    [->>+<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]
    <-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[
    -<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+
    >>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<
    -]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]
    <<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<
    <<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+
    >>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>-<<<<<<]>>>>>>[-<<<<
    <<+>>>>>>]<[-]<<
  compare highest byte against 128 (sign bit)
    [-]<[-]<[-]<>[-]++++++++++++++++++++++++++++++++++++++++++++++++++++
    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    ++++++++>[-]+[-<[->>+<<]<[->+<]>>>[-<<<+>>>]<]<[<[->>+>+<<<]>>>[-<<<
    +>>>]<[>+<[-]]+>[-<->]<[-<[-]+<+>>]<<->-]<[>+<[-]]>[-<+>]<[>+<[-]]+>
    [-<->]<
if not 0
[[-]<
  pushi(0)
    >[-]>[-]>[-]>[-]
  subi
    [->>+<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]
    <-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[
    -<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>[->+>+<<]>>[-<<+
    >>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<
    -]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<->>][-]
    <<<]<<<<[->>>>>>[->+>+<<]>>[-<<+>>]<[>+<[-]]+>[-<->]<[-<<+>>][-]<-<<
    <<<<]>>>>>>[-<<<<<<+>>>>>>]<[>+<-]>[-<-<+>>]<<<[->>+[->+>+<<]>>[-<<+
    >>]<[>+<[-]]+>[-<->]<[-<<->>][-]<<<]<<<<[->>>>>>-<<<<<<]>>>>>>[-<<<<
    <<+>>>>>>]<[-]<<
>[-]]<

There's a bit of duplicated work, including too many "clear" instructions ([-]) but that's an acceptable cost that comes with the simplicity of being able to write abs rather than copy-pasting this monstrosity eight times in total (twice in each branch).

Our stack now only contains a boolean on top of our data, which is the distance between the head and the tail: the maximum of the X and Y distances. What's left for us to do is to update the tail if the distance is greater than 1: in a "if", we do:

// duplicate all four bytes again so that we can modify them
dupi4
// state of the stack: [hx, hy, tx, ty, hx, hy, tx, ty]
swapi
// [hx, hy, tx, ty, hx, hy, ty, tx]
rolli3(1)
// [hx, hy, tx, ty, hx, tx, hy, ty]
// computes the signum of the diff (-1, 0, or 1)
subi signum
// [hx, hy, tx, ty, hx, tx, sy]
rolli3(1)
// [hx, hy, tx, ty, sy, hx, tx]
subi signum
// [hx, hy, tx, ty, sy, sx]
rolli4(3)
// [hx, hy, ty, sy, sx, tx]
// subtract the signum of the y coordinate of the diff
// from the tail's y coordinate
// we don't add because we computed the diff the wrong
// way around to avoid a swap
subi
// [hx, hy, ty, sy, new tx]
rolli3(1)
// [hx, hy, new tx, ty, sy]
swapi
// [hx, hy, new tx, sy, ty]
subi
// [hx, hy, new tx, new ty]

signum is also simply defined as:

if (lti_(0)) { popi pushi(-1) }
if (gti_(0)) { popi pushi( 1) }

In short, we have done the following:

follow (headx, heady) (tailx, taily) =
  let diffx = signum (tailx - headx)
      diffy = signum (taily - heady)
   in (tailx - diffx, taily - diffy)

And our stack now contains the updated version of the tail!

Saving the position

We are going to need to save each tail position as we iterate through the instructions. But we are operating on a stack of values, on top of which we always have [head x, head y, tail x, tail y]. How do we do that?

There are two tricks here: the first is to use the fact that the tail's coordinates fit into two bytes despite being stored as four bytes each. That means we can craft a four-bytes int that uniquely represents the position, by combining the two lowest bytes of the y coordinate and the two lowest bytes of the x coordinate.

// copy both ints (eight bytes)
dupi2
// move the lowest byte (1) of tail y to byte 3 of tail x
[-<<<<<<+>>>>>>]<
// move byte 2 of tail y to byte 4 of tail x
[-<<<<<<+>>>>>>]<
// pop the two remaining bytes
[-]<[-]<

So, the (500, 500) point would become 500 * 65536 + 500 = 32768500. And now, for the second trick: we're gonna send this identifier below our current stack with a simple rolli5(1):

// before: [hx, hy, tx, ty, point]
rolli5(1)
// after:  [point, hx, hy, tx, ty]

If we do this after each iteration, then our stack will grow every time:

start:   [hx, hy, tx, ty]
after R: [p0, hx, hy, tx, ty]
after R: [p0, p1, hx, hy, tx, ty]
after U: [p0, p1, p2, hx, hy, tx, ty]

Meaning that when our input loop ends, we are going to have in memory a long list of non-zero integers uniquely identifying all positions the tail has visited, bordered by 0s on each side!

Sorting the points

Now we're done with processing instructions; we have the full list of points. We now have to sort it! And the simplest possible way to do this is... good ol' bubble sort! This is the slowest part of the code: there are over 11k points; for my puzzle input, we will end doing a number of comparisons / steps which is the triangular number of points: 64133475 in the case of my input...

Our bubble sort will have an outer loop and an inner loop: the outer loop will start at the last item of the list, and will run until the last item is 0. The inner loop will traverse the list "right to left", swapping items as we go, bringing the smallest item to the bottom of the list. When we're there, we move the lowest item behind the zero at the bottom of it, so that it's "removed" from the list; we then move back all the way to the top of the list, and continue with the outer loop.

The problem is that swapping two items on the way "left" requires some free buffer to do the comparison... meaning that, on the way left, we need to temporarily move the biggest element far away to the right to free some local buffer. The body of our inner loop is therefore going to be:

// while we're on an item
while(not0) {
  // sort top two items: if the top one is lower, swap
  if (dupi2 lti) { swapi }
  // move the bigger one far away to free some local buffer
  // and go to the next item
  [->>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<]<
  [->>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<]<
  [->>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<]<
  [->>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<]<
}

This inner loop will finish when we are on the 0, meaning we've moved all the items we've encountered far away; and we now that the last one was the smallest. We can therefore copy it back and put behind the current zero:

// move back one item
>>>>
// copy the smallest item back from afar
>>>>>>>>>>>>>>>>>>>
[-<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>]<
[-<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>]<
[-<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>]<
[-<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>]>>>
<<<<<<<<<<<<<<<<<<<
// and put it behind the 0, so that it's "out"
[-<<<<+>>>>]<
[-<<<<+>>>>]<
[-<<<<+>>>>]<
[-<<<<+>>>>]>>>

Those two operations could be merged into one: i just have a separate macro for "bring the next item back".

Now we simply go all the way back up to the first element: we stop when we encounter a 0:

>>>> move_back
while(not0) {
  >>>> move_back
}
<<<<

So, in short, this is what the tape is going to look like:

[ 00 , 12 , 15 , 11 ,<15>, 00, 00 ]
start the outer loop: 15 is not 0
start the inner loop:
15 is not lower than 11, no swap
[ 00 , 12 , 15 , 11 ,<15>, 00, 00 ]
move 15 far away to free some space
[ 00 , 12 , 15 ,<11>, 00 , 00 , .... , 15 ]
rinse and repeat:
swap
[ 00 , 12 , 11 ,<15>, 00 , 00 , .... , 15 ]
move
[ 00 , 12 ,<11>, 00 , 00 , .... , 15 , 15 ]
swap & move
[ 00 ,<11>, 00 , 00 , .... , 12 , 15 , 15 ]
no swap & move
[<00>, 00 , 00 , .... , 11 , 12 , 15 , 15 ]
end of the loop "down"; move the lowest element back before the 0:
[ 00 ,<11>, 00 , 00 , .... , 12 , 15 , 15 ]
[ 11 ,<00>, 00 , 00 , .... , 12 , 15 , 15 ]
loop back "up", moving the elements back
[ 11 , 00 ,<12>, 00 , 00 , .... , 15 , 15]
[ 11 , 00 , 12 ,<15>, 00 , 00 , .... , 15]
[ 11 , 00 , 12 , 16 ,<15>, 00 , 00]
repeat the outer loop: 15 is not 0
stop when all elements behind 0
[ 11 , 12 , 15 ,<15>]

Hurray, it took 6 hours, and we have a sorted list of points!

Folding down

To compute the result, we will do a "simple" fold down: basically, comparing the values of the list pairwise, and incrementing an accumulator if they are different.

We insert the accumulator below the two top values:

pushi(0) rolli3(1)
// our stack is now:
// [ 00 , 00 , 11 , 12 , 00 , 15 ,<15>]

Then we loop until we reach the 0 at the bottom of the list:

// are the two next points different?
dupi2 nei
// [ 00 , 00 , .... , aa , yy, xx ,<bb>]

// if true: they are different!
dupb [[-]<
  // erase that boolean
  [-]<
  // [ 00 , 00 , .... , aa , yy ,<xx>]
  // erase the top value
  [-]<[-]<[-]<[-]<
  // swap the two next ints to bring the accumulator on top
  swapi
  // [ 00 , 00 , .... , yy ,<aa>]
  // increase the accumulator by 1
  pushi(1) addi
  // put the accumulator back behind the second value
  rolli3(1)
  // [ 00 , 00 , .... , aa , zz ,<yy>]
  // we were in the "true" case: push a "true" back on top
  >+
>]<

// now let's negate the boolean with a "not"
[>+<[-]]+>[-<->]<

// if it's now true, it means we didn't take the first branch
// the two numbers were the same!
dupb [[-]<
  // erase that boolean
  [-]<
  // do the same thing without increasing the counter
  [-]<[-]<[-]<[-]<
  swapi
  rolli3(1)
  >
>]<

Sone of the complexity here comes from having to keep track of the boolean: we remove it to deal with the stack, and add it back so that we can perform the "else", in essence. We also break an important rule here: the ifs are written with the assumption that we're going to be back to where we were in memory, which is why we duplicate the boolean and set it to 0: if the if body is balanced, we will be back to the cell after the boolean, now set to 0, the if will not loop, and we will return to the previous cell. Here, our body is unbalanced, and we move through the tape! It works, because we always end up setting higher cells to 0 when deleting them, meaning the if logic, even if unbalanced, does end up properly on a 0, avoiding a loop.

With our examples values, this would result in the following:

[ 00 , 00 , 11 , 12 , 00 , 15 ,<15>]
[ 00 , 00 , 11 , 00 , 12 ,<15>]
[ 00 , 00 , 01 , 11 ,<12>]
[ 00 , 02 , 00 ,<11>]
[ 03 , 00 ,<00>]

When our loop ends because we've reached a 0, our accumulator is 3: we've found how many different points there was in the list! That's our result! We're done! Hurra-

Printing the result

Oh hell no. See, the problem is that the only printing primitive is the . command, which prints one character, whose ascii code is in the current cell. There's no way to print a 4-cells signed int32 to the console. Which means... we're gonna have to do it ourselves.

I am not gonna go over the details of how to do so, because this post is already long enough, and because i already had a function just for this. The gist of this is this bit:

<[-   >>>>>>> >      >       >       >       >     >     >     + _cleanp    <<<<<<<<<<<<<<]
<[-  >>>>>>>> >      >       >       >       >   ++>+++++>++++++ _cleanp   <<<<<<<<<<<<<<<]
<[- >>>>>>>>> >      >       > ++++++>  +++++>+++++>  +++>++++++ _cleanp  <<<<<<<<<<<<<<<<]
<[->>>>>>>>>>+>++++++>+++++++>+++++++>+++++++>   ++>    +>++++++ _cleanp <<<<<<<<<<<<<<<<<]

in short; for each byte, loop until they're zero, and each time increase the display digits with the corresponding values:

  • byte 4: 1, 6, 7, 7, 7, 2, 1, 6

  • byte 3: 0, 0, 0, 6, 5, 5, 3, 6

  • byte 2: 0, 0, 0, 0, 0, 2, 5, 6

  • byte 1: 0, 0, 0, 0, 0, 0, 0, 1

the _cleanp macro does the bit carrying job on the way back: if a display digit is greater than ten, remove ten from it, and add 1 to the previous digit. In the end, we end up with a bunch of display cells, and it's enough to go over them and do a ++++++++++++++++++++++++++++++++++++++++++++++++. (increase the value by the ascii value of 0, and print).

And then... we're done.

In conclusion

Here's the source file. This is the biggest one i've ever written in that made-up language. It's the biggest and slowest brainf*ck program i've ever made. It's a monstrosity that spits in the face of god and befouls the earth by its very presence. It's my baby and i'm so proud of it.

But, jokes aside, i hope this was interesting? An exploration of how to write brainf*ck code, but also an example of how to reason when working in an extremely constrained environment like this, and how to work with stack languages like Forth.

...now i just need to get part 2 working.


Satisfactory is functionally complete - working NAND gate

I've successfully implemented a NAND gate in Satisfactory, which means it's possible (although it would be monstrous) to implement a working computer within the game. :)

The goal was simple: I wanted to build a building that, given two electricity inputs A and B, would only power an output circuit IF not both inputs have power. The challenge is that there is no electricity control logic within the game, beyond power switches. And, as far as materials go, there aren't a lot of ways to control the flow with electricity: belts don't require power, neither do splitters, programmable splitters don't have control logic that can be manipulated with electricity... The only obvious solution for flow control with electricity is horribly cumbersome: powering train stations. But there's ONE logistic building that CAN be controlled with electricity... and that's the humble water pump!

Water pumps have interesting properties: if electricity is supplied, they provide 20m headlift to the fluid in the pipe; if no electricity is supplied, they reset the headlift to 0. Additionally, they always behave like a valve, whether powered or not. That makes it easy to conditionally enable a branch: if, after a fluid splitter, there's a pump behind a 14m rising pipe, the fluid will only go through that branch if the pump provides headlift. This is where I got the initial intuition: if you build two of those "pump then 14m elevation pipe" in a row, the fluid will go through if BOTH pumps have power. This is almost an AND gate. But this was not enough, two problems remained:

  1. fluid is not electricity

  2. that's the AND part of a NAND gate, but how to do the NOT part?

Problem 1 is easily solved: if the fluid is fuel, then it can be fed to a fuel generator to generate output electricity. That means my gate needs a fuel input on top of the logic inputs, but that's similar to how a NAND gate has access to an "always on" source of power. But problem 2 took me a while. The answer turned out to be an overflow valve: a trick in pipe layout to create a lower priority branch, that is only chosen if there's nowhere else for the fluid to go. It is implemented with a simple raised pipe: the fluid will only reach the other side if the pipe first fully fills up; if another branch can consume all the incoming fluid, then the pipe won't fill up, and the branch won't be chosen.

Putting it together:

  • the building takes as input exactly 12m3/min of fuel, as measured by a valve

  • that fuel goes to a splitter:

    • one branch is an overflow, connected to the output fuel generator

    • the other branch goes through two "relays" of pump + high elevation pipe, then ends with a "ground" fuel generator, connected back to the power grid, but NOT to the output of the building.

As a result, if both pumps are powered, if both gate inputs are on, then the fuel can go through the "ground" branch, that takes priority. Since there's exactly 12m3/min of fuel going in it, it will be entirely consumed by the ground generator, and the pipe will never fill up. However, if one of the two pumps is not powered, then the overflow branch slowly fills up, and ends up powering the output generator. Mission accomplished!

If we wanted to push this further, the main issue to address would be the propagation delay: it takes a WHILE for the pipe to fill up, meaning that after disconnecting one of the two inputs, it can take up to a minute for the output to turn on. :D Furthermore, it would probably be possible to directly output the fuel in the "ground" case, rather than burning it, and cycle it back, to reduce the overall fuel consumption of a machine built out of those gates.

In practice, this probably won't be used for anything, but it was an extremely fun exercise, that surprisingly took less than three hours from original idea to screenshot! :)

Here's some screenshots showing the result, and the setup.

EDIT: I've made an updated and smaller version. I created a blueprint file for it, but I'm not sure where to upload it?

EDIT 2: blueprint link


You simply don't have what this requires. Make a note and come back later.


Come back as an adult for a hint.


Megalovania is too short, so i did the Flintstones' theme instead.


I have planned for NG+ but never executed on it: i built a vault with a large storage container for every resource (except elevator parts), all hooked to a dimensional depot, and put all the sloops and remaining mercer spheres in a chest in that vault. What i was planning to do what to use a save editor to then reset the entire map except for the vault, reset the elevator progression, and restart. Clean map, can rebuild from anywhere, but no need to go collect the artifacts again, no need to unlock recipes again, and a bunch of resources available immediately to speed up the early game.