Codegolf - Writing a Brainf*ck interpreter

[Frank Spychalski]

Hi,

I stumbled over this funny site called CodeGolf.com and tried my luck
on one of their problems "Writing a Brainf*ck" Interpreter
(http://www.codegolf.com/competition/index/8). I have a working
solution, but it is still pretty large compared to the only other Ruby
solution.

I put my code online
(http://amazing-development.com/archives/2006/08/07/playing-on-the-codegolf-range/)
and added some explanations on what I did.

If any Ruby Guru would review my code and give me some hints for
further improvement, I would be forever in his debt...

thanks
Frank

ps: I won't submit any solution where I used outside help! I just
cannot imagine how a 142 byte solution is even possible and search for
insight.

 

[Michael Ulm]

Hi,

I stumbled over this funny site called CodeGolf.com and tried my luck
on one of their problems "Writing a Brainf*ck" Interpreter
(http://www.codegolf.com/competition/index/8). I have a working
solution, but it is still pretty large compared to the only other Ruby
solution.

I put my code online
(http://amazing-development.com/archives/2006/08/07/playing-on-the-codegolf-range/)

and added some explanations on what I did.

Using the idea by Daniel Martin on your site, I managed to come up with a
232 byte solution:

c,$k=STDIN.read.split'!'
eval "d,a=[],0;"+c.unpack("C*").map{|i|
{10,"",?+,"y+",?-,"y-",?[,"while y*>0 do",?],"end",?.,"print y*.chr",
?,,"d[a]=$k.slice!(0) or exit"}||"a+=#{i-61}"
}.join(";").gsub(/y(.)/,'(d[a]=(d[a]||0)\11&255)')

To make it as small as possible, join the last four lines.

Best regards,

Michael


--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: (e-mail address removed)
Visit our Website: www.isis-papyrus.com

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------

 

[Daniel Martin]

Using the idea by Daniel Martin on your site, I managed to come up with a
232 byte solution:

c,$k=STDIN.read.split'!'
eval "d,a=[],0;"+c.unpack("C*").map{|i|
{10,"",?+,"y+",?-,"y-",?[,"while y*>0 do",?],"end",?.,"print y*.chr",
?,,"d[a]=$k.slice!(0) or exit"}||"a+=#{i-61}"
}.join(";").gsub(/y(.)/,'(d[a]=(d[a]||0)\11&255)')

I've found I can do even better by switching d to a huge (32K) string
of \0s, which lets you dispense with the &255 bit. I also went back
to building the new script in a separate variable, which let me
replace .unpack("C*").map with .each_byte

I like your use of gsub and wish I could take advantage of that too,
but trying to ends up with a net expansion of my current 214 byte
version:

c,$k=STDIN.read.split'!'
j=%w[d="\0"*8**5 a=0]
c.each_byte{|i|j<<{?<,"a-=1",?>,"a+=1",?+,"d[a]+=1",
?-,"d[a]-=1",?[,"while d[a]>0 do",?],"end",
?.,"print d[a,1]",?,,"d[a]=$k.slice!(0)||exit"}||''}
eval j.join("
")

As with yours, you get to 214 bytes by joining the lines that make up
the hash literal.

 

[Michael Ulm]

Daniel Martin wrote:
--snip--

I like your use of gsub and wish I could take advantage of that too,
but trying to ends up with a net expansion of my current 214 byte
version:

c,$k=STDIN.read.split'!'
j=%w[d="\0"*8**5 a=0]
c.each_byte{|i|j<<{?<,"a-=1",?>,"a+=1",?+,"d[a]+=1",
?-,"d[a]-=1",?[,"while d[a]>0 do",?],"end",
?.,"print d[a,1]",?,,"d[a]=$k.slice!(0)||exit"}[i]||''}
eval j.join("
")

As with yours, you get to 214 bytes by joining the lines that make up
the hash literal.
[/i][/QUOTE][i]

Very nice. If you accept a more fragile version (but still conforming
to the specs) you can bring that down to 210 bytes:

c,$k=STDIN.read.split'!'
j=%w[d="\0"*8**5 a=0]
c.each_byte{|i|j<<({10,"",?<,"a-=1",?>,"a+=1",
?[,"while d[a]>0 do",?],"end",?.,"print d[a,1]",
?,,"d[a]=$k.slice!(0)||exit"}[i]||"d[a]+=#{44-i}")}
eval j.join("
")



--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: [email][email protected][/email]
Visit our Website: [URL="http://www.isis-papyrus.com"]www.isis-papyrus.com[/URL]

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------[/i][/i]

 

[Daniel Martin]

Very nice. If you accept a more fragile version (but still conforming
to the specs) you can bring that down to 210 bytes:

c,$k=STDIN.read.split'!'
j=%w[d="\0"*8**5 a=0]
c.each_byte{|i|j<<({10,"",?<,"a-=1",?>,"a+=1",
?[,"while d[a]>0 do",?],"end",?.,"print d[a,1]",
?,,"d[a]=$k.slice!(0)||exit"}||"d[a]+=#{44-i}")}
eval j.join("
")

I managed to squeeze out a few more characters by replacing the hash
lookup with an array index. I also switched out slice!(0) for an
indexing operation, but in the end that caused no overall character
count change. Anyway, here's 198 characters:

c,$k=STDIN.read.split'!'
j=%w[d="\0"*8**5 q=a=0]
c.each_byte{|i|j<<'
a-=1
a+=1
while d[a]>0
end
print d[a,1]
d[a]=$k[q]||exit;q+=1
d[a]+=1
d[a]-=1'.split('
')["
<>[].,+-".index(i)]}
eval j.join("
")

As an added bonus (?), all the newlines in that are necessary to the
code.

Still, there's supposedly another way to squeeze an additional 50
characters out, which I think is going to require some sort of
fundamental shift in the approach to the problem.

 

[Simon Strandgaard]

Still, there's supposedly another way to squeeze an additional 50
characters out, which I think is going to require some sort of
fundamental shift in the approach to the problem.

I have just given it a shot.. 146 bytes

prompt> ruby bf.rb
'++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
Hello World!
prompt> ruby bf.rb ',[.,]'this program echoes its input
this program echoes its input
only 146 bytes!
only 146 bytes!
^Cbf.rb:3: (eval):5:in `getc': (Interrupt)
from (eval):5
prompt> cat bf.rb
eval 'd=[i=0]*8**5'+ARGV[0].gsub(/./){"
"+%w[i+=1 X+=1 i-=1 X-=1 print(X.chr) X=STDIN.getc end
while(X>0)]['>+<-.,]['.index($&)]}.gsub(/X/,'d')
prompt>

 

[Simon Strandgaard]

I have just given it a shot.. 146 bytes

I saw at the codegolf page that one had a record of 142 bytes..

well here is my 141 bytes long version

eval 'd=[i=0]*8**5'+ARGV[0].gsub(/./){"
"+%w[i+=1 X+=1 i-=1 X-=1 putc(X) X=STDIN.getc end
while(X>0)]['>+<-.,]['.index($&)]}.gsub(/X/,'d')

 

[Daniel Martin]

well here is my 141 bytes long version

eval 'd=[i=0]*8**5'+ARGV[0].gsub(/./){"
"+%w[i+=1 X+=1 i-=1 X-=1 putc(X) X=STDIN.getc end
while(X>0)]['>+<-.,]['.index($&)]}.gsub(/X/,'d')

Note that both this and the earlier one you posted don't conform to
the interface of the codegolf challenge: namely, that bf program will
be presented on stdin, and separated from input by a !.

Also, your program fails on this simple bf program:
++++[>++++++++[>++++++++<-]<-]>>[>++++++++++.<-]

A correct bf interpreter using the traditional 8-bit cell should
output nothing. Yours... doesn't. True, the codegolf people didn't
say you had to use an 8-bit cell, so maybe this is ok.

However, I hadn't known about putc, and seeing your code gives me some
ideas.

Note that even with your version, you can save two bytes by NOT doing
the .gsub bit, and expanding X into d[a]. Doing that substitution may
save you 15 characters out of the %w block, but
gsub(/X/,'d')
is seventeen characters long.

Anyway, here's where I'm at, at 168 characters:

j='d="\0"*8**5;a=0'
while i=STDIN.getc
j+='
'+%w{1 a-=1 a+=1 while(d[a]>0)
end putc(d[a]) d[a]=STDIN.getc||exit
d[a]+=1 d[a]-=1}["
<>[].,+-".index(i)||break]
end
eval j

 

[Simon Strandgaard]

well here is my 141 bytes long version

[snip]
Note that both this and the earlier one you posted don't conform to
the interface of the codegolf challenge: namely, that bf program will
be presented on stdin, and separated from input by a !.

aha.. I did'nt really use the rules from codegolf. I looked it
up at wikipedia. I should had seen this.

A correct bf interpreter using the traditional 8-bit cell should
output nothing. Yours... doesn't. True, the codegolf people didn't
say you had to use an 8-bit cell, so maybe this is ok.

Ok, I have to rethink the impl to restrict it to 8 bit.
Now I see why people is using strings for this.

However, I hadn't known about putc, and seeing your code gives me some
ideas.

Note that even with your version, you can save two bytes by NOT doing
the .gsub bit, and expanding X into d[a]. Doing that substitution may
save you 15 characters out of the %w block, but
.gsub(/X/,'d')
is seventeen characters long.

Argh.. I misscalculated..
5 times d = 20 bytes
5 times X + 17 = 22 bytes

Thanks for your hints.

Anyway, here's where I'm at, at 168 characters:

j='d="\0"*8**5;a=0'
while i=STDIN.getc
j+='
'+%w{1 a-=1 a+=1 while(d[a]>0)
end putc(d[a]) d[a]=STDIN.getc||exit
d[a]+=1 d[a]-=1}["
<>[].,+-".index(i)||break]
end
eval j

Idea for improvement:

while(d[a]>0)
end
#=> 13 bytes

(
)while(d[a]>0)
#=> 12 bytes

 

[Frank Spychalski]

Thanks for the feedback, BTW the next challenge is out: Pascal's Triangle

bye
Frank

 

[Farrel Lifson]

Thanks for the feedback, BTW the next challenge is out: Pascal's Triangle

bye
Frank

That was also a past ruby quiz (#84)

Farrel

 

[Frank Spychalski]

it is easier than then ruby quiz because there is no need to align the cells

 

[Mike Berrow]

Can anyone vouch for the authenticity of this 'codegolf.com' site?
Several things seem strange about it.

-- The code submissions do not seem to be viewable
-- There is zero activity in the forums

-- Mike Berrow

 

[Ben Bleything]

Can anyone vouch for the authenticity of this 'codegolf.com' site?
Several things seem strange about it.

What do you mean by "authenticity?" Are you afraid they're going to
take your golfed brainf*ck interpreter and sell it?

I've submitted a number of solutions and everything works the way they
say it will, that's good enough for me.

-- The code submissions do not seem to be viewable

Of course they're not... otherwise you could just download and resubmit
the best entry and effectively cheat.

-- There is zero activity in the forums

According to the front page, it seems that the forums were opened less
than a day ago. So, I'm not surprised The site itself isn't that old
and hasn't gotten much publicity yet.

I'm not quite sure what you're worried about, but I wouldn't be.

Ben