From: Ruby Quiz <james@...>
Date: 2007-08-16T23:18:04+09:00
Subject: [SUMMARY] Cellular Automata (#134)

I chose this quiz because I felt it was easy and interesting.  It seems the jury
is still out on the easy aspect though.  I believe there were only two correct
solution this week.  Most of them had problems with at least some rules,
including my own code.  Let's have a look at what went wrong.

The issue is that any rule which sets the one's bit, creates a case where 000
activates the middle cell.  Since all cells not on are off and our area of cells
is theoretically infinite in width, that means those rules create long strands
of active cells on the very first step.

This is only a problem because many of us tried a shortcut like my own code of:

	options[:steps].times do
	  cells << "00#{cells.last}00".scan(/./).
	                               enum_cons(3).
	                               inject("") { |nc, n| nc + RULE_TABLE[n.join] }
	end

However, adding two zeros to either end is not enough to properly display these
patterns.

A better approach is to create a viewing window of the cell space large enough
to show the interesting parts of the pattern.  We will get the idea of the
infinite spans when we see the cells running off the edges of such a window.

It was Simon Kr旦ger who pointed out these issues in the discuss and I believe
his solution was the first correct submission, so let's take a peek at that
code.  Here's the setup:

	require 'optparse'
	
	rule, steps, cells = 145, 20, '1'
	
	OptionParser.new do |opts|
	  opts.on("-r RULE", Integer) {|rule|}
	  opts.on("-s STEPS", Integer) {|steps|}
	  opts.on("-c CELLS", String) {|cells|}
	end.parse!
	
	# ...

You can see Simon require the OptionParser library here and put it to work. 
Take a close look at just how the parameters are assigned though, because the
code is tricky.

First, some defaults are setup in normal variables.  Then the OptionParser code
gets run, passing the user's settings into blocks that don't seem to do anything
with the values.  Note though that those block variables have the same names as
the variables where the defaults were placed.  In Ruby 1.8.x this will actually
change the value of the outer variable.

This is probably a good habit to start breaking now, if you catch yourself using
it.  A future version of Ruby will change these variable assignment rules and
break code like the above.

Now that the variables are assigned, Simon creates the current row of cells:

	# ...
	
	size = steps + cells.size + steps
	line = cells.center(size, '0')
	
	# ...

This is just the starting cells padded with zeros.  The key though is the amount
of padding.  There are only two cases for how the cells grow.  We've talked
about the infinite growth for rules with the one's bit on already, but all other
rules can growth at most one cell in either direction each step.  That's the
padding Simon adds, step zeros to either side.

Now we are ready for the application code:

	# ...
	
	steps.times do
	  puts line.tr('01', ' X')
	  widened = line[0, 1] + line + line[-1, 1]
	  line = (0...size).map{|i| rule[widened[i, 3].to_i(2)]}.join
	end

This code loops over the requested number of steps.  At each step, it prints the
current row of cells.

Now the widening step is another clever trick.  Remember, we have two growth
rates, one cell at a time and infinite growth.  In the first case, we will have
zeros at both ends and beyond that there should be more zeros.  In the latter
case, all the cells on the edges will be ones to represent the infinite growth. 
Beyond those would be more ones.  By expanding the grid with what is already on
each end, both cases are covered.

The final line of the iterator does the actual change of cells.  It walks the
widened row, but takes the cells three at a time.  This will drop the two extra
cells at the end back off and give us the proper row length.

The actual application of the rule is done here with bit indexing.  By treating
the three cells as a bit pattern and converting them to an Integer, we get the
index for the rule that will fetch the proper zero or one for that pattern.

You may want to work through this code with a pencil and paper until it all
clicks.  I did.  There's a lot going on in that tiny bit of code.

My thanks to all of the others who submitted as well.  These other solutions
were interesting as well, despite my claims that they weren't completely
correct.  Most of them worked on all of the rules that didn't expand infinitely
and that includes the interesting rules.  Do browse through those.

Tomorrow we will fiddle with with an Erlang problem I found interesting...