Golfing Rule 110

Background.md

What is Rule 110?

Rule 110 is an algorithm for a cellular automaton. The automaton works on of an infinite tape of 1s and 0s. It has a write head that can write to a specific position on the tape, and a read head that reads the position under the write head as well as the positions to either side. The set of three values read determines the value written by the write head according to the following rules:

Values Read	111	110	101	100	011	010	001	000
Value Written	0	1	1	0	1	1	1	0

If you notice, the value to write for each set of three values read corresponds to the position of the bits in the binary representation of the number 110. Hence, the name of the rule. Wikipedia has more information here.

Why is Rule 110 Special?

If you iterate through the possible rules, the large majority of them are uninteresting. Some don't create any patterns, and a handful create variations on the Sierpinski triangle A few, however, create quite intricate patters. Only Rule 110, however, has shown to be Turing complete. That means that, given a starting state for the tape, in some number of steps you can eventually find every possible pattern. In other words, if you wanted to write a program that took some input, and generated some output – any output – using Rule 110 you would only need to specify the number of iterations to run.

Explanation.md

How does it work?

The core of both golf solutions lies in the following Ruby snippet: t=[0,0,*t,0,0].each_cons(3).map{|b|n.to_s(2)[-(b*"").to_i(2)-1]||0}. Written out more clearly, this becomes:

tape = [0, 0, *tape, 0, 0].each_cons(3).map do |bits|
  rule_bits = rule_no.to_s(2).reverse
  rule_pos = bits.join.to_i(2)
  write_bit = rule_bits[rule_pos] || 0
  write_bit
end

That is, we have to take the rule number, use Integer#to_s(base) to turn it into a string of bits (base 2), and reverse it so we can index into the bits using string position. (Alternatively, we can index the string backwards with negative indices.) Which string position (bit) to write depends on the 3 consecutive bits surrounding the write position (Enumerable#each_cons). We take these three values, join them together to form a bit string (Array#join), and then convert them to an integer using String#to_i(base), again using base 2.

If we want to grow the tape (i.e. simulate an infinite tape), we need to append 2 zeros on either end of the array forming the tape. At the very least we need to append one zero on the ends so that the first and last position have 3 consecutive bits to use to determine the write bit.

roguesgolf.rb

# Press return to step through all of the rules. Run using "ruby -ne".
n||=1;t=1;99.downto(0){|i|puts" "*i+((t=[0,0,*t,0,0].each_cons(3).map{|b|n.to_s(2)[-(b*"").to_i(2)-1]||0})*"").tr("10","# ")};n+=1

rule110.rb

# Uses the first command line argument as a seed, and applies rule 110. Run using "ruby -e" and passing a string argument.
t=$*[0].unpack("B*")[0].chars;150.times{$><<((t=[0,*t,0].each_cons(3).map{|b|"01110110"[(b*"").to_i(2)]})*"").tr("10","# ")+"\n"}