Aug '06
Playing on the CodeGolf Range
by Frank Spychalski filed under articles, Computer, Fun, Ruby

picture by bigpru

I stumbled over this funny site called and tried my luck on the first problem (actually it’s the sixth, but it was the last and therefore appeared first on their page – confused?) Writing a Brainfuck Interpreter:

The brainfuck language uses a simple model of a computer consisting of an array of memory cells, a movable pointer into the array, an output stream, an input stream and the program itself. The program is formed from a sequence of the below commands :

  • > – Increment the pointer to point to the next cell to the right.
  • < – Decrement the pointer to point to the next cell to the left.
  • + – Increment the byte pointed to by the pointer.
  • - – Decrement the byte pointed to by the pointer.
  • [ - Jump forward to the command after the corresponding ] if the byte at the pointer is zero.
  • ] – Jump back to the command after the corresponding [ if the byte at the pointer is non-zero.
  • . - Output the value of the byte at the pointer.
  • , - Accept one byte of input, storing its value in the byte at the pointer.

It didn't take me very long to write a running interpreter. My first version was more than a thousand characters. Even after renaming the variables and stripping all the whitespaces I still needed around 700 characters, which is huge compared to the best Ruby solution with only 142 characters.

Warning! Spoilers ahead - you might want to stop reading if you want to solve the problem, too

Brainfuck Interpreter Version 1 - a real interpreter

This was my very first idea. The algorithm is pretty obvious and nothing really fancy was done here. Two optimizations:

  • aggregated the + and - operation and < and > into one when each to save space
  • iterate over the input program to get the target addresses for the jump operations

But this code was still too slow. It passed the first 5 tests, but failed the rot13 performance test.

# Version 1 after a lot of rewrites

data =,0)
datapointer = 0
codepointer = 0

(code,input) = '!'

# build a jump table to quickly access target address to jump to
stack = []
jmptbl = {}
(0..(code.size-1)).each {|i|
  case code[i]
    when 91: stack.push i
    when 93: m = stack.pop; jmptbl[i] = m; jmptbl[m] = i  

while codepointer < code.size do
  x = code[codepointer]
  case x
# < >
    when 60, 62: datapointer = datapointer + x - 61 
# + - 
    when 43, 45: data[datapointer] = (data[datapointer] - x + 44) % 256
# [
    when 91: codepointer = (data[datapointer] == 0 ? jmptbl[codepointer] : codepointer)  
# ]             
    when 93: codepointer = (data[datapointer] != 0 ? jmptbl[codepointer] : codepointer)
# .
    when 46: print "#{data[datapointer].chr}" 
# ,    
    when 44: data[datapointer] = input.slice!(0)
             exit if data[datapointer].nil?   
  codepointer = codepointer + 1  
# Version 1 obfuscated 
# 389 characters without this comment,0)
case c[i]
when 91:s.push i
when 93:m=s.pop;j[i]=m;j[m]=i  
while b<c.size do
case x
when 60,62:a=a+x-61 
when 43,45:d[a]=(d[a]-x+44)%256  
when 91:b=(d[a]==0?j[b]:b) 
when 93:b=(d[a]!=0?j[b]:b)
when 46:print"#{d[a].chr}"
when 44:d[a]=k.slice!(0)
exit if d[a].nil?  

Brainfuck Interpreter Version 2 - "optimize - don't do it"

This code contains many useless optimizations :-)

  • store the target address inside the program as the address for ] or address plus codesize for [
  • store + and - as -255 and -257, so I can simply add the command to the data

But these optimizations didn't provide any significant speedup, the code was only about 10 percent faster on my machine which was still too slow to pass the performance test. And the program was even larger than my original version with 533 characters. I could perhaps squeeze out a few characters with a complicated formula for the first 6 lines of the case statement, but I didn't try this because this version was too slow anyway.

# version 2 - forget it, it sucks
data =,0)
codepointer = 0
datapointer = 0

(code,input) = '!'

codesize = code.size
stack = []
opt = []
(0..(codesize-1)).each {|i|
  case code[i]
    when 60: opt << -3
    when 62: opt << -1
    when 43: opt << -255 
    when 45: opt << -257 
    when 44: opt << -5 
    when 46: opt << -6     
    when 91: stack.push opt.size; opt << 0 # just a placeholder
    when 93: m = stack.pop; opt[m] = opt.size + codesize; opt << m  
while codepointer < opt.size do
  x = opt[codepointer]
  if x < -200
    data[datapointer] = (data[datapointer] + x) % 256
  elsif x < -3
    if x == -5
      data[datapointer] = input.slice!(0)
      exit if data[datapointer].nil?
      print "#{data[datapointer].chr}"
  elsif x < 0
    datapointer = datapointer + x + 2  
    if x < codesize
      codepointer = (data[datapointer] != 0 ? x : codepointer)    
      codepointer = (data[datapointer] == 0 ? x % codesize : codepointer)
  codepointer = codepointer + 1  

Brainfuck Interpreter Version 3 - Brainfuck to Ruby

As I realized I wasn't going to pass the performance test with my other ideas I knew I had to generate Ruby code. The tricky part was how to simulate the commands "[" and "]". I started with the "Hello World!" Brainfuck program and rewrote it step by step in Ruby until I had an idea on how to replace every character of the input language with a chunk of Ruby code.

picture by digitalsextant

My translation table:
[ if currentCell != 0
] end while currentCell != 0
< plus -1
> plus 1
+ inc 1
- inc -1
. out
, read

The definitions for the methods are shown below. The whole program was slightly larger than my version 1 but it is about 3 times faster, which was fast enough to pass the performance test.

# Version 3
def currentCell
  $data[$datapointer] || 0
def inc i
  $datapointer = $datapointer + i
def plus i 
  $data[$datapointer] = currentCell + i) % 256
def out
  print "#{currentCell.chr}"
def read
  $data[$datapointer] = $input.slice!(0)
  exit if !$data[$datapointer]
def append s
  $program << s << "

$program = ''
$data = []
$datapointer = 0

($code,$input) = '!'

(0..($code.size-1)).each {|i|
  tmp = $code[i]
  case tmp
    when 60,62: append "inc #{tmp-61}"
    when 43,45: append "plus #{44-tmp}"
    when 91: append "if currentCell != 0
    when 93: append"end while currentCell != 0
    when 46: append "out"
    when 44: append "read"
eval $program 
# Version 3 obfuscated
# 401 characters without this comment
def x
def y i
def v i 
def t
def u
exit if !$d[$a]
def r s
case q
when 60,62:r"y #{q-61}"
when 43,45:r"v #{44-q}"
when 91:r"if x!=0
when 93:r"end while x!=0
when 46:r"t"
when 44:r"u"
eval $p

What's next?

I had a lot of fun writing these different versions. But now I'm stuck. I don't have the slightest clue on how to get to an even shorter piece of code. I already tried to add a method which generates the methods currentCell, inc, etc. but the overhead of one added method was more than what I gained by removing def and end.
I'm still thinking about other possible techniques to move towards the 142 byte by carldr. I believe there is a trick that uses special knowledge of the Brainfuck language I just don't have. If anybody has some generic hints on how to write shorter Ruby code, please leave a note :-)

6 Responses to “Playing on the CodeGolf Range”

  1. 1


    Thanks for the blog post, it was really interesting to read the process you’ve gone through to get the solution you have! There are a few clues I’ll give you :

    1) You’re on the right track with your last submission.
    2) I know no special knowledge of the Brainfuck language.
    3) You don’t need any function calls.

    I’m sure there are more I can give you, but that would ruin the surprise of finding them! If you’re on IRC, drop by #codegolf on – I’m usually round during the day UK time. Or, if you’re not, there will be forums on the Codegolf site within the week. Either way, I’ll try and give you some more hints without ruining the fun. Glad you’re enjoying the site.


    carldr (August 7th, 2006 at 23:29)
  2. 2

    # 243 bytes, once extraneous newlines are removed (in the big hash literal, commas don’t need to be followed by newlines)

    def x i=0;$d[$a]=(($d[$a]||0)+i)%256;end
    eval $c.unpack("C*").map{|i|{?<,"$a-=1",?>,"$a+=1",?+,"x 1",
    ?-,"x -1",?[,"while x>0 do",?],"end",?.,"print x.chr",
    ?,,"$d[$a]=$k.slice!(0) or exit"}[i]||''}.join("

    As a plus, I think it’s faster too.

    edited the code to work around wordpress

    Daniel Martin (August 8th, 2006 at 03:58)
  3. 3

    Thanks for the comments. It’s embarrassing that I have missed Carl’s #3. Daniel thanks for the code – I didn’t think of to create my program, nice idea… Right now I’m at work but I can’t wait to get home :-)

    Frank Spychalski (August 8th, 2006 at 09:34)
  4. 4

    Note that some of my code seems to have been eaten by the submission process – part of that hash literal should read:

    {?<,”$a-=1″,?>,”$a+=1″,?+,”x 1″,

    Daniel Martin (August 8th, 2006 at 11:05)
  5. 5

    I edited your original comment, but it doesn’t work on my machine. Could you mail me your code (to fs at this domain)?

    Frank Spychalski (August 8th, 2006 at 11:46)
  6. 6

    Finally a working version from Daniel :-) Thanks again

    Frank Spychalski (August 8th, 2006 at 16:18)

Any comments? Or questions? Just leave a Reply: