[QUIZ] Cellular Automata (#134)

ruby-talk
1

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.

2

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

Regards,
Craig

···

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

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.

3

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

      Elementary Cellular Automaton -- from Wolfram MathWorld

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

···

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

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. 11110 is 30 in binary, so we just
pad the right side with zeros and we have our table.

4

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

cellular_automata.rb (1.5 KB)

···

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

5

Here is my solution. No fancy graphics, the kids didn't give me enough time for that :wink:

-Doug Seifert

automaton.rb (3.66 KB)

6

Ruby Quiz wrote:

[...]
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.

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 = [0]*count + ARGV[0].split('').map{|i|i.to_i} + [0]*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[a*4+b*2+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

7

Ruby Quiz wrote:

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.

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
# == Usage

···

#
# cellular_automaton [OPTIONS] CELLS
#
# -h, --help:
# show help
#
# -r, --rule RULE:
# specified the rule to use as a decimal integer, defaults to 30
#
# -s, --steps STEPS:
# specifies the number of steps that should be shown, defaults to 20
#
# -w, --width WIDTH:
# specifies the number of cells that should be shown per step,
# defaults to 20
#
# CELLS: The initial cell state that should be used. Must be given as a
# 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

  # Creates a new state using the specified +rule+ given in decimal.
  # +inital_state+ holds an array of booleans describing the initial
  # 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

# Defaults
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__

--
Andreas Launila

8

Here is my solution to this week's quiz.
I have created pasties for the full code:
Cellular Automata program: http://pastie.caboo.se/87013
RMagick Graphical Extention: http://pastie.caboo.se/87015

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[0]).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[0].to_i, ARGV[1].to_i,
ARGV[2].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

···

On 8/10/07, Ruby Quiz <james@grayproductions.net> wrote:

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.

9

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

···

--
Posted via http://www.ruby-forum.com/.

10

James Gray wrote:

The three rules of Ruby Quiz:

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:

# file: cell.rb
# 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[0].to_i)
  puts cell.simulate(ARGV[2],ARGV[1].to_i)
end

···

--
Posted via http://www.ruby-forum.com/\.

11

James Gray wrote:

The three rules of Ruby Quiz:

My _working_ solution :slight_smile: Thanks for the clarifications James. 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

Code:

# file: cell.rb
# 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
    @max_gen ||= num_gen+1
    raise ArgumentError if num_gen < 0
    if num_gen == 0
      format_gen(cur_gen,num_gen)
    else
      format_gen(cur_gen,num_gen) +
simulate(build_new_gen(cur_gen),num_gen-1)
    end
  end

  private

  # format a generation for printing
  def format_gen gen,num_gen
    ("%0#{@max_gen+(@max_gen-num_gen)}d" % 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[0].to_i)
  puts cell.simulate(ARGV[2],ARGV[1].to_i)
end

···

--
Posted via http://www.ruby-forum.com/\.

12

I didn't have much time this weekend, but I had a bit more than
previous weeks, so here's my solution. The goal here was "minimal
coding". As a result, the rule-evaluation statement could charitably
be described as "terse". It just does X's and spaces as in the quiz
description.

#!ruby
require 'optparse'

rule = 30
initial_pattern = '1'
steps = 10
OptionParser.new do |opts|
  opts.banner = "Usage: ca.rb [opts]"
  opts.on("-r", "--rule N", Integer, "Rule number") do |n|
    rule = n
  end
  opts.on("-s", "--states N", Integer,
                "Number of states (default 10)") do |s|
    steps = s
  end
  opts.on("-c", "--cells BITSTRING", String,
                "Initial cell pattern as 0s and 1s") do |s|
    initial_pattern = s
  end
end.parse!

# This ensures some padding for those nasty odd rules
pattern = '0' * steps + initial_pattern + '0' * steps;
(steps-1).times {
  puts pattern.tr('01',' X')
  ppat = pattern[0,1] + pattern + pattern[-1,1]
  pattern = (1..pattern.size).inject(""){|s,i|
    s << ((rule >> [ppat[i-1,3]].pack('b3')[0])&1).to_s
  }
}
puts pattern.tr('01',' X')

__END__

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.to_a.last )
       puts "s=%q(#{s})",s.to_a.last

13

Cleaned up a couple of things in my program, mainly using to_i to convert
from binary:

class CellularAutomata

  # Compute a single iteration (Generation) of the cellular automata
  # Inputs: State array, rule array
  # Returns: New State array
  def compute_generation(state, rule)
    result = Array.new

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

    # Build a list of the corresponding bits for each 3 digit binary number
    (state.size - 2).times do |i|
      result.push(rule[state.slice(i, 3).join.to_i(2)])
    end

    result
  end

  # Run 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
end

if ARGV.size == 3
  cell = CellularAutomata.new
  for generation in cell.run(ARGV[0].to_i, ARGV[1].to_i,
ARGV[2].split("").map{|i| i.to_i })
    print "\n", generation
  end
else
  print "Usage: Cellular_Automata.rb rule_number number_of_steps initial_state"
end

A pastie of it is here: http://pastie.caboo.se/87535
Thanks,

Justin

···

On 8/10/07, Ruby Quiz <james@grayproductions.net > wrote:

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.

14

My solution, late-ish but not too late:

#!/usr/bin/env ruby

require 'optparse'

cells = nil
steps = nil
rule = nil
OptionParser.new do |opts|
  opts.on('-c', '--cells [CELLS]', 'A string representing the initial
cell state as a series of 1s and 0s') do |cells_opt|
    cells = cells_opt
  end
  opts.on('-s', '--steps [STEPS]', Integer, 'The number of steps to
simulate') do |steps_opt|
    steps = steps_opt.to_i
  end
  opts.on('-r', '--rule [RULE]', Integer, 'The rule as a decimal
integer') do |rule_opt|
    rule = ('%b' % rule_opt)[0,8].rjust(8, '0')
  end
  opts.parse!(ARGV)
end

rule_table = {}
(0..7).to_a.reverse.collect { |n| '%b' % n }.zip(rule.split('')) do |
n, r|
  rule_table[n.rjust(3, '0')] = r
end

cells = ('0' * steps) + cells + ('0' * steps)

puts cells.gsub(/1/, 'X').gsub(/0/, ' ')
steps.times do
  check_cells = "0#{cells}0" # pad with zeroes for ease of checking
  new_cells = ''

  (0...cells.length).each do |i|
    neighborhood = check_cells[i, 3]
    new_cells << rule_table[neighborhood]
  end
  cells = new_cells
  puts cells.gsub(/1/, 'X').gsub(/0/, ' ')
end

Cassady:~/stuff yossef$ ./cellular.rb -s 20 -c 1 -r 110
                    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

···

On Aug 10, 7:53 am, Ruby Quiz <ja...@grayproductions.net> wrote:

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 othercellularautomata that are equally interesting. In fact, there is a group of
256 one-dimensionalcellularautomata that are quite easy to simulate but still
fun to observe.

To simulate these elementarycellularautomata, 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.

15

Craig Demyanovich <cdemyanovich <at> 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.

In addition, you'll be padding the left side, Shirley?

16

are these not fractals?

17

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[01]+\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 Gray II from the Turtle Graphics quiz.

class PPM
   class Color
     def self.(*args)
       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] = 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 Gray II

···

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

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

18

[snip]

      Elementary Cellular Automaton -- from Wolfram MathWorld

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 :slight_smile:

sorry: I wrote it in objc.

···

On 8/11/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:

--
Simon Strandgaard
http://opcoders.com/

19

Drew Olson wrote:

James Gray wrote:

The three rules of Ruby Quiz:

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

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

# file: cell.rb
# 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[0].to_i)
  puts cell.simulate(ARGV[2],ARGV[1].to_i)
end

···

--
Posted via http://www.ruby-forum.com/\.

20

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

James Edward Gray II

···

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

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