Ruby Brainfuck golf [Update]

Some days ago, I discovered a website – which is the most addicting one I know :) – codegolf.com. The goal is, to solve programming problems with as short code as possible.

As I said, it is addicting. You do not write better ruby code by golfing. But you can really improve the knowledge of the language. And it is fun :)

Brainfuck

After doing some of the other challenges I tried the brainfuck challenge.
Brainfuck is a Turing-complete esoteric programming language consisting only of 8 letters, operating on a 30000 cells-array. This is the hello world program:

The goal is to build a interpreter.

A basic brainfuck interpreter

This is my first one. It is not that fast, but works fine.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

f,e=$<.read.split'!'
e&&e=e.split('')
b=[a=i=n=0]*s=30000
while i<f.size
  case f[i]
  when ?>
    a+=1
  when ?<
    a-=1
  when ?+
    b[a]+=1
  when ?-
    b[a]-=1
  when ?.
    putc b[a]
  when ?,
    e==[]?i=s:b[a]=e.shift[0]
  when ?[
    n=d=1 if b[a]==0
  when ?]
  n,d=1,-1 if b[a]!=0
  end

  while n>0
    i+=d
    f[i]==?[&&n+=d
    f[i]==?]&&n-=d
  end
  i+=1
end

• About 300 Byte without the whitespaces.
• Cannot calculate all square numbers till 1000 within 4 seconds..

There are some possibilities to shorten the code.. but not, to get down to 107 Bytes (that is the size of the brainfuck interpreter by the Ruby golfing god flagitious)! I had recognized, that I needed another approach.

Playing code golf

To understand the following solution better, here are the specifications about the brainfuck interpreter for the challenge:

• The Ruby version is 1.8.5
• The input for the brainfuck program is directly appended, split by an exclamation mark
• There is no cell overflow (255 + 1 = 256, not 0)
• The result of the tests (see the golfcode challenge page) has to be calculated within 4 seconds
• You don’t need 30000 cells, just enough to pass the tests
• The input is well formed brainfuck (…no “comments” are in it [except new lines])
• Exiting with an error is fine, as long the output is right :)

The ansatz is: eval

Every letter of the brainfuck program is translated into ruby and then executed via eval. Then, some golfing tricks are applied. For example the global variable $$ holds a (big) process number, which are enough cells. There are some more nice golfing tips at the codegolf-board (Thanks).

After lots of hours and hours (days!) of thinking, trying, depression, but also with senses of achievement, this is my result:

Ruby Brainfuck interpreter in 158 Bytes

 1
2
3
4

gets'!'
%w(! [ ] + - > < . ,).zip(%w{9 ( )while(0!=b[a]) b[a]+=1 b[a]-=1 a+=1 a-=1 putc(b[a]) (b[a]=getc)<11&&1/0}).map{|a,b|gsub a,b+$/}
eval"b=[a=0]*$$
"+$_

It’s so crazy… I don’t know (yet) how it’s possible to shrink it another 51 Bytes °_°

Update

I wanted to get into the top ten! So I thought and thought… and discovered that it actually is possible to get it shorter ;).

To get down to 149 Bytes I used the gsub mechanism of the 158 Byte solution, that was already there, to substitute some often used fragments of the code words. I also got some Bytes by putting the initialization out the eval.

Ruby Brainfuck interpreter in 149 Bytes

 1
2
3
4

gets'!'
%w(! + - > < [ ] . , j k).zip(%w{9 j+k j-k a+k a-k ( )until(j==0); putc(j); (j=getc)<11&&1/0; b[a] =1;}).map{|a,b|gsub a,b}
b=[a=0]*$$
eval$_

Won some Bytes!

Then I had been puzzled again.. and searched the internet. After reading some code of some top golfers (ruby but also perl), I realized the big trick: Instead of using the direct brainfuck commands to get the right eval code fragment, you can us their ASCII values by mapping them to low numbers. These can be used for (very short) Array access!

So how to find these mappings? I did it by writing a little bruteforce C programm (in C because I mistakenly thought, it will take some time to find a formula, but it got lots in seconds)

Now, I had to iterate on each sourcecode character instead of using gsub, so I could not use the “compression” substitution anymore. But nevertheless it is far shorter.

Ruby Brainfuck interpreter in 137 Bytes

 1
2
3

b=[a=0]*$$
gets'!'
eval split('').map{|z|%w{b[a]+=1 (b[a]=getc)<11&&1/0 b[a]-=1 putc(b[a]) 9 ( a-=1 )while(b[a]!=0) a+=1}[z[0]%32%11]}*$/

Yeah! Got into the top ten!

Ruby Brainfuck interpreter in 125120 Bytes

I did it and got the 5th place [:)]4th :). It is possible. I could not believe it myself. Now it is up to you, to find out how ;)

Ruby Brainfuck interpreter in 107 Bytes

…is the one by flagitious. Magic.

(He has not to obey the Ruby interpreter, the Ruby interpreter obeys him!)