# Cellular Automata (#134)

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
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 Q. 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
printing to the terminal.

Noticed a typo in the quiz. 1110 is not 30 in binary; 11110 is.

Regards,
Craig

Craig D. <cdemyanovich gmail.com> writes:

Noticed a typo in the quiz. 1110 is not 30 in binary; 11110 is.

binary, so we just
pad the right side with zeros and we have our table.

are these not fractals?

On Aug 10, 2007, at 8:53 AM, Ruby Q. wrote:

“neighborhood” of the cell currently being examined, which includes
binary, so we just
pad the right side with zeros and we have our table.

I’d like to add a little to this quiz description. The cellular
automaton James describes is sometimes referred to as the Wolfram
automaton because Stephen Wolfram has studied and written extensively
on it. There is a good discussion of this problem at

``````  http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
``````

IIRC, the rule 30 automaton is famous for being chaotic. It looks
like this.

John J. wrote:

are these not fractals?

Some are, most aren’t. The majority of rules (as far as I remember -
not written my solution yet ) come up with fairly dull stable
patterns.

On Aug 10, 2007, at 9:49 AM, Gareth A. wrote:

Thanks guys. I’ve updated the web site description.

James Edward G. II

On Aug 11, 2007, at 3:30 AM, Alex Y. wrote:

John J. wrote:

are these not fractals?
Some are, most aren’t. The majority of rules (as far as I remember

• not written my solution yet ) come up with fairly dull stable
patterns.

True, but some of the rules are very interesting.

Rule 30 passes many tests of random number generation, for example.
Mathematica uses that very rule internally in it’s algorithm for
generating large random integers.

James Edward G. II

Here’s my fairly straightforward, no bells-and-whistles solution.

Each state is represented as an Array of Strings. I originally just used
a String, and split() when needed, but keeping it as an Array makes it a
bit faster and does simplify the code in a few places.

transformer() builds a Proc that takes a neighborhood as its argument
(as
an Array of Strings) and returns the transformed cell state (as a
String).
A Hash could have been used instead of a Proc.

step() takes a state (as an Array of Strings), tacks [0,0] onto both
ends,
and calls each_cons(3) to iterate through the neighborhoods, which are
passed to the transformer Proc.

\$ ./cellular_automata.rb -r 110 -s 1 -n 15
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

Here is my solution. No fancy graphics, the kids didn’t give me enough
time for that -Doug Seifert

Ruby Q. wrote:

[…]
This week’s Ruby Q. 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.

not much time so nothing facing here:

require ‘enumerator’

puts(“usage: ruby q134.rb [rule] [count] [start]”) || exit if ARGV.size
!= 3

rule, count = ARGV.shift.to_i, ARGV.shift.to_i
start = *count + ARGV.split(’’).map{|i|i.to_i} + *count

## (0…count).inject(start) do |l, nr| puts l.inject("#{nr}:".rjust(3)){|s, i| s + [’ ', ‘#’][i]} (l[0,1] + l + l[-1,1]).enum_cons(3).map{|a,b,c| rule[a4+b2+c]} end

i doubled the last and first item from each line - this seems to create
more
consistent results with the inverted patterns than just assuming they
are 0:

ruby q134.rb 129 20 1
0: #
1:################### ###################
2:################## # ##################
3:################# #################
4:################ ##### ################
5:############### ### ###############
6:############## ## # ## ##############
7:############# #############
8:############ ############# ############
9:########### ########### ###########
10:########## ## ######### ## ##########
11:######### ####### #########
12:######## ###### ##### ###### ########
13:####### #### ### #### #######
14:###### ## ## ## # ## ## ## ######
15:##### #####
16:#### ############################# ####
17:### ########################### ###
18:## ## ######################### ## ##
19:# ####################### #
20: ###### ##################### ######

cheers

Simon

Ruby Q. wrote:

This week’s Ruby Q. 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.

Slightly different/renamed options and no graphics:

ruby cellular_automaton.rb -r 41 -s 20 -w 30 100100
X X
XXXXXXXXXXXXXXXXXXXXXXX X
X XXXX
XXXXXXXXXXXXXXXXXXXXX X X
X X X XX
X XXXXXXXXXXXXXXXXXX X X
X XX
XXX XXXXXXXXXXXXXXXX X XXXX
X X X X X
X X XXXXXXXXXXXXX X XX
X X X X X
XXXXX XXXXXXXXXXX X X
X X X X X X
X XXX X XXXXXXXXX XXXX
X X X X X
XXX XXXXX XXXXXXX X XX
X X X X X X X
X X XXX X XXXXXXXXX
X X X XXXX
XXXXX XXXXX XXXXXXX X
X X X X X X X XX

== Code

#!/usr/bin/env ruby

# string of 0 and 1.

require ‘getoptlong’
require ‘rdoc/usage’
require ‘enumerator’

# Describes a state in a cellular automaton.

class CellularAutomatonState
attr :cells

private

# All the possible neighbourhoods of size 3.

NEIGHBOURHOODS = [[true, true, true], [true, true, false],
[true, false, true], [true, false, false], [false, true, true],
[false, true, false], [false, false, true], [false, false, false]]

public

# state.

def initialize(rule, initial_state)
@cells = initial_state

``````# Decode the rule into a hash map. The map is then used when
# computing the next state.
booleans = rule.to_s(2).rjust(
NEIGHBOURHOODS.size, '0').split(//).map{ |x| x == '1' }
if booleans.size > NEIGHBOURHOODS.size
raise ArgumentError, 'The rule is too large.'
end
@rules = {}
NEIGHBOURHOODS.each_with_index do |neighbourhood, i|
@rules[neighbourhood] = booleans[i]
end
``````

end

# Updates the automaton one step.

def step!
@new_cells = []
# Regard the endings as false.
([false] + @cells + [false]).each_cons(3) do |neighbourhood|
@new_cells << @rules[neighbourhood]
end
@cells = @new_cells
end

def to_s
@cells.map{ |x| x ? ‘X’ : ’ ’ }.join
end
end

rule = 30
steps = 20
width = 20

# Options

opts = GetoptLong.new(
[’–help’, ‘-h’, GetoptLong::NO_ARGUMENT],
[’–rule’, ‘-r’, GetoptLong::REQUIRED_ARGUMENT],
[’–steps’, ‘-s’, GetoptLong::REQUIRED_ARGUMENT],
[’–width’, ‘-w’, GetoptLong::REQUIRED_ARGUMENT])
opts.each do |opt, arg|
case opt
when ‘–help’: RDoc::usage
when ‘–rule’: rule = arg.to_i
when ‘–steps’: steps = arg.to_i
when ‘–width’: width = arg.to_i
end
end

if ARGV.size != 1
abort “Incorrect usage, see --help”
end

# Turn the provided state into an array of booleans, pad if needed.

cells = ARGV.shift.rjust(width,‘0’).split(//).map!{ |cell| cell == ‘1’ }

# Create the initial state and then step the desired number of times.

state = CellularAutomatonState.new(rule, cells)
puts state.to_s
steps.times do
state.step!
puts state.to_s
end

END

On Aug 12, 2007, at 8:13 AM, Jesse M. wrote:

Here’s my fairly straightforward, no bells-and-whistles solution.

My solution does the required tasks and makes PPM graphics. Here’s
the code:

#!/usr/bin/env ruby -wKU

require “ppm”

require “enumerator”
require “optparse”

options = {:rule => 30, :steps => 20, :cells => “1”, :output => :ascii}

ARGV.options do |opts|
opts.banner = “Usage: #{File.basename(\$PROGRAM_NAME)} [OPTIONS]”

opts.separator “”
opts.separator “Specific Options:”

opts.on( “-r”, “–rule RULE”, Integer,
“The rule for this simulation.” ) do |rule|
raise “Rule out of bounds” unless rule.between? 0, 255
options[:rule] = rule
end
opts.on( “-s”, “–steps STEPS”, Integer,
“The number of steps to render.” ) do |steps|
options[:steps] = steps
end
opts.on( “-c”, “–cells CELLS”, String,
“The starting cells (1s and 0s).” ) do |cells|
raise “Malformed cells” unless cells =~ /\A+\z/
options[:cells] = cells
end
opts.on( “-o”, “–output FORMAT”, [:ascii, :ppm],
“The output format (ascii or ppm).” ) do |output|
options[:output] = output
end

opts.separator “Common Options:”

opts.on( “-h”, “–help”,
“Show this message.” ) do
puts opts
exit
end

begin
opts.parse!
rescue
puts opts
exit
end
end

RULE_TABLE = Hash[ *%w[111 110 101 100 011 010 001 000].
zip((“%08b” % options[:rule]).scan(/./)).flatten ]

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

width = cells.last.length
if options[:output] == :ascii
cells.each { |cell| puts cell.tr(“10”, "X ").center(width) }
else
image = PPM.new( :width => width,
:height => cells.length,
:background => PPM::Color::BLACK,
:foreground => PPM::Color[0, 0, 255],
:mode => “P3” )
cells.each_with_index do |row, y|
row.center(width).scan(/./).each_with_index do |cell, x|
image.draw_point(x, y) if cell == “1”
end
end
image.save(“rule_#{options[:rule]}steps#{options[:steps]}”)
end

END

It requires this tiny PPM library:

#!/usr/bin/env ruby -wKU

# Updated by James Edward G. II from the Turtle Graphics quiz.

class PPM
class Color
def self.
args << args.last while args.size < 3
new(*args)
end

`````` def initialize(red, green, blue)
@red   = red
@green = green
@blue  = blue
end

BLACK = new(0, 0, 0)
WHITE = new(255, 255, 255)

def inspect
"PPM::Color[#{@red}, #{@green}, #{@blue}]"
end

def to_s(mode)
if mode == "P6"
[@red, @green, @blue].pack("C*")
else
"#{@red} #{@green} #{@blue}"
end
end
``````

end

DEFAULT_OPTIONS = { :width => 400,
:height => 400,
:background => Color::BLACK,
:foreground => Color::WHITE,
:mode => “P6” }

def initialize(options = Hash.new)
options = DEFAULT_OPTIONS.merge(options)

`````` @width      = options[:width]
@height     = options[:height]
@background = options[:background]
@foreground = options[:foreground]
@mode       = options[:mode]

@canvas = Array.new(@height) { Array.new(@width) { @background } }
``````

end

def draw_point(x, y, color = @foreground)
return unless x.between? 0, @width - 1
return unless y.between? 0, @height - 1

`````` @canvas[y][x] = color
``````

end

# Bresenham's line algorithm - Wikipedia

def draw_line(x0, y0, x1, y1, color = @foreground)
steep = (y1 - y0).abs > (x1 - x0).abs
if steep
x0, y0 = y0, x0
x1, y1 = y1, x1
end
if x0 > x1
x0, x1 = x1, x0
y0, y1 = y1, y0
end
deltax = x1 - x0
deltay = (y1 - y0).abs
error = 0
ystep = y0 < y1 ? 1 : -1

`````` y = y0
(x0..x1).each do |x|
if steep
draw_point(y, x, color)
else
draw_point(x, y, color)
end
error += deltay
if 2 * error >= deltax
y     += ystep
error -= deltax
end
end
``````

end

def save(file)
File.open(file.sub(/.ppm\$/i, “”) + “.ppm”, “w”) do |image|
image.puts @mode
image.puts “#{@width} #{@height} 255”

``````   @canvas.each do |row|
pixels = row.map { |pixel| pixel.to_s(@mode) }
image.send( @mode == "P6" ? :print : :puts,
pixels.join(@mode == "P6" ? "" : " ") )
end
end
``````

end
end

END

James Edward G. II

On 8/11/07, Morton G. [email protected] wrote:
[snip]

``````  http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
``````

IIRC, the rule 30 automaton is famous for being chaotic. It looks
like this.

Above picture made with Mathematica, not Ruby.

I don’t know if posting images is a good thing, but here is mine.
Compressed as much as possible sorry: I wrote it in objc.

I added another command-line switch to specify the output mapping
(defaulting to ’ ’ and ‘X’ like the example.)

#!/usr/bin/env ruby

require ‘optparse’
require ‘enumerator’

ruleset = 0
steps = 1
cells = [‘0’]
output_map = ’ X’

OptionParser.new do |opts|
opts.on("-r", “–ruleset RULESET”, Integer, “Ruleset specification”)
{|r| ruleset = r }
opts.on("-s", “–steps STEPS”, Integer, “Number of steps”) {|s| steps
= s}
opts.on("-c", “–cells CELLS”, “Initial cells string”) {|c| cells =
c.split(//)}
opts.on("-m", “–map MAP”, “Character map for output”) {|m| output_map
= m}
end.parse!(ARGV)

rule = {}
0.upto(7) {|i| rule[sprintf("%03b", i).split(//)] = ruleset[i].to_s}

width = steps * 2 + cells.length + 1
0.upto(steps) do
puts cells.join.tr(‘01’, output_map).center(width)
cells = ([‘0’,‘0’] + cells + [‘0’,‘0’]).enum_cons(3).map {|l| rule[l]}
end

Here is my solution to this week’s quiz.
I have created pasties for the full code:
Cellular Automata program: Parked at Loopia
RMagick Graphical Extention: Parked at Loopia

Here is a quick walk-though of the core logic. First, I included
everything
in its own class:
class CellularAutomata

I created a method to compute a single iteration (Generation) of the
cellular automata. The method takes a State array and rule number, and
builds the next state (generation) of the cells:

def compute_generation(state, rule)
result = Array.new

``````# Pad front and back of state to compute boundaries
state.insert(0,state).flatten!
state.push(state[-1])

# Find the 3 digit binary num at each index, and build a list of the
``````

corresponding bits
# Uses built-in ruby functionality to index individual bits
(state.size - 2).times do |i|
result.push(rule[convert_to_dec(state.slice(i, 3), 2)])
end

``````result
``````

end

This method preps the input and runs a series of generations:

def run(rule, steps, state)
# Pad state to width of board
(steps).times do
state.insert(0, 0)
state.push(0)
end

``````result = [].push(Array.new(state))

steps.times do
state = compute_generation(state, rule)
result.push(Array.new(state))
end

result
``````

end

Here is a boilerplate method to convert an array of numbers in the given
base (binary in this program) to a decimal number. There probably is a
better way to do this in ruby:

def convert_to_dec(num_array, base)
result, place = 0, 0
for digit in num_array.reverse
result = result + digit * (base ** place)
place = place + 1
end
result
end

And finally, here is the code to parse command line args and print
everything to console:
if ARGV.size == 3
cell = CellularAutomata.new
for generation in cell.run(ARGV.to_i, ARGV.to_i,
ARGV.split(“”).map{|i| i.to_i })
print “\n”, generation
end
else
print “Usage: Cellular_Automata.rb rule_number number_of_steps
initial_state”
end

Here is a sample run:
Cellular_Automata.rb 30 10 1

000000000010000000000
000000000111000000000
000000001100100000000
000000011011110000000
000000110010001000000
000001101111011100000
000011001000010010000
000110111100111111000
001100100011100000100
011011110110010001110
110010000101111011001

A few of the more interesting pictures generated by the RMagick class
are
available online:

Thanks,

Justin

James G. wrote:

The three rules of Ruby Q.:

Here’s my solution. Note: I saw no reason to make the output right
justified, so mine is left justified. Not sure if this matters much…

Sample output:

drew\$ ruby cell.rb 110 20 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

My code:

# author: drew olson

class CellAutomata
require ‘enumerator’

def initialize rule
raise ArgumentError if rule < 0 || rule > 255
@rule_table = build_table rule
end

# simulate a given number of generations. return in string format

def simulate cur_gen, num_gen
raise ArgumentError if num_gen < 0
if num_gen == 0
format_gen(cur_gen)
else
format_gen(cur_gen) + simulate(build_new_gen(cur_gen),num_gen-1)
end
end

private

# format a generation for printing

def format_gen gen
gen.gsub(/0/,’ ').gsub(/1/,‘X’).strip+"\n"
end

# build new generation based on current generation

def build_new_gen gen
new_gen = ‘’
(‘00’+gen+‘00’).split(//).each_cons(3) do |group|
new_gen += @rule_table[group.join(’’).to_i(2)]
end
new_gen
end

# build rule table based on a number seed

def build_table rule
rule_string = ("%08d" % rule.to_s(2)).split(//).reverse.to_s
(0…7).inject({}) do |rule_table,i|
rule_table[i] = rule_string[i,1]
rule_table
end
end
end

# create automation based on command line args

if FILE == \$0 || true
cell = CellAutomata.new(ARGV.to_i)
puts cell.simulate(ARGV,ARGV.to_i)
end

Drew O. wrote:

James G. wrote:

The three rules of Ruby Q.:

Here’s my solution. Note: I saw no reason to make the output right

Whoops, shouldn’t have stripped the output. Updated:

# author: drew olson

class CellAutomata
require ‘enumerator’

def initialize rule
raise ArgumentError if rule < 0 || rule > 255
@rule_table = build_table rule
end

# simulate a given number of generations. return in string format

def simulate cur_gen, num_gen
raise ArgumentError if num_gen < 0
if num_gen == 0
format_gen(cur_gen)
else
format_gen(cur_gen) + simulate(build_new_gen(cur_gen),num_gen-1)
end
end

private

# format a generation for printing

def format_gen gen
gen.gsub(/0/,’ ').gsub(/1/,‘X’)+"\n"
end

# build new generation based on current generation

def build_new_gen gen
new_gen = ‘’
(‘00’+gen+‘00’).split(//).each_cons(3) do |group|
new_gen += @rule_table[group.join(’’).to_i(2)]
end
new_gen
end

# build rule table based on a number seed

def build_table rule
rule_string = ("%08d" % rule.to_s(2)).split(//).reverse.to_s
(0…7).inject({}) do |rule_table,i|
rule_table[i] = rule_string[i,1]
rule_table
end
end
end

# create automation based on command line args

if FILE == \$0 || true
cell = CellAutomata.new(ARGV.to_i)
puts cell.simulate(ARGV,ARGV.to_i)
end

James G. wrote:

On Aug 13, 2007, at 8:17 AM, Drew O. wrote:

Note: I saw no reason to make the output right
justified, so mine is left justified. Not sure if this matters much…

I don’t think the rules should be justified in either direction. The
pattern dictates how they expand.

Your code draws some rules differently, for example:

James -

Thanks for the follow up. I may be totally missing something, but I’m
confused where the left padding comes from in the first generation in

On Aug 13, 2007, at 8:17 AM, Drew O. wrote:

Note: I saw no reason to make the output right
justified, so mine is left justified. Not sure if this matters much…

I don’t think the rules should be justified in either direction. The
pattern dictates how they expand.

Your code draws some rules differently, for example:

\$ ruby -I solutions/James\ Edward\ Gray\ II/ solutions/James\ Edward
Gray\ II/cellular_automaton.rb -r 2
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
\$ ruby solutions/Drew\ Olson/cell.rb 2 20 1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

James Edward G. II