Jan 28 2021
I seem to have a real infatuation with unconvential programming challenges. Whenever I get to do something completely new that is at the same time simple enough to take no more than a day or two, but also far enough 'out there' that just looking up the solution is out of the question, my brain really seems to light up.
So, after rewatching Tom Scott's video about the FizzBuzz interview question, I figured a fun brain teaser would be to try and implement FizzBuzz in Befunge, an esoteric programming language I am quite fond of.
Without much fanfare, here it is:
0>1+:45*5*`#@_v > v > v
^,*25< _v#!*<>::3%!!:#^_"zziF",,,,>\5%!!:#^_"zzuB",,,,v
^.:< ^ <
If you're curious how it works, and what the mental process of writing it looked like, read on!
Why: Simply put, Befunge is my favourite esoteric language. It has just the right mix of complexity, weirdness, and style for me.
What: Wikipedia tells me that "Befunge is a stack-based, reflective, esoteric programming language. It differs from conventional languages in that programs are arranged on a two-dimensional grid.". "Reflective" here means that code can inspect and modify itself, although I didn't make use of this here.
How: I used the BedroomLAN Befunge Interpreter for running and debugging the code, but any compliant interpreter should work for this.
So, let's break down the code byte by byte!
As mentioned, Befunge works on a two-dimensional grid, and we start in the top left corner, moving right.
Every instruction is exactly one character, with space being a 'no-op', meaning it does nothing. The program ends when it executes the @ instruction.
Our very first instruction is 0! In Befunge, the instructions 0 through 9 simply push their respective value onto the stack. The stack is used for all instructions that have operands. This first value we push is going to be the counter for our loop later.
The next instruction is >. Since Befunge is 2D, execution can go up, down, left, or right! The instructions ^, v, < and > are used to change direction, which is easy to remember, since they kind of look like arrows. At this point in the program we're already going right, so we can ignore this bit for now.
Next is 1, followed by +. Arithmetic in Befunge is done via the instructions +, -, *, /, and %, with / being integer division, and % being division remainder (or "modulo"). All arithmetic operations work by popping (removing from the top of the stack) two operands, applying the operation to them, and pushing (adding to the top of the stack) the result. If you know about Reverse Polish Notation, this will be quite familiar to you.
Next is :. This instruction simply duplicates the value at the top of the stack. You'll see this used a few times because operations always remove their operands from the stack.
So, at this point, our stack has two values on it, those being our counter value, twice. If you're not sure why, try stepping through 01+:@ in the interpreter and looking at the stack view.
The first thing any implementation of FizzBuzz usually does is create a loop from 1 to 100, so let's do that! But wait, if we can only push the numbers 0 to 9 onto the stack, how do we push 100?
Look at the next bit code, 45*5*. We push 4, 5, multiply those (giving us 20!), push 5, do another multiply, and ta-da! We have the value 100 on our stack
Next question, what does an if look like in Befunge?
First up, we have `. This is the 'greater than' instruction. It pops two values from the stack, and checks if the second is greater than the first, and pushes 1 (for true) or 0 (for false).
Next is #. This is an interesting one: It simply skips over the instruction that follows it, which is @, and would end our program. You'll see why this is handy in a second.
Then we have _. This is our version of the if keyword you have in most conventional languages. It goes like this: Pop a value off the stack. If it's 0, go right, otherwise, go left. So, all together this acts like we wrote if (counter > 100) { exit(); } else { ... }!
Next we go down, then immediately right. This brings us to this imposing hunk of code:
v > v > v
>::3%!!:#^_"zziF",,,,>\5%!!:#^_"zzuB",,,,v
This is where the main logic of our FizzBuzz lies. Let's go through it step by step:
::. Duplicate the top of the stack twice, which right now is our counter value.3%. Push 3, and calculate the remainder.!!. This is a trick you might've seen if you do a lot of programming in C.!is the logical NOT operator. It pops a value from the stack, and if it is 0, pushes 1, if it is any other value, pushes 0. Negating a value twice like this essentially converts it to a boolean for us.:#^_. This is similar to theifwe had earlier. Duplicate the value, jump over the^, go right if the value is zero, go left (and then up) if it isn't. The thing to note here is that an integer is divisible by N ifx % Nis zero. If we go up, we simply 'walk around' the next bit of code."zziF",,,,. The"instruction starts 'string mode', in which all characters get pushed onto the stack as-is until another"is executed. Because stacks work on a Last In, First Out (LIFO) basis, we push the characters in the reverse order we want them to be printed in.,pops and prints a single character, and we pushed four, so four,s it is. This forms ourif (i % 3 == 0) { print("Fizz"); }logic.>\. We have a 'go right' here so that if we walked around the previous code, and we're coming in from above, we return to going right. At this point our stack has three values on it: Our counter, twice, and the result from the previous modulo, either 0 or 1. The\instruction swaps two values on the top of the stack, so the copy of our accumulator is back on top.5%!!:#^_"zzuB",,,,. This is exactly the same code as in steps 2-5, except we check if our counter is divisable by 5, and if it is, we print "Buzz". Note that if our value is divisible by both 3 and 5, it is also divisible by 15, and this automagically handles the "FizzBuzz" case for us!
Phew! That wasn't so bad, I hope. Deep breath, we're already on the last stretch.
Now that we did our FizzBuzz checks, we're all the way on the right side of the code, and the first thing we do is walk all the way back to the left, then up, then left again:
0>1+:45*5*`#@_
^,*25< _v#!*< <- we are here now!
^.:<
At this point, our stack has 3 values: Our counter, the result from the first modulo, and the result from the second modulo. Note that we're going left now, but I will still list the instructions in the order they are executed.
The two results tell us "was our counter not divisible by 3 and 5?". That slightly awkward negative in there is because of how I arranged the code, but here's a cool trick: When working with booleans (1s and 0s only), multiplication acts like the logical AND operation! In our case, since both of our operands are inverted, this actually becomes the logical NOR operation, and when we invert the result of that, we get the logical OR, which is what we need to answer "was our counter divisible by 3 or 5?"!
So, expectably we have another if: #v_. Skip over the v, go left if true, go right (and down) if false.
Let's look at the false path. Ignoring the direction changes, we execute :.. Since the _ removed our check value, the only thing we have left on our stack is the counter value. We duplicate it, and print it, using ., which pops a value and prints it as an integer.
We get back on the same path as the true path, which simply ignores the integer printing part, and we get the very last bit of the loop: 52*,. This pushes the value 10 onto the stack, and prints it as a character with ,. The character with value 10 is of course the newline character, which you'll know as \n in most languages.
Finally, we return to the very beginning of our code, and that's what we needed that > for. And so, we get the next iteration of our loop: We increment the counter, compare it, do the whole thing over and over again, intil our counter increments past 100, at which point the first if sends us left, ending the program at the @ instruction.
And that's FizzBuzz!
It's not the fastest, or smallest, or most obfuscated way to write it, but I'm quite happy with how it turned out. In fact, with some of the free space we have, we can sprinkle in a little flair:
0>1+:45*5*`#@_v > v > v
^,*25< _v#!*<>::3%!!:#^_"zziF",,,,>\5%!!:#^_"zzuB",,,,v
nya! ^.:< ^ $$$$$$$$$$$$$$$$$$ "FizzBuzz by Saphie" <
You'll see that I placed that string right in the middle of the code, so it'll get pushed onto our stack. That's what the chain of $s is for: it pops a value from the stack, and simply throws it away, removing the string again. The little nya! in the corner simply gets walked around by the code.
So how did I go about writing this? Surprisingly, it was quite straightforward: In essence, I wrote the pseudocode in an assembly-like language, with labels and jumps to direct control flow. This looked roughly like this:
start:
push 0
loop:
push 1
add
push 100
if (greater) { goto end; }
dup
dup
push 3
mod
not
not
and so on...
For the main FizzBuzz logic, I wrote down what I needed the stack to look like at each step, like so:
c = counter, r = result
c
::
c c c
3
c c c 3
%
c c r1
\
c r1 c
5
c r1 c 5
%
c r1 r2
*
c r
_
c
The rest was a matter of translating the pieces to Befunge instructions, and connecting the logic together in a compact manner. My familiarity with low-level languages and assembly definitely comes in handy when playing with esoteric languages, as they tend to deliberately be quite primitive.
And that's all! I hope it was an interesting read, and I hope I sparked your interest for this funky little language. Thanks for reading!