World's smallest ETA interpreter
Copyright © Stephen Sykes, 2002 - 2007.
It's fun to write really small and compact code in the tradition of the annual obfuscated C contest. Perl also lends itself to this kind of compressed code, and there is an ETA interpreter written in this way.
Ruby, however, is not known for this type of thing. But I present here a compressed Ruby interpreter that is rather shorter than the shortest Perl version made so far:
Actually, this started life as a 5-liner, but harsh competition from mtve and the guys at Perl Monks motivated me to do some more work on it. The most significant optimisations were using gsub as the line level iterator, using negative subscripts instead of using the 'size' method on the stack, extensive use of logical operators rather than 'if' or '?:', and use of the $= variable instead of downcase.
It now stands at 306 characters and I'm particularly pleased with it.
So the challenge has been laid - is is possible to build an ETA interpreter in less than this in a mainstream language?
*** [update 21 Feb 2002] Mtve and the guys ar perl monks have come up with a new strategy that beats this Ruby implementation - 290 bytes is the current record. See the evolution described here. I tried a couple of different Ruby implementations, including this one:
But this is 318 chars.
*** [update 22 Jan 2003] Nearly a year later, and I returned to the project.
It took just a couple of flashes of inspiration, and Ruby now comes in at 277 characters -
comfortably beating Perl once more!
So the challenge has once again been laid before the Perl Monks.
*** [update 23 Jan 2003] Mtve responded splendidly with a 270 character perl masterpiece. However, I have made some improvements. I sent to him a 268 char attempt, but subsequently improved again. I am now at 255 characters, by perl golf rules (newlines count as 1 char). I await the response...
*** [update 24 Jan 2003] Well, again Mtve came up with the goods and provided a 261, then 254 char version. Here is the 254 (I have added two newlines in the code for readability, they are not required or counted):
However, I made a couple of improvements, and 252 is the best Ruby version now:
Does Ruby win? If Mtve improves again, then no I fear. I can't see any areas that I can improve the Ruby version further.
*** [update 27 Jan 2003] That said, I finally figured out how I could factor the recurrent n<< out, and saved three bytes doing it.
Also, in-lining the 'i' array saves another four - this was obvious, and I should have done it earlier.
Using putc drops me another two, and moving some code around saved one last byte.
So I'm now somewhat miraculously well under the 250 barrier at 242.
What's more, just for fun, I made it into a valid ETA program (it just waits for a char then exits, but it is valid).
Mtve has sent me a 233 character perl program. He has altered strategy and used much of the algorithm I am using in Ruby. I would be well beaten by this except for the fact that it is not, at present, a valid interpreter because of a problem handling regex special characters in the input.
I am waiting for him to come up with a fix, but until then Ruby is the leader.
*** [update 28 Jan 2003] Stone the crows, just when I thought nothing further could be done to the program to improve it I found a way to chop another seven characters. I also fixed a little bug in the previous version - quite similar to the one Mtve had!
Here is the best yet at 235 bytes:
*** [update 2 Feb 2003] I studied hard, and found yet another six bytes that were not required.
Here is the 229 character masterpiece:
This must, now, be the smallest possible – although I've thought that before!
Note, it has been pointed out that the program does not work correctly if you use it like this:
This is because of a bug in Ruby – it seems to incorrectly count the input lines from the input when using indirection (matz fixed the bug once I pointed it out, but it will take a while to filter through to a release).
The solution in the mean time is to use the program like this:
*** [update 5 Feb 2003] I shaved just one more byte. I'm now at 228:
*** [update 6 Feb 2003] Mtve has come back with an excellent perl script with 231 characters. He has also pointed out that there is a bug in the way I handle getc - after end of input the I instruction should push -1 onto the stack. Fixing this costs three characters, so I'm now at 231:
Here is Mtve's Perl masterpiece (231 chars):
*** [update March 2003] It seems that this is the limit, and we are both too exhausted to work on this any more.
So it's officially a tie!
One final note - my program works in recent versions of Ruby, but terse features I am using are becoming deprecated as Ruby moves away from some of its Perlish origins.
So there are more and more warning messages, and with Ruby 1.8 these are very intrusive.
I advise running with warnings turned off (
Or is it?
*** [update 1 Apr 2004] A miracle happened - over a year after my last work on this, I just noticed a little improvement - I'm now at 227.
Let's see if Perl/Mtve can improve also.
Improvements in 2007
*** [update 21 Sep 2007] More improvements following correspondence with Darren of darrenks.com
I received a series of emails, ending with the following excellent solution (and I thank Darren very much for the insights and time he took to produce this):
This measures at 218 chars, an amazing improvement of 9. Also, one problem was fixed - Ruby disallows having a string on the right hand side of =~ (since 1.8.something), so the program works again now. Wonderful achievement Darren, thanks.
One thing to note is that the warnings with this version are many. -W0 is definitely needed (as it was with my previous versions also).
So while I was thinking about this, and with renewed energy, I had a good look at the code. I found some tiny improvements of my own. I made two versions - one that will not generate any warnings, and one that generates many warnings.
Firstly the clean version:
Next to see is the unclean, warnings-but-we-don't-care version:
This is an incredible 212 chars. It actually generates an error if you exit by falling off the end of the ETA program, and there happens to be items left on the stack. Well, you should exit by transferring to zero of course.
As always, I don't think there are any more improvements, but I've been wrong so many times before. Write to me if you find one!
*** [update 22 Sep 2007] One byte more from Darren
"Your changes look good, I see one minor improvement: ~-_+=1 instead
What a nice use of the complement operator. And right, those increment and decrement operators would be very useful for us. Here are the two programs with the improvement:
If you are interested in obfuscated Ruby, then this is a good page - there is a nice maze generator in 10 lines (you need to know it takes two arguments - width and height), and also a BrainF*ck implementation.
S.D.Sykes Sep 2007