[QUIZ] Cellular Automata (#134)

[James Edward Gray II]

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

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

James Edward Gray II=

 

[Alpha Chen]

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

 

[James Edward Gray II]

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

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

 

[Simon Kröger]

..00000000000000000000100000000000000000000...

All of those 000 neighborhoods turn cells on.

James Edward Gray 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

 

[Daniel Martin]

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__

 

[Yossef Mendelssohn]

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.

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