Sometimes we all feel as though life has gotten a bit out of hand. It's certainly been that way for me lately. As you may have noticed, I haven't updated this blog in quite some time, despite the way I was obviously trying to do it weekly. Was this just yet another case of someone up and walking away from their blog? No, not me! Really! I promise! (Well, at least this time it wasn't....)
So what's been keeping me so busy? My life has been very busy in several dimensions. I'll spare you most of it, but one was Ruby DCamp, an "unconference" centered around Ruby. The first day featured a "code retreat". Not an official one with Corey Haines himself present, but at least an event of that style. Apparently, the canonical problem to tackle in these is Conway's Game of Life.
Since each round is only 45 minutes, I didn't manage to get all the way through a successful implementation. And since it's so simple, I won't bother you with the one I did later.
BUT...
Evan Light, the organizer of Ruby DCamp, sort of threw down a gauntlet about extending Life from two dimensions to... unlimited. So, of course I then spent much of my spare time figuring that out.
The really hard part was to figure out how to display the state of the world. Eventually I settled on a sort of recursive concept:
- An individual cell is just output as-is.
- A row of cells (which I represented internally as a String) is output as-is, again.
- A two-dimensional world was output as a grid, as usual.
- For any higher dimensions, though:
- If it's odd, it's output as a row of blocks from the next dimension down, with a border between each and around the whole set.
- If it's even, it's output as a block of rows from the next dimension down, with a border between each and around the whole set.
Yeah, I know, that sounds kinda complex. But take a look at it in action, and you'll see what I mean. For instance, a three-dimensional world would look like this:
|* *| * | *|
|***| **|* |
|** | * |* |
a four-dimensional world would look like this:
+---+---+---+
|* *| * | *|
|***| **|* |
|** | * |* |
+---+---+---+
|* *| **| *|
| **| **|* *|
|** | *|* |
+---+---+---+
|* *| * | *|
|* *| **|***|
|** |** |* *|
+---+---+---+
a five-dimensional world would look like this:
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||***| **|* |||***| **|* |||***| **|* ||
||** | * |* |||** | * |* |||** | * |* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| **| *|||* *| **| *|||* *| **| *||
|| **| **|* *||| **| **|* *||| **| **|* *||
||** | *|* |||** | *|* |||** | *|* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||* *| **|***|||* *| **|***|||* *| **|***||
||** |** |* *|||** |** |* *|||** |** |* *||
|+---+---+---+|+---+---+---+|+---+---+---+|
a six-dimensional world would look like this:
+-------------+-------------+-------------+
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||***| **|* |||***| **|* |||***| **|* ||
||** | * |* |||** | * |* |||** | * |* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| **| *|||* *| **| *|||* *| **| *||
|| **| **|* *||| **| **|* *||| **| **|* *||
||** | *|* |||** | *|* |||** | *|* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||* *| **|***|||* *| **|***|||* *| **|***||
||** |** |* *|||** |** |* *|||** |** |* *||
|+---+---+---+|+---+---+---+|+---+---+---+|
+-------------+-------------+-------------+
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||***| **|* |||***| **|* |||***| **|* ||
||** | * |* |||** | * |* |||** | * |* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| **| *|||* *| **| *|||* *| **| *||
|| **| **|* *||| **| **|* *||| **| **|* *||
||** | *|* |||** | *|* |||** | *|* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||* *| **|***|||* *| **|***|||* *| **|***||
||** |** |* *|||** |** |* *|||** |** |* *||
|+---+---+---+|+---+---+---+|+---+---+---+|
+-------------+-------------+-------------+
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||***| **|* |||***| **|* |||***| **|* ||
||** | * |* |||** | * |* |||** | * |* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| **| *|||* *| **| *|||* *| **| *||
|| **| **|* *||| **| **|* *||| **| **|* *||
||** | *|* |||** | *|* |||** | *|* ||
|+---+---+---+|+---+---+---+|+---+---+---+|
||* *| * | *|||* *| * | *|||* *| * | *||
||* *| **|***|||* *| **|***|||* *| **|***||
||** |** |* *|||** |** |* *|||** |** |* *||
|+---+---+---+|+---+---+---+|+---+---+---+|
+-------------+-------------+-------------+
and so on.
And now, what you've all been waiting for... the code:
#!/usr/bin/ruby
# first some general utility stuff
# combine several blocks of text, as columns.
# might be some more elegant way to do this with recursive
# calls to Array#zip or something like that....
def combine_columns blocks, separator = '|', border = true
exploded = blocks.map { |blk| blk.split "\n" }
num_rows = exploded[0].length
result = []
num_rows.times do |row_num|
row = exploded.map { |blk| blk[row_num] }
if border then
row.push ''
row.unshift ''
end
result << row.join(separator)
end
result.join "\n"
end
# combine several rows of text, with separators made of a given char, using an
# alternate char wherever another certain char appears in the top or bottom of
# the row, assuming that they all start (and end) with the same thing as the
# start of the first.
def combine_rows rows, norm_char = '-', except = '|', response = '+', border = true
first_line = rows[0]
len = first_line.index("\n")
sep = norm_char * len
start = 0
while not (start.nil? or start >= len)
start = first_line.index except, start
if not start.nil?
sep[start] = response
start += 1
end
end
tmp = rows.join("\n#{sep}\n")
tmp = "#{sep}\n#{tmp}\n#{sep}" if border
end
# now the stuff specifically for this app:
class World
# apply the basic rules of life and death
# TODO MAYBE: Speed this up. This is where the profiler says it spends
# the second most time out of all the parts I wrote.
def apply_rule cur, nbrs
if cur == '*' then
(nbrs >= @min_stay and nbrs <= @max_stay ) ? '*' : ' '
else
(nbrs >= @min_birth and nbrs <= @max_birth) ? '*' : ' '
end
end
# public only for external testing purposes
def count_neighbors coords
count_neighbors_helper [], coords, coords, @cells
end
def initialize opts
@cells = opts[:cells]
@num_dims = get_num_dims_helper @cells
# Note, these formulas are rather ad-hoc. Just my SWAG at how to adjust
# for varying number of dimensions, and give the "standard" results in 2d.
base = 2 ** @num_dims
@min_stay = opts.fetch :min_stay, base / 2
@max_stay = opts.fetch :max_stay, base - 1
@min_birth = opts.fetch :min_birth, base / 2 + 1
@max_birth = opts.fetch :max_birth, base - 1
@max_stay = @min_stay if @max_stay < @min_stay
@max_birth = @min_birth if @max_birth < @min_birth
end
# convert current state to a string, for display purposes
def to_s
to_s_helper @cells, @num_dims
end
# let the world turn....
def turn
@cells = turn_helper @cells, []
end
private
# see what's in a particular subset of cells neighboring a given center
# TODO MAYBE: Speed this up. This is where the profiler says it spends
# the most time out of all the parts I wrote.
def count_neighbors_helper coords_done, coords_todo, center, cells
todo_dup = coords_todo.dup
count = 0
next_coord = todo_dup.shift
((next_coord - 1) .. (next_coord + 1)).each do |idx|
next if idx < 0 or idx >= cells.length
done_dup = coords_done.dup
done_dup << idx
if cells.class == Array
count += count_neighbors_helper done_dup, todo_dup, center, cells[idx]
elsif done_dup != center and cells[idx..idx] == '*'
count += 1
end
end
count
end
# figure out how many dimensions are in this world.
# (need this in order to set default rule parameters.)
def get_num_dims_helper cells
if cells.class == Array: get_num_dims_helper(cells[0]) + 1
elsif cells.class == String: 1
else
puts "ERROR: cells must be of type [Array of ...] String"
puts "(i.e., String, Array of String, Array of Array of String, etc.)"
# TODO: throw an exception?
exit 1
end
end
# turn a chunk of the world into a string,
# by recursing if it's too big to do at once (3+ dimensions).
# 1d is a simple string (should only happen in a total 1d world),
# 2d is a block of strings printed atop each other,
# higher odd dimensions are rows of blocks,
# higher even dimensions are blocks of rows.
def to_s_helper cells, num_dims
if num_dims == 1: cells
elsif num_dims == 2: cells.join("\n")
elsif num_dims % 2 == 0 then
rows = cells.map { |row| to_s_helper(row, num_dims - 1) }
combine_rows rows
else
blocks = cells.map { |blk| to_s_helper blk, num_dims-1 }
combine_columns blocks
end
end
# turn the world a piece at a time, drilling down into subsections as needed,
# accumulating results as we go
def turn_helper cells, coords
results = []
cells.length.times do |idx|
coords_dup = coords.dup
coords_dup << idx
if cells.class == Array: results << turn_helper(cells[idx], coords_dup)
else
results << apply_rule(cells[idx..idx], count_neighbors(coords_dup))
end
end
results = results.join if cells.class == String
results
end
end
But wait! There's more! You get a special bonus: the tests used to develop this program. Sorry they're not complete, but as you can probably guess, the ones I've left blank would be horribly tedious to fill in.
#! /usr/bin/ruby
require 'nd_life'
require 'profile'
describe 'nd_life' do
it 'should apply altered rules correctly' do
w = World.new :cells => '',
:min_stay => 4,
:max_stay => 6,
:min_birth => 2,
:max_birth => 5
w.apply_rule('*', 3).should == ' '
w.apply_rule('*', 4).should == '*'
w.apply_rule('*', 6).should == '*'
w.apply_rule('*', 7).should == ' '
w.apply_rule(' ', 1).should == ' '
w.apply_rule(' ', 2).should == '*'
w.apply_rule(' ', 5).should == '*'
w.apply_rule(' ', 6).should == ' '
end
it 'should apply default 1d rules correctly' do
w = World.new :cells => ''
w.apply_rule('*', 0).should == ' '
w.apply_rule('*', 1).should == '*'
w.apply_rule('*', 2).should == ' '
w.apply_rule(' ', 1).should == ' '
w.apply_rule(' ', 2).should == '*'
w.apply_rule(' ', 3).should == ' '
end
it 'should apply default 2d rules correctly' do
w = World.new :cells => ['']
w.apply_rule('*', 1).should == ' '
w.apply_rule('*', 2).should == '*'
w.apply_rule('*', 3).should == '*'
w.apply_rule('*', 4).should == ' '
w.apply_rule(' ', 2).should == ' '
w.apply_rule(' ', 3).should == '*'
w.apply_rule(' ', 4).should == ' '
end
it 'should apply default 3d rules correctly' do
w = World.new :cells => [['']]
w.apply_rule('*', 3).should == ' '
w.apply_rule('*', 4).should == '*'
w.apply_rule('*', 7).should == '*'
w.apply_rule('*', 8).should == ' '
w.apply_rule(' ', 4).should == ' '
w.apply_rule(' ', 5).should == '*'
w.apply_rule(' ', 7).should == '*'
w.apply_rule(' ', 8).should == ' '
end
it 'should apply default 4d rules correctly' do
w = World.new :cells => [[['']]]
w.apply_rule('*', 7).should == ' '
w.apply_rule('*', 8).should == '*'
w.apply_rule('*', 15).should == '*'
w.apply_rule('*', 16).should == ' '
w.apply_rule(' ', 8).should == ' '
w.apply_rule(' ', 9).should == '*'
w.apply_rule(' ', 15).should == '*'
w.apply_rule(' ', 16).should == ' '
end
it 'should count 1d neighbors correctly' do
w = World.new :cells => '* ** '
w.count_neighbors([0]).should == 0
w.count_neighbors([1]).should == 2
w.count_neighbors([2]).should == 1
w.count_neighbors([3]).should == 1
w.count_neighbors([4]).should == 1
end
it 'should count 2d neighbors correctly' do
w = World.new :cells => ['* ',
' * ',
' **']
w.count_neighbors([0,0]).should == 1
w.count_neighbors([0,1]).should == 2
w.count_neighbors([0,2]).should == 1
w.count_neighbors([1,0]).should == 3
w.count_neighbors([1,1]).should == 3
w.count_neighbors([1,2]).should == 3
w.count_neighbors([2,0]).should == 2
w.count_neighbors([2,1]).should == 2
w.count_neighbors([2,2]).should == 2
end
it 'should count 3d neighbors correctly' do
c = [['* ',
' '],
[' *',
'**'],
['* ',
' *']]
w = World.new :cells => c
w.count_neighbors([0,0,0]).should == 3
w.count_neighbors([0,0,1]).should == 4
w.count_neighbors([0,1,0]).should == 4
w.count_neighbors([0,1,1]).should == 4
w.count_neighbors([1,0,0]).should == 6
w.count_neighbors([1,0,1]).should == 5
w.count_neighbors([1,1,0]).should == 5
w.count_neighbors([1,1,1]).should == 5
w.count_neighbors([2,0,0]).should == 4
w.count_neighbors([2,0,1]).should == 5
w.count_neighbors([2,1,0]).should == 5
w.count_neighbors([2,1,1]).should == 4
end
it 'should count 4d neighbors correctly'
it 'should generate the next setup correctly in 1d' do
w = World.new :cells => '* ** '
c_str = w.to_s
neighbor_counts = {}
c_str.length.times { |idx| neighbor_counts[idx] = w.count_neighbors [idx] }
w.turn
c2_str = w.to_s
c_str.length.times do |idx|
old = c_str[idx..idx]
new = c2_str[idx..idx]
nbrs = neighbor_counts[idx]
new.should == w.apply_rule(old, nbrs)
end
end
it 'should generate the next setup correctly in 2d' do
c = ['* ',
' * ',
' **']
w = World.new :cells => c
c_str = w.to_s
neighbor_counts = {}
c.length.times do |row_idx|
c[row_idx].length.times do |col_idx|
neighbor_counts["#{row_idx}_#{col_idx}"] = w.count_neighbors [row_idx, col_idx]
end
end
w.turn
c2_str = w.to_s
c.length.times do |row_idx|
cur_row = c[row_idx]
cur_row.length.times do |col_idx|
idx = row_idx * (cur_row.length + 1) + col_idx
old = c_str[idx..idx]
new = c2_str[idx..idx]
nbrs = neighbor_counts["#{row_idx}_#{col_idx}"]
new.should == w.apply_rule(old, nbrs)
end
end
end
it 'should generate the next setup correctly in 3d'
it 'should generate the next setup correctly in 4d'
it 'should store a 1d setup correctly' do
c = '* '
w = World.new :cells => c
w.to_s.should == c
end
it 'should store a 2d setup correctly' do
c = ['* ', ' * ', ' **']
w = World.new :cells => c
w.to_s.should == c.join("\n")
end
it 'should store a 3d setup correctly' do
c = [['* ',
'* ',
' * '],
[' **',
' * ',
'* *'],
['** ',
'** ',
' **']]
w = World.new :cells => c
w.to_s.should == "|* | **|** |\n"\
"|* | * |** |\n"\
"| * |* *| **|"
end
it 'should store a 4d setup correctly' do
c = [[['* ', '* ', ' * '],
[' **', ' * ', '* *'],
['** ', '** ', ' **']],
[['* ', '* ', ' * '],
[' **', ' * ', '* *'],
['** ', '** ', ' **']],
[['* ', '* ', ' * '],
[' **', ' * ', '* *'],
['** ', '** ', ' **']]]
w = World.new :cells => c
w.to_s.should == "+---+---+---+\n"\
"|* | **|** |\n"\
"|* | * |** |\n"\
"| * |* *| **|\n"\
"+---+---+---+\n"\
"|* | **|** |\n"\
"|* | * |** |\n"\
"| * |* *| **|\n"\
"+---+---+---+\n"\
"|* | **|** |\n"\
"|* | * |** |\n"\
"| * |* *| **|\n"\
"+---+---+---+"
end
it 'should store a 5d setup correctly'
it 'should store a 6d setup correctly'
end
If you're especially observant (no I don't mean Orthodox!), you may have noticed that my previous tests were done with Test::Unit, and these are RSpec. Yes, I finally learned RSpec, at Ruby DCamp. Also note the profiler; that helped me spot the bottlenecks. (You may think you know where the bottlenecks in your code are, but chances are, you're wrong. That's just one of the things humans generally aren't very good at. Let the machine do the work and tell you where it hurts.)
And! If you order by midnight tonight, you get a special second bonus: a test driver, so you can watch this thing run, in six whopping dimensions! Just look:
#!/usr/bin/ruby
require 'nd_life'
# six dimensions
cells = [[[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]]],
[[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]]],
[[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]],
[[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']],
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]]]]
def randomize cells
if cells.class == Array then
cells.map { |part| randomize part }
else
cells.length.times { |i| cells[i..i] = rand(2) == 1 ? '*' : ' ' }
end
end
randomize cells
w = World.new :cells => cells
gen_num = 0
prev_worlds = []
stable = false
rep = w.to_s
while not stable do
gen_num += 1
puts "Generation #{gen_num}:"
puts rep
prev_worlds << rep
w.turn
rep = w.to_s
idx = prev_worlds.rindex rep # use rindex since later most likely to match
if not idx.nil?
stable = true
puts "Next state is same as at Generation #{idx + 1}"
end
end
Now how much would you pay? (crickets . . . crickets . . .) Well that's okay, because it's not $999, not $99, not even $9, but free, though as always I would appreciate you donating the time to tell me how I'm Doin' It Wrong.
Seriously. This thing is pretty slow, at about seven seconds per generation, on my machine. (On the other claw, it is pretty ancient, a Powerbook, and yes I mean Powerbook not Macbook.) Let's hear some ideas for speeding it up. The profiler says the main timesink is the counting of neighbors, specifically count_neighbors_helper. Any better, or at least other, ideas? Why would you do it your way?
As for other assorted improvements, I've already thought of, but decided not to do quite yet:
- Telling it only how many dimensions it has, and how big it is, letting it assume that all dimensions are the same size, and generate random contents.
- Telling it only how many dimensions it has, and how big each is, letting it generate random contents.
- Having it detect when stability has been reached. (Actually I had that in earlier, just detecting when a new generation was the same as the old, but since so many forms of stability are cyclic, I took it out, in favor of moving that functionality to the driver.)
