Asp Forum - [QUIZ] Cellular Automata (#134

James Gray

8/10/2007 12:54:00 PM

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

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.

25 Answers

Craig Demyanovich

8/10/2007 1:15:00 PM

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.

John Joyce

8/11/2007 2:13:00 AM

are these not fractals?

Alex Young

8/11/2007 8:31:00 AM

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

James Gray

8/11/2007 3:50:00 PM

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.
>
>
> In addition, you'll be padding the left side, Shirley?

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

James Edward Gray II

James Gray

8/11/2007 4:07:00 PM

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

Jesse Merriman

8/12/2007 1:14:00 PM

Content-Type: Multipart/Mixed;
boundary="Boundary-00=_pdwvGh1C3FtoFsb"
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
jessemerriman@warpmail.net
http://www.jessemer...

Simon Kröger

8/12/2007 1:52:00 PM

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

Andreas Launila

8/12/2007 2:24:00 PM

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

James Gray

8/12/2007 4:22:00 PM

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", :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][x] = color
end

# http://en.wikipedia.org/wiki/Bresenham%27s_line...
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

Zed Lopez

8/13/2007 7:15:00 AM

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

comp.lang.ruby

[QUIZ] Cellular Automata (#134

James Gray

Craig Demyanovich

John Joyce

Alex Young

James Gray

James Gray

Jesse Merriman

Simon Kröger

Andreas Launila

James Gray

Zed Lopez

x Login to ForumsZone