# [QUIZ] Cellular Automata (#134)

Discussion in 'Ruby' started by Ruby Quiz, Aug 10, 2007.

1. ### Ruby QuizGuest

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

printing to the terminal.

Ruby Quiz, Aug 10, 2007

2. ### Craig DemyanovichGuest

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.

Craig Demyanovich, Aug 10, 2007

3. ### John JoyceGuest

are these not fractals?

John Joyce, Aug 11, 2007
4. ### Alex YoungGuest

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

--
Alex

Alex Young, Aug 11, 2007
5. ### James Edward Gray IIGuest

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

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

>
>

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

James Edward Gray II

James Edward Gray II, Aug 11, 2007
6. ### James Edward Gray IIGuest

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

> John Joyce 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 Gray II

James Edward Gray II, Aug 11, 2007
7. ### Jesse MerrimanGuest

[SOLUTION][QUIZ] Cellular Automata (#134)

--Boundary-00=_pdwvGh1C3FtoFsb
Content-Type: Multipart/Mixed;
boundary="Boundary-00=_pdwvGh1C3FtoFsb"

--Boundary-00=_pdwvGh1C3FtoFsb
Content-Type: text/plain;
charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--
Jesse Merriman

http://www.jessemerriman.com/

--Boundary-00=_pdwvGh1C3FtoFsb
Content-Type: application/x-ruby;
name="cellular_automata.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="cellular_automata.rb"

#!/usr/bin/env ruby
# Ruby Quiz 134: Cellular Automata

require 'enumerator'
require 'getoptlong'

Draw = { :blank => ' ', '0' => ' ', '1' => 'X' }
Edge = [0, 0]
NeighborhoodSize = 3

# Build a Proc that takes a neighborhood as its argument and returns the
# transformed cell state.
def transformer rule_num
rule = rule_num.to_s 2
rule = ('0' * (2**NeighborhoodSize - rule.length) + rule).reverse.split(//)
lambda { |hood| rule[hood.join.to_i(2)] }
end

# Takes the current state and a transformation Proc, and returns the next
# state.
def step state, trans
new_state = []

(Edge + state + Edge).each_cons(NeighborhoodSize) do |hood|
new_state << trans[hood]
end

new_state
end

# Outputs the current state. The current step number and total step number are
# needed to calculate how far to indent.
def puts_state state, step, total_steps
puts Draw[:blank] * (total_steps - step) + state.map { |x| Draw[x] }.join
end

if __FILE__ == \$0
Opts = GetoptLong.new(
[ '--rule', '-r', GetoptLong::REQUIRED_ARGUMENT ],
[ '--state', '-s', GetoptLong::REQUIRED_ARGUMENT ],
[ '--steps', '-n', GetoptLong::REQUIRED_ARGUMENT ] )

# defaults
rule = 110
state = %w{ 1 }
steps = 20

Opts.each do |opt, arg|
case opt
when '--rule'; rule = arg.to_i
when '--state'; state = arg.split(//)
when '--steps'; steps = arg.to_i
end
end

trans = transformer(rule)

puts_state state, 0, steps
steps.times do |s|
state = step(state, trans)
puts_state state, s+1, steps
end
end

--Boundary-00=_pdwvGh1C3FtoFsb--
--Boundary-00=_pdwvGh1C3FtoFsb--

Jesse Merriman, Aug 12, 2007
8. ### Simon KrögerGuest

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 + [' ', '#']}
(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

Simon Kröger, Aug 12, 2007
9. ### Andreas LaunilaGuest

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

Andreas Launila, Aug 12, 2007
10. ### James Edward Gray IIGuest

Re: [SOLUTION][QUIZ] Cellular Automata (#134)

On Aug 12, 2007, at 8:13 AM, Jesse Merriman 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", utput => :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, pm],
"The output format (ascii or ppm)." ) do |output|
options[utput] = 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[utput] == :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][x] = color
end

# http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
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" ? rint : uts,
pixels.join(@mode == "P6" ? "" : " ") )
end
end
end
end

__END__

James Edward Gray II

James Edward Gray II, Aug 12, 2007
11. ### Zed LopezGuest

Re: Cellular Automata (#134)

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

Zed Lopez, Aug 13, 2007
12. ### Drew OlsonGuest

Re: Cellular Automata (#134)

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

Drew Olson, Aug 13, 2007
13. ### Drew OlsonGuest

Re: Cellular Automata (#134)

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

Drew Olson, Aug 13, 2007
14. ### James Edward Gray IIGuest

Re: Cellular Automata (#134)

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

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 Gray II

James Edward Gray II, Aug 13, 2007
15. ### Drew OlsonGuest

Re: Cellular Automata (#134)

James Gray wrote:
> 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...

>
> 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
--
Posted via http://www.ruby-forum.com/.

Drew Olson, Aug 13, 2007
16. ### James Edward Gray IIGuest

Re: Cellular Automata (#134)

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

> James Gray wrote:
>> 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...

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

The first row isn't padded. It's that the later rows push it over.
I started with:

X

Then Rule 2 fills the cell down and to the left:

X
X

And again:

X
X
X

Make sense now?

James Edward Gray II

James Edward Gray II, Aug 13, 2007
17. ### Drew OlsonGuest

Re: Cellular Automata (#134)

James Gray wrote:
>
> Make sense now?
>
> James Edward Gray II

Ah yes, that makes perfect sense, thanks for the insight.
--
Posted via http://www.ruby-forum.com/.

Drew Olson, Aug 13, 2007
18. ### Drew OlsonGuest

Re: Cellular Automata (#134)

James Gray wrote:
> The three rules of Ruby Quiz:

My _working_ solution 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 = 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/.

Drew Olson, Aug 13, 2007
19. ### Guest

Re: Cellular Automata (#134)

A short but hopefully sweet solution:

#!/usr/bin/env ruby

require 'enumerator'
require 'optparse'

rule = 110
steps = 20
cells = 1

OptionParser.new do |opts|
opts.on("-r RULE", Integer) {|rule|}
opts.on("-s STEPS", Integer) {|steps|}
opts.on("-c CELLS", Integer) {|cells|}
end.parse!

cells = cells.to_s(2)

steps.times do
puts cells.gsub('0', ' ').gsub('1', 'X')

cells = "00#{cells}00".split(//).enum_foreach_cons, 3)
cells = cells.map {|neighborhood|
rule[neighborhood.join.to_i(2)] }.join
end

, Aug 13, 2007
20. ### Simon KrögerGuest

Re: Cellular Automata (#134)

wrote:
> A short but hopefully sweet solution:
>
> [...]

Sweet indeed, i like especialy the to_i(2), didn't thought about that.
But running your solution with rule 145 gave me

X
X
XX X
X X
XXX X X
X X X X
XX X X X
XXX X X X
XXX X X X X X
X X X X X X
XX XXX X X X X
XXX X X X X X X
XXX X X X X X X X
X X XXX X X X X X
XX XXX X X X X X X X
XXX X X X X X X X X
XXX X X XXX X X X X X X
X X XXX X X X X X X X X
XX XXX X X X X X X X X X
XXX X X XXX X X X X X X X

While my solution produced

0: X
1:XXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXX
2:XXXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXXXXXXX
3:XXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXXXXXX
4:XXXXXXXXXXXXXXXX XX X XXXXXXXXXXXXXXXXX
5:XXXXXXXXXXXXXXX X X XXXXXXXXXXXXXXXX
6:XXXXXXXXXXXXXX XXX X X XXXXXXXXXXXXXXX
7:XXXXXXXXXXXXX X X X X XXXXXXXXXXXXXX
8:XXXXXXXXXXXX XX X X X XXXXXXXXXXXXX
9:XXXXXXXXXXX XXX X X X XXXXXXXXXXXX
10:XXXXXXXXXX XXX X X X X X XXXXXXXXXXX
11:XXXXXXXXX X X X X X X XXXXXXXXXX
12:XXXXXXXX XX XXX X X X X XXXXXXXXX
13:XXXXXXX XXX X X X X X X XXXXXXXX
14:XXXXXX XXX X X X X X X X XXXXXXX
15:XXXXX X X XXX X X X X X XXXXXX
16:XXXX XX XXX X X X X X X X XXXXX
17:XXX XXX X X X X X X X X XXXX
18:XX XXX X X XXX X X X X X X XXX
19:X X X XXX X X X X X X X X XX
20: XX XXX X X X X X X X X X X

Anyone who can confirm one of these as 'correct' ?

cheers

Simon

Simon Kröger, Aug 13, 2007