Saturday, November 23, 2013

Brainfuck

So a friend at work started IMing me with text "encoded" in a brainfuck program.  To be able to respond properly, I of course had to learn brainfuck.

Then I started tweeting out small brainfuck programs that output short strings.  I did this once per day, without making any kind of reference to them or giving any kind of clue as to what they were.  The goal was to see if anyone could figure it out and reply to me with what each one outputs.  The secondary goal was to learn how to optimize brainfuck for size so I could fit things into tweets.

For the uninitiated, brainfuck has eight operators. + and - add one and subtract one to the current memory "cell".  > and < move the memory pointer up one cell and down one cell.  [ begins a loop so long as the current cell is nonzero, and ] ends that loop (and causes flow to jump to the beginning of the loop).  Last but not least, . and , (period and comma) output the current cell as a character and take a single character as input to the current cell.  With these eight operations (and only one flow control structure!) you can do almost anything.

Here are all my brainfuck tweets.  I've stuck their output in spoiler tags.

November 12th: >++++[>++[<<++++++++>>-]<-]++[<+++++>-]<++.+++.---. LOL
November 13th: >++++++[<+++++++++++>-]>+++++++[<++++++++++++>-]<+>>+++++[<+++++++++>-]+++[<<<.>.>.>-]<<<.>.-..>>++[<----->-]<---.<<++.>--.+++.<+++.>--. BU-BU-BU-BUTT DRUGS
November 14th: >-[-------<+>]>-[---<+>]<----->>-[---<+>]>++++[-<++++++++>]<<<<.+>>>.<<<.-->>.--.+.->.<.++++++<<.+.---->..---<.-.-->>>.<<.>.>.<<<.+++.-. I JUST SHIPPED MY BED
November 15th: >+++++[>++[<<++++++++>>-]<-]<+++>>+++[>++[<<+++++>>-]<-]<++<.++.-----.>.<------.+++++.-. SUP JON
November 16th: >-[<->+++]<->>-[<->+++++++]<->>++++[<++++++++>-]<<<[.>.---.>.<---.+++.<-.+.>>.<+++<] Infinite loop of "THE BEST"
November 17th: >-[<->+++++++]>-[<->+++]<------->>-[<->+++]<->>++++[<++++++++>-]<<<<.>.>.<<----.>>--.<<++++.>+.>.>. INTERIOR
November 18th: >>----[<--->----]>-[<->+++]<--->>++++[<++++++++>-]<<<.>.---.<.>.<+.+++++.>---.<----.>>. CROCODILE
November 19th: >>----[<+>----]<++>>-[<->+++++++]<+++>>-[<->+++]<->++++++++++<<<.>..<++++++++.--.------.>>.<+++.>--.>. ALLIGATOR
November 20th: >>-[<->+++++++]>-[<->+++]<--->>++++[<++++++++>-]<<<.>>.<<-----.>.<+++++.>++++.<----.>>.<<----.>>. I DRIVE A
November 21st: >>----[<--->----]>-[<->+++]<------>>-[<->+++]<+>>++++[<++++++++>-]<<<<.+++++.---.>>.----.<.---.<.>>++.>. CHEVROLET
November 22nd: >>-[<->+++++++]>-[<->+++]<-------->>-[<->+++]<+>>++++[<++++++++>-]<<<.++.>.<<.----.>>>. MOVIE
November 23rd: >>-[<->+++++++]<->>-[<->+++]<->++++++++++<.<.---.----.>.<++++.>--.>.> THEATER

The seven starting on November 17th have a slight easter egg: they're small parts of a longer phrase, and I designed the programs such that you can join them all together to get the full phrase.  If you look at the memory dump of the full phrase you'll see that each day's program ends on the last cell it uses, and each day's memory is just appended to the previous day's.  In addition, the very last one is designed such that you can continually paste the whole thing over and over and have the phrase get generated over and over.

References explained:
November 13th: Rhett & Link's Butt Drugs commercial.
November 14th: K-Mart "Ship My Pants" commercial.
November 15th: the result of me having a vague discussion of these tweets with a friend who'd been trying to figure them out.
November 16th: well, just listen to the song "Best of You" by Foo Fighters and keep in mind that the internet likes to loop things that are repeated.
November 17th through 23rd: This freestyle rap that the internet once again decided to loop, just because it was funny.

The interpreter I used to make all of these is available at http://copy.sh/brainfuck/.  No download necessary, it runs within your browser.  It's a bit lacking in useful debugging features (such as breakpoints and step-by-step execution with live memory dump), but it works decently for writing and testing.

I did use calculation structures that I don't fully understand in my tweeted programs.  Basically, any of the later ones which all depend on cell value "wrapping".  This is because the cell values are unsigned, so 255+1 would be 0 and 0-1 would be 255.  I started having to use this method to calculate values in order to keep the programs small enough to fit in a single tweet.