Cellular Automata (#134)

Ruby
21

James G. wrote:

Make sense now?

James Edward G. II

Ah yes, that makes perfect sense, thanks for the insight.

22

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

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

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

23

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_for(:each_cons, 3)
cells = cells.map {|neighborhood|
rule[neighborhood.join.to_i(2)] }.join
end

24

James G. wrote:

The three rules of Ruby Q.:

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

25

On Aug 13, 2007, at 5:00 PM, Simon Kröger wrote:

XX X
X X XXX X X X X X
1:XXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXX
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

I believe your code is correct and mine makes the same mistake as
alpha.chen’s code.

James Edward G. II

26

[email protected] 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

27

On Aug 13, 3:12 pm, James Edward G. II [email protected]
wrote:

I believe your code is correct and mine makes the same mistake as
alpha.chen’s code.

Forgive me for being dense, but I can’t seem to figure out what the
mistake is. When I do it by hand, I get the same result as when I run
the script:

145 = 10010001b

[0 0]1[0 0]
[0 0]0 0 1[0 0]
1 1 0 0 1

Alpha Chen

28

James Edward G. II wrote:

…00000000000000000000100000000000000000000…

All of those 000 neighborhoods turn cells on.

James Edward G. II

Yep. Ok i borrowed some ideas from Alpha Chen and tried to
remove everything evil from my solution. The result:

require ‘optparse’

rule, steps, cells = 145, 20, ‘1’

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

size = steps + cells.size + steps
line = cells.center(size, ‘0’)

steps.times do
puts line.tr(‘01’, ’ X’)
widened = line[0, 1] + line + line[-1, 1]
line = (0…size).map{|i| rule[widened[i, 3].to_i(2)]}.join
end

Well, not much new here but i think its clean and straight.

cheers

Simon

29

On Aug 13, 2007, at 6:24 PM, Alpha Chen wrote:

[0 0]1[0 0]
[0 0]0 0 1[0 0]
1 1 0 0 1

For any rules with a 1 in the final bit position, the edges should
basically be an infinite strand of on cells. Remember, any cell
that’s not on is off, so you technically start with:

…00000000000000000000100000000000000000000…

All of those 000 neighborhoods turn cells on.

James Edward G. II

30

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

31

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

32

On Aug 10, 7:53 am, Ruby Q. [email protected] wrote:

To simulate these elementarycellularautomata, you first need to construct a
“neighborhood” of the cell currently being examined, which includes the cell

the rule as an integer in decimal, the number of steps to simulate, and the
XXX XX
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.

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