From: Justin Ethier <justin.ethier@...>
Date: 2007-08-13T04:29:51+09:00
Subject: Re: [QUIZ] Cellular Automata (#134)

------=_Part_9219_11345197.1186946995889
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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:
http://justin.ethier.googlepages.com/134-cellularautomatapictures

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

------=_Part_9219_11345197.1186946995889--