# Optimized FizzBuzz in brainfuck

While looking for brainfuck related things, I came across Simon Forsberg's FizzBuzz in Brainfuck and cheekily commented a link to my own brainfuck FizzBuzz answer over on PPCG. He suggested I should post my own Code Review question with a detailed explanation.

First, the code (350 bytes):

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


### Try it online!

This can be split into three sections:

• Tape generation: Sets up the tape in the correct format
• While looping over 100 numbers:
• Checking the number: Checks if the number is divisible by 3 or 5, and printing Fizz and/or Buzz if so.
• Printing the number: Only if it isn't a FizzBuzz number

# Tape Setup:

• Cell 3: The counter for the "Buzz" section
• Cell 4 through 8: These are the ascii values for "BuziF", a compact way of representing both "Fizz" and "Buzz".
• Cell 9: The counter for the "Fizz" section
• Cell 11: The overall counter to keep track of the 100 numbers

Brainfuck code:

Generates the number 61:
+[-[>+<<]>-]>--
This is taken from the Esolangs brainfuck constants page at https://esolangs.org/wiki/Brainfuck_constants

Sets all the cells to values very close to the needed ones
Basically multiplies 61 by various values (going over 255 wraps around to 0)
[>+>++>++>++++++>+>>>++++++<<<[<]>-]
Tape looks like:
0 0' 61 122 122 110 61 0 0 110
It needs to be:
0 5  66 117 122 105 70 3 0 100
Notice that (almost) all of these values are off by multiples of 5 so we increment a cell to 5
<+++++
And add/subtract 5s from each value
[>+>+>->>->++>+>>--[<<]>-]
Leaving the tape as:
0' 5 66 117 122 105 71 5 0 100
We make some final changes to get the desired cells
>[>]<--<->>>
Before leaving the memory pointer on the counter


# Inside the Loop:

## Checking if Fizz/Buzz

Both the Fizz and Buzz counters are initially set to 5 and 3 respectively. At each iteration of the loop, both counters are decremented. If either reach 0, their respective string is printed and resets the counter. It also sets a check for later to not print the number. Here's a python representation of this section of the code.

fizz = 3
buzz = 5
for i in range(1,101):
check = False
fizz -= 1
buzz -= 1
if fizz == 0:
print("Fizz",end='')
fizz = 3
check = True
if buzz == 0:
print("Buzz",end='')
buzz = 5
check = True
if not check:
print(i,end='')
print()


The relevant brainfuck section is:

Tape Format:
0 BCounter "BuziF" FCounter Check 0 Counter

<<- Decrement Fizz counter
[<]<[ If Fizz counter == 0
>+++   Reset counter
>+<<   Increment check cell
.<.<.. Print "Fizz"
[<]<]
>>- Decrement Buzz counter
[<<]>[ If Buzz counter == 0
<+++++   Reset counter
>.>.>..  Print "Buzz"
[>>>]<<+ Increment check cell
[<]]


## Printing the number

If the FizzBuzz check is empty, we need to print the number as an actual string. Since brainfuck doesn't have a way to convert a cell value to a printed number (surprise surprise), we need to convert the counter to two ASCII values (not three, since 100 is "Buzz") representing the number.

However, the counter is counting down from 100, we first need to subtract it from 100. Then we get the number modulo 10, which leaves us the tens and singles in different cells. Before printing though, we need to check whether the tens digit is 0, in which case we remove it. Then we add 48 to the numbers to convert it to the ASCII value of the number and print them. Here's some more python code:

def printNumber(n):
#Only works for numbers between 0 and 100
tens = n//10
singles = n%10
if tens != 0:
print(chr(tens+48), end='')
print(chr(singles+48), end='')


The relevant brainfuck code:

If the number check is 0 (reset the cell if not)
>[>>>]<<[[-]>>]>
[
Tape looks like:
BuziF c 0 100-N' 0  where 100-N is the counter and N is the number
We won't use anything left of the 100-N

Generate the number 100 and the number 10
>(10++++++++++)[->(10++++++++++)>+<<]
Tape: 0 100-N 0' 100 10
Subtract 100-N from 100 while keeping a copy of the 100-N
<[->+>-<<]
And increment N by 2 to counter some modulo stuff
>>++
Tape: 0 0 100-N N+2' 10 0
[ While N
Tape: 0 0 100-N N' Modulo Quotient 0;
>[>>>]< If the modulo is 0:
[>++++++++++>+>] Reset the modulo to 10 and increment the Quotient
<<-<- Decrement both N and the modulo
]
Tape: 0 0 100-N 0' 9-single tens
Subtract the singles cell from 10
+++++++++>[-<->]<[->+<]>>[>]
Tape:  0 0 100-N 0 single tens 0'
If the tens cell is 0:
Tape: 0 0 100-N 0 single 0'

(8++++++++)[-<(6++++++)<(6++++++)>>]
Tape: 0 0 100-N 0 single tens 0'
OR
Tape: 0 0 100-N 48 single 0'

If the tens cell was 0 reset the 48 cell
<<<[>[-]]
Tape: 0 0 100-N 0 single tens 0'
OR
Tape: 0 0 100-N 0 single 0'

Print the tens (if needed) and singles while resetting the cells
>[>]<[.[-]<]<
Move the 100-N cell back to the correct position
[-<+>]>
Tape: 0 100-N 0' 0 0
]


### And Finally!

Printing a newline

++++++++++.[-]


And decrementing the counter

<<-]


# Main Questions:

• Can I make this any more optimized? My biggest concerns are:
• The number printing section, which is extremely inefficient with the modulo section
• The tape setup, which can probably be shorter.
• Should I setup the newline cell (10) in the tape generation section rather than generate it once per loop?

By just going through it in such detail in this question I've already thought of several ways to shorten the code, so there's that at least.

TAPE FORMAT:
0
5   : Buzz Counter (BC)
66  : ASCII "B"
117 : ASCII "u"
122 : ASCII "z"
105 : ASCII "i"
70  : ASCII "F"
3   : Fizz Counter (FC)
0   : FizzBuzz Check (Ch)
100 : Loop counter (C)
0

Some definitions:
' : Memory pointer is on this cell
_ : Substitute for dash
p : Substitute for plus
N : The current number

Generates the number 61:
+[-[>+<<]>-]>--
This is taken from the Esolangs brainfuck constants page at https://esolangs dot org/wiki/Brainfuck_constants

Sets all the cells to values very close to the needed ones
Basically multiplies 61 by various values (going over 255 wraps around to 0)
[>+>++>++>++++++>+>>>++++++<<<[<]>-]
Tape looks like:
0 0' 61 122 122 110 61 0 0 110
It needs to be:
0 5  66 117 122 105 70 3 0 100
Notice that (almost) all of these values are off by multiples of 5 so we increment a cell to 5
<+++++
And add/subtract 5s from each value
[>+>+>->>->++>+>>--[<<]>-]
Leaving the tape as:
0' 5 66 117 122 105 71 5 0 100
We make some final changes to get the desired cells
>[>]<--<->>>
Finally leaving the memory pointer on the counter

TAPE: 0 5 66 117 122 105 71 5 0 100'

[
CHECKING FOR FIZZBUZZ
<<- Decrement Fizz counter
[<]<[ If Fizz counter == 0
>+++   Reset counter
>+<<   Increment check cell
.<.<.. Print "Fizz"
[<]<]
>>- Decrement Buzz counter
[<<]>[ If Buzz counter == 0
<+++++   Reset counter
>.>.>..  Print "Buzz"
[>>>]<<+ Increment check cell
[<]]

PRINTING NUMBER
If the number check is 0 (reset the cell if not)
>[>>>]<<[[-]>>]>
[
TAPE: BC BuziF FC 0 100_N' 0
We won't be using anything left of the 100_N so we can ignore it

Generate the number 100 and the number 10
>(10++++++++++)[->(10++++++++++)>+<<]
Tape: 0 100_N 0' 100 10
Subtract 100_N from 100 while keeping a copy of it
<[->+>-<<]
And increment N by 2 to counter some modulo stuff
>>++
Tape: 0 0 100_N Np2' 10 0
[ While N
Tape: 0 0 100_N N' Modulo Quotient 0;
>[>>>]< If the modulo is 0:
[>++++++++++>+>] Reset the modulo to 10 and increment the Quotient
<<-<- Decrement both N and the modulo
]
Tape: 0 0 100_N 0' 9_single tens
Subtract the singles cell from 10
+++++++++>[-<->]<[->+<]>>[>]
Tape:  0 0 100_N 0 single tens 0'
If the tens cell is 0:
Tape: 0 0 100_N 0 single 0'

(8++++++++)[-<(6++++++)<(6++++++)>>]
Tape: 0 0 100_N 0 single tens 0'
OR
Tape: 0 0 100_N 48 single 0'

If the tens cell was 0 reset the 48 cell
<<<[>[-]]
Tape: 0 0 100_N 0 single tens 0'
OR
Tape: 0 0 100_N 0 single 0'

Print the tens (if needed) and singles while resetting the cells
>[>]<[.[-]<]<
Move the 100_N cell back to the correct position
[-<+>]>
Tape: 0 100_N 0 0' 0
]
Print a newline
++++++++++.[-]
And decrement counter
<<-
]

• Just give me some time and I promise to review this! – Simon Forsberg Feb 1 '18 at 17:11
• @SimonForsberg No pressure, but any updates? – Jo King Apr 30 '18 at 4:23
• Still planning on reviewing it some time, unfortunately reviewing Brainfuck code is not an easy task. I'm a bit busy the coming week but I promise I haven't forgotten (entirely) about this! – Simon Forsberg May 2 '18 at 10:30