fizzbuzz in brainfuck, part one
September 22, 2013> > > > > > > > > > > > > > > > > > > > > > < < + > + > + + + > > > + + + + + > > > + > + + + + + + + + + + > + + + + + + + + + + > + + + + + + + + + + > + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + > + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + > + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + > > > > > > > > > > > > > > > > > + + + + + + + [ < < < < < + + + + + + + + + + > > > > > - ] + + + + + + + + + + + [ < < < < + + + + + + + + + + > > > > - ] < < < < - - - - - > > > > + + + + + + + [ < < < + + + + + + + + + + > > > - ] < < < - - - - > > > + + + + + + + + + + + + [ < < + + + + + + + + + + > > - ] < < - - - > > + + + + + + + + + + + + [ < + + + + + + + + + + > - ] < + + < < < < < < < < < < < < < < < < < < < < < < [ > > > < < [ > > < [ > < < < < < < < < < > [ - ] + > [ - ] < < [ > > > > > > > > > < < < < < < > [ - ] > [ - ] < < [ > + > + < < - ] > [ < + > - ] > [ > > > > . > . > . > . < < < < < < < [ - ] ] > > > > < < < < < < < < < > - < [ > > + < < - ] ] > > [ < < + > > - ] < [ > > > > > > > > . > > > > > > > > > > > > > > > . > . > > > . . < < < < < < < < < < < < < < < < < < < < < < < < < > [ - ] > [ - ] < < [ > + > + < < - ] > [ < + > - ] + > [ < - > [ - ] ] < [ > > > > > > > > > > > > > > > > > > > > > > . > . > . . < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < [ - ] > > > > > > > > > > > < < < < < - ] > > > > > < < < < < < < < < + + + < + + + + + + + + + + [ - ] + > > > > > > > > > > < < < < < < < < - ] > > > > > > > > < < < < < < > [ - ] + > [ - ] < < [ > - < [ > > + < < - ] ] > > [ < < + > > - ] < [ < + + + + + > > > > > > < < < < < < < < < < [ < [ > > > > > > > > > > > . > > > > > > > > > > > > > > > > > . > . > . . < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < - ] + > - ] + > > > > > > > > > > < < < < < - ] > > > > > > > > + < < < < < < < < < < < < - > > > > > > > > > < < < < < < - > > > > > > < - ] + + + + + + + + + + > > > > - - - - - - - - - - < + < < < < - ] + + + + + + + + + + > > > > - - - - - - - - - - < + < < < < - ] > > > . > > > > > > > > > > > > > > > > > . > . > . . < < < < < < < < < < < < < < < < < < < < <
A couple of weeks ago I got it into my pointy little egg-head that I wanted to write a fizzbuzz in brainfuck. As with a lot of the stupid ideas that occur to me, I initially dismissed it as a waste of time, as-well-I-had-ought-to-have-done.
“Nahhhhhhh,” past me said to himself, chuckling, “that would be totally, needlessly hard right now, and it would take a lot of time, and anyway I don’t know how I would even START! Unless, maybe, well… I wonder if I could write an if/else… and then if I could do that…maybe with a multiples counter cell…and….”
And so after a quick googling, I was off. I nerd-sniped myself.
I decided the easiest way to go about it was to write fizzbuzz in Ruby, first, and then translate it into brainfuck. Aww Ruby, you so pretty with your little modulos and all that ish. But of course I couldn’t use anything more complicated than an if/else statement, and I had to do everything incrementally by 1, as well… and I could only stop loops by allowing their index counter to reach zero, not when it got to a certain high number like 100… hmmmmmm.
It looks a little unwieldy, but I used numbers spelled out as variable names to stand for the address of the memory cell that I would eventually use in brainfuck. The variables could only be set to numbers, and until loops can only be set to terminate at zero. I started by writing a program that simply counts to 100 without any of the divisor logic.
First I needed to mark how high I was going to count. We’re going to 100, so I need a 1 in the hundreds loop counter, a 10 in the tens loop counter, and a 10 in the ones loop counter to start with:
seven = 1
eight = 10
nine = 10
Those are the indices; they are going to be going down. Now I need the memory
slots holding the actual numerals that are going to be printed… including one
slot that holds a new line character I can access so not everything comes out
all smashed together, because I can’t use puts:
ten = "/n"
eleven = 0
twelve = 0
thirteen = 0
Now I’ll just create some nested loops to do the counting (up in the printed slots’ case and down in the index slots’ case):
until seven == 0
until eight == 0
until nine == 0
print ten #prints the newline
print eleven #prints the hundreds place
print twelve #prints the tens place
print thirteen #prints the ones place
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
end
nine = 10 #resets the ones place index slot
eight -=1 #decrements the tens place index slot
twelve += 1 #increments the tens place print slot
thirteen = 0 #resets the ones place print slot
end
eight = 10 #resets the tens place index slot
seven -= 1 #decrements the hundreds place index slot
eleven += 1 #increments the hundreds place print slot
twelve = 0 #resets the tens place print slot
end
Okay- still Ruby… ugly, non-Rubyish Ruby, but now it is nothing I can’t do in brainfuck.
But we haven’t done the hard part yet- implementing the logic that will filter out the multiples of 3 and 5 and replace them with “Fizz” and “Buzz.” In Ruby or any other higher level language, this program practically writes itself with a modulo operation, which returns zero if a number is evenly divisible by another number and leaves no remainder. But brainfuck, of course, doesn’t have this operation, and remember- it’s conditional loops can only be triggered by a “0” in the memory slot that is being evaluated, anyway.
This one took a little bit of thought, but a solution was forthcoming. I add two more index cells:
five = 3
six = 5
and decrement both of those each time I print a number out- when the “3” index slot reaches zero, I know I have found a multiple of 3 and can use that spot to trigger the code to print “Fizz” (and to reset the index back to 3- or rather 2 actually, since that accounts for the ol’ off by one) instead of the code to print the number. Ditto for “Buzz.”
Here is what all this looks like…
five = 3
six = 5
seven = 1
eight = 10
nine = 10
ten = "\n"
eleven = 0
twelve = 0
thirteen = 0
until seven == 0
until eight == 0
until nine == 0
if five == 0
print ten #don't forget the newline!
print "Fizz"
five = 2
six -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
elsif six == 0
print ten
print "Buzz"
six = 4
five -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
else
print ten #prints the newline
print eleven #prints the hundreds place
print twelve #prints the tens place
print thirteen #prints the ones place
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
five -= 1 #decrements the multiple of 3 tracker
six -= 1 #decrements the multiple of 5 tracker
end
end
nine = 10 #resets the ones place index slot
eight -=1 #decrements the tens place index slot
twelve += 1 #increments the tens place print slot
thirteen = 0 #resets the ones place print slot
end
eight = 10 #resets the tens place index slot
seven -= 1 #decrements the hundreds place index slot
eleven += 1 #increments the hundreds place print slot
twelve = 0 #resets the tens place print slot
end
#since the above loop is set to terminate at the top after it reaches 100, that
#final number won't get printed. I'll print it below:
print ten
print eleven
print twelve
print thirteen
Now, before printing the number, the program checks to see if it is a multiple of three or five…only when it is not divisible by either does it print the number itself.
This totally works! But there are some issues- I can’t use elsifs in brainfuck- the algorithms I’ve researched aren’t that sophisticated, and I haven’t implemented “FizzBuzz” for the numbers that are multiples of both- the logic catches them on “Fizz” and skips over the other bits. Also there is some needless repetition with the newlines, though I’m actually going to need some of that later on so I’ll leave it for now.
I can’t use explicit elsifs to evaluate mutliple possible states… but I CAN do that evaluation in series as two nested if/else statements, which is all elsif is shorthand for anyway… and I can deal with those! Now it looks like this:
five = 3
six = 5
seven = 1
eight = 10
nine = 10
ten = "\n"
eleven = 0
twelve = 0
thirteen = 0
until seven == 0
until eight == 0
until nine == 0
if five == 0
print ten #don't forget the newline!
print "Fizz"
five = 2
six -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
else
if six == 0
print ten
print "Buzz"
six = 4
five -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
else
print ten #prints the newline
print eleven #prints the hundreds place
print twelve #prints the tens place
print thirteen #prints the ones place
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
five -= 1 #decrements the multiple of 3 tracker
six -= 1 #decrements the multiple of 5 tracker
end
end
end
nine = 10 #resets the ones place index slot
eight -=1 #decrements the tens place index slot
twelve += 1 #increments the tens place print slot
thirteen = 0 #resets the ones place print slot
end
eight = 10 #resets the tens place index slot
seven -= 1 #decrements the hundreds place index slot
eleven += 1 #increments the hundreds place print slot
twelve = 0 #resets the tens place print slot
end
#since the above loop is set to terminate at the top after it reaches 100, that
#final number won't get printed. I'll print it below:
print ten
print eleven
print twelve
print thirteen
Aside from the repetition we are ignoring- there are three problems left. Still no “FizzBuzz,” and when it should make “FizzBuzz,” it throws off the 5’s counter into negative numbers so it never prints Buzz after 15. And it’s not evaluating 100. The first and second problem can be fixed with just one more “if” statement, nuzzled way down in the bowels of our increasingly complexprogram. We know we’ll only have to write “FizzBuzz” if we’ve already written “Fizz,” so anytime we print “Fizz,” we just throw in an extra check against whether or not we need to write “Buzz.” Now, if we write “FizzBuzz”, we will also be resetting the 5’s counter.
Oh and as for the last problem, I just hardcoded printing “Buzz” out at the end instead of “100”, bypassing all the logic, because I’m a filthy, cheating, dirty fraud. YOLO####333. Also because it will always end up on a multiple of 100, so at least the “Buzz” part will be right. Screw you, 300, 600, and 900!!
five = 3
six = 5
seven = 1
eight = 10
nine = 10
ten = "\n"
eleven = 0
twelve = 0
thirteen = 0
until seven == 0
until eight == 0
until nine == 0
if five == 0
print ten #don't forget the newline!
print "Fizz"
if six == 0
print "Buzz"
six = 5
end
five = 2
six -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
else
if six == 0
print ten
print "Buzz"
six = 4
five -= 1
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
else
print ten #prints the newline
print eleven #prints the hundreds place
print twelve #prints the tens place
print thirteen #prints the ones place
nine -= 1 #decrements the ones index slot
thirteen += 1 #increments the ones print slot
five -= 1 #decrements the multiple of 3 tracker
six -= 1 #decrements the multiple of 5 tracker
end
end
end
nine = 10 #resets the ones place index slot
eight -=1 #decrements the tens place index slot
twelve += 1 #increments the tens place print slot
thirteen = 0 #resets the ones place print slot
end
eight = 10 #resets the tens place index slot
seven -= 1 #decrements the hundreds place index slot
eleven += 1 #increments the hundreds place print slot
twelve = 0 #resets the tens place print slot
end
# Since the above loop is set to terminate at the top after it reaches 100, that
# final number won't get printed. I'll print it below:
print ten
print "Buzz" #dirty cheater.
So I’ve written the whole program in a way that brainfuck can accommodate. The next step is to translate it. Bleep, bloop, bleep! I’m going to write that in a separate post, because this is getting pretty long. Also if you want to increase the maximum number that you’re evaluating, try changing the initial index of the hundreds place in the above code! It will go for as long as you want it to, because it will just continue to print higher numbers because it is Ruby! brainfuck wouldn’t be able to do that past 999, because we would need to implement a new loop to print the thousands place, because it is printing strings of digits instead of numbers. We’ll get to that next time.
If you got this far, you deserve this. Come back soon!