From: Ruby Quiz <james@...>
Date: 2007-08-10T21:53:52+09:00
Subject: [QUIZ] Cellular Automata (#134)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Most of us have probably heard of Conway's Game of Life, but there are other
cellular automata that are equally interesting.  In fact, there is a group of
256 one-dimensional cellular automata that are quite easy to simulate but still
fun to observe.

To simulate these elementary cellular automata, you first need to construct a
rule table.  This table is a description of the changes that happen in each
discreet step of time.  Here's the table for the "rule 30" automaton:

	+-----------------------------------------------------------------+
	| Neighborhood    | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
	+-----------------------------------------------------------------+
	| New Center Cell |  0  |  0  |  0  |  1  |  1  |  1  |  1  |  0  |
	+-----------------------------------------------------------------+

The first row is the same for this whole family of automata.  It represents the
"neighborhood" of the cell currently being examined, which includes the cell
itself and one cell to either side of it.  The current values of those cells,
ones being on and zeros being off, can be used to determine the new value for
this cell in the next discreet step of time.

That new value comes from the bottom row.  This row is generated by taking the
rule number, 30 in this case, in binary form.  1110 is 30 in binary, so we just
pad the right side with zeros and we have our table.

Once you have the rules, you just apply them to a string of cells.  For example,
given the cells:

	11001

The rule 30 table creates:

	1101111

Note that cells outside of what I had were off (zeros) for the purposes of
calculating neighborhoods.

This week's Ruby Quiz is to write a program that accepts up to three parameters:
the rule as an integer in decimal, the number of steps to simulate, and the
starting state of the cells as a String of ones and zeros.  Here's a sample run
of my solution using all three options:

	$ ruby cellular_automaton.rb -r 110 -s 20 -c 1
	                    X                    
	                   XX                    
	                  XXX                    
	                 XX X                    
	                XXXXX                    
	               XX   X                    
	              XXX  XX                    
	             XX X XXX                    
	            XXXXXXX X                    
	           XX     XXX                    
	          XXX    XX X                    
	         XX X   XXXXX                    
	        XXXXX  XX   X                    
	       XX   X XXX  XX                    
	      XXX  XXXX X XXX                    
	     XX X XX  XXXXX X                    
	    XXXXXXXX XX   XXX                    
	   XX      XXXX  XX X                    
	  XXX     XX  X XXXXX                    
	 XX X    XXX XXXX   X                    
	XXXXX   XX XXX  X  XX                    

To impress your friends, try adding in support for graphic output in addition to
printing to the terminal.