Life in N Dimensions

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