Asp Forum - Codegolf - Writing a Brainf*ck interpreter

Frank Spychalski

8/7/2006 8:37:00 PM

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/competiti...). 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-devel.../archives/2006/08/07/playing-on-the-codeg...)
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.
--
http://amazing-devel...

13 Answers

Michael Ulm

8/8/2006 2:00:00 PM

Frank Spychalski wrote:

> 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/competiti...). 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-codeg...)
>
> 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"}[i]||"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: michael.ulm@isis-papyrus.com
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

8/8/2006 3:41:00 PM

Michael Ulm <michael.ulm@isis-papyrus.com> writes:

> 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"}[i]||"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"}[i]||''}
eval j.join("
")

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

Michael Ulm

8/9/2006 6:13:00 AM

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.
>

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: michael.ulm@isis-papyrus.com
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

8/9/2006 1:39:00 PM

Michael Ulm <michael.ulm@isis-papyrus.com> writes:

> 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("
> ")

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

8/9/2006 5:44:00 PM

On 8/9/06, Daniel Martin <martin@snowplow.org> wrote:
[snip]
> 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[i]')
prompt>

--
Simon Strandgaard

Simon Strandgaard

8/9/2006 7:05:00 PM

On 8/9/06, Simon Strandgaard <neoneye@gmail.com> wrote:
> On 8/9/06, Daniel Martin <martin@snowplow.org> wrote:
> [snip]
> > 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

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[i]')

--
Simon Strandgaard

Daniel Martin

8/9/2006 8:06:00 PM

"Simon Strandgaard" <neoneye@gmail.com> writes:

> 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[i]')

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[i]')
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

8/9/2006 8:39:00 PM

On 8/9/06, Daniel Martin <martin@snowplow.org> wrote:
> "Simon Strandgaard" <neoneye@gmail.com> writes:
> > 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[i]')
> is seventeen characters long.

Argh.. I misscalculated..
5 times d[i] = 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

--
Simon Strandgaard

Frank Spychalski

8/10/2006 2:13:00 PM

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

bye
Frank
--
http://amazing-devel...

Farrel Lifson

8/10/2006 2:23:00 PM

On 10/08/06, Frank Spychalski <rubytalk@spychalski.de> wrote:
> Thanks for the feedback, BTW the next challenge is out: Pascal's Triangle
>
> bye
> Frank
> --
> http://amazing-devel...
>
>

That was also a past ruby quiz (#84)

Farrel

comp.lang.ruby

Codegolf - Writing a Brainf*ck interpreter

Frank Spychalski

Michael Ulm

Daniel Martin

Michael Ulm

Daniel Martin

Simon Strandgaard

Simon Strandgaard

Daniel Martin

Simon Strandgaard

Frank Spychalski

Farrel Lifson

x Login to ForumsZone