Test driving Conway's Game of Life in Ruby : Part 2 of 2

Contd... Part 2
Do the evolution (with due apologies to Pearl Jam)
Let’s model our simulation with a file aptly titled ‘GameOfLife.rb’

Rule#1 : Any live cell with fewer than two live neighbours dies, as if by loneliness.
Red
Create new test case class

ts_GameOfLife.rb
require 'test/unit'
require 'Colony'
require 'GameOfLife'

class Test_GameOfLife < Test::Unit::TestCase

def test_Evolve_Loneliness
  @obColony = Colony.readFromFile("Colony1.txt");
  @obColony = GameOfLife.evolve(@obColony)
  assert( !@obColony.isCellAlive(1, 0) )
  assert( @obColony.isCellAlive(1, 1) )
  assert( !@obColony.isCellAlive(2, 2) )
end
end

Since we want to run all the tests from multiple files now, we can create a “test suite” It is as easy as creating a new file named ts_GameOfLife.rb.
Naming conventions : Prefix ts_ for test suites..

ts_GameOfLife.rb
require 'test/unit'
require 'tc_Colony'
require 'tc_GameOfLife'

We can then run the test suite with
ruby ts_GameOfLife.rb

Green
We traverse each cell in the colony and kill the cell if it is alive

class GameOfLife

def evolve ( obColony )
  (0..maxRows).each{ |iRow|
    (0..maxCols).each{ |iCol|
      killCellIfLonely(obColony, iRow, iCol)
    }
  }
  return obColony;
end

private
def killCellIfLonely(obColony, iRow, iCol)
  if (obColony.isCellAlive(iRow, iCol)  && ( obColony.getLiveNeighbourCount( iRow, iCol ) < 2 ) )
    obColony.markCell( iRow, iCol, false )
  end
end

end

Detour
Hmm but we don’t have getLiveNeighbourCount() and markCell(). Let’s test drive
Small red

tc_Colony.rb
def test_GetLiveNeighbourCount()
  assert_equal( 2, @obColony.getLiveNeighbourCount(0,0) )
  assert_equal( 0, @obColony.getLiveNeighbourCount(0,3) )
  assert_equal( 1, @obColony.getLiveNeighbourCount(1,3) )
  assert_equal( 0, @obColony.getLiveNeighbourCount(2,3) )
end

Small green

Colony.rb
 def getLiveNeighbourCount( iRow, iCol )
  iCountOfLiveNeighbours = 0

  obCoordinatesToExamine = [
    [iRow-1, iCol-1], [iRow-1, iCol], [iRow-1, iCol+1],
    [iRow, iCol-1], [iRow, iCol+1],
    [iRow+1, iCol-1], [iRow+1, iCol ], [iRow+1, iCol+1] ]

  obCoordinatesToExamine.each{ |curRow, curCol|
    iCountOfLiveNeighbours = iCountOfLiveNeighbours+1 if (isCellInBounds(curRow, curCol) && isCellAlive(curRow, curCol))
  }
  return iCountOfLiveNeighbours
end

def isCellInBounds( iRow, iCol)
  return ((0...@maxRows) === iRow) && ((0…@maxCols) === iCol)
end

Small Red

def test_MarkCell()
  assert( !@obColony.isCellAlive(0,0) )

  @obColony.markCell( 0, 0, true )
  assert( @obColony.isCellAlive(0,0), "Should have born now!" )

  @obColony.markCell( 0, 0, false )
  assert( !@obColony.isCellAlive(0,0), "Should have died now!" )
end

Small Green

def markCell( iRow, iCol, bIsCellAlive )
  @colonyGrid[iRow][iCol] = ( bIsCellAlive ? "1" : "0" )
  return
end

Refactor
I see some duplication with “1” and “0” – but I’ll refactor with Strike 3.

Hmmm still Red is my evolve test case. Had to use a couple of traces to find the bugger .. I left out a dot in the bold section below. 2 dots – inclusive range, 3 dots – max bound is not part of the range.

def evolve ( obColony )
  obNewColony = obColony.clone()

  (0...obColony.maxRows).each{ |iRow|
    (0...obColony.maxCols).each{ |iCol|
      #print "Count = " + obColonySnapshot.getLiveNeighboursCount( iRow, iCol ).to_s
      if ( obColony.getLiveNeighboursCount( iRow, iCol ) < 2 )
        obNewColony.markCell( iRow, iCol, false )
      end
    }
  }

  return obNewColony;
end

Colony.rb
def clone()
  #return Colony.new( @maxRows, @maxCols, Array.new(@colonyGrid) )
  return Colony.new( @maxRows, @maxCols, @colonyGrid.map{ |elem| elem.clone } )
end

Refactor

Well I got bit with the ranges. I used 0..obColony.maxRows instead of 0…obColony.maxRows and it blew up my test. I think traversing the Colony should be handled / provided by the colony itself. I don’t want anyone making the same mistake.

Let’s move that into a ruby iterator style Colony.each() method. So here it is

Colony.rb
def each
  (0...@maxRows).each{ |iRow|
    (0...@maxCols).each{ |iCol|
      yield iRow, iCol
    }
  }
end

so now I can use this in GameOfLife#evolve, Colony#to_s and Test_Colony#test_IsCellAlive. Code is even smaller!!

def evolve ( obColony )
  obNewColony = obColony.clone()

  obColony.each{ |iRow, iCol|
    if ( obColony.getLiveNeighboursCount( iRow, iCol ) < 2 )
      obNewColony.markCell( iRow, iCol, false )
    end
  }

  return obNewColony;
end

Colony.rb
def to_s
  sGridListing = ""
  each{ |iRow, iCol|
    sGridListing += ( isCellAlive( iRow, iCol) ? "@ " : ". " )
    sGridListing += "\n" if iCol.succ == @maxCols
  }
  return sGridListing
end

Next we need a test for Colony#clone that we sneakily added in to fix this test. We need to check if the cloned colony is similar to the original ..

tc_Colony.rb
def test_Clone
  clonedColony = @obColony.clone()
  assert_not_equal( clonedColony.object_id, @obColony.object_id, "Cloned object is the same as original" )

  @obColony.each{ |iRow, iCol|
    assert_equal( @obColony.isCellAlive(iRow, iCol),
      clonedColony.isCellAlive(iRow, iCol),
      "Contents differ at " + iRow.to_s + ", " + iCol.to_s )
  }
end

Ok let’s take a look at our next rule.
Rule#2 - Any live cell with more than three live neighbours dies, as if by overcrowding.
Let’s create a test colony for this rule.

Colony_Overcrowding.txt
3, 4
0 0 1 0
1 1 1 1
0 0 1 1

Red

tc_GameOfLife.rb
def test_Evolve_Overcrowding
  arrExpected = [false, false, true, false,
                false, false, false, false,
                false, false, false, true]
              
  @obColony = Colony.readFromFile("Colony_Overcrowding.txt");
  @obColony = GameOfLife.new.evolve(@obColony)

  iLooper = 0
  @obColony.each{ |iRow, iCol|
    assert_equal( arrExpected[iLooper], @obColony.isCellAlive(iRow, iCol),
      "Mismatch at " + iRow.to_s + ", " + iCol.to_s )
    iLooper += 1
  }
end

Green
Ok so we kill em off even if there are too many of them in an area ! Just another OR clause …

def evolve ( obColony )
  obNewColony = obColony.clone()

  obColony.each{ |iRow, iCol|
    if obColony.isCellAlive(iRow, iCol) and
       ( (obColony.getLiveNeighboursCount(iRow,iCol) < 2) or (obColony.getLiveNeighboursCount(iRow,iCol) > 3) )
      obNewColony.markCell( iRow, iCol, false )
    end
  }
  return obNewColony;
end

Rule#3 - Any dead cell with exactly three live neighbours comes to life.
Red

Colony_Birth.txt
5, 5
0 0 0 0 1
1 1 0 0 1
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0

tc_GameOfLife.rb
def test_Evolve_Birth
  arrExpected = [false, false, false, false, false,
                false, true, false, true, false,
                false, false, true, true, false,
                false, true, true, true, false,
                false, false,false, false, false             
                ]
    
  @obColony = Colony.readFromFile("Colony_Birth.txt");
  @obColony = GameOfLife.new.evolve(@obColony)

  iLooper = 0
  @obColony.each{ |iRow, iCol|
    assert_equal( arrExpected[iLooper], @obColony.isCellAlive(iRow, iCol),
      "Mismatch at " + iRow.to_s + ", " + iCol.to_s )
    iLooper += 1
  }
end

Green

GameOfLife.rb
def evolve ( obColony )
  obNewColony = obColony.clone()

  obColony.each{ |iRow, iCol|
    if obColony.isCellAlive(iRow, iCol)
      if ( (obColony.getLiveNeighboursCount(iRow,iCol) < 2) or (obColony.getLiveNeighboursCount(iRow,iCol) > 3) ) then
        obNewColony.markCell( iRow, iCol, false )
      end
    else
      obNewColony.markCell( iRow, iCol, true ) if ( obColony.getLiveNeighboursCount(iRow,iCol) == 3 )
    end
  }
  return obNewColony;
end

Hmm… that broke my overcrowding test. Oh yeah, as per the new rule, there is a newborn in that colony. Let me just update the expected results as

arrExpected = [false, false, true, true,
false, false, false, false,
false, false, false, true]

Refactor
The tests are duplicating code to traverse and check the Colony with the expected results/array. Extract method

private
def assert_colonies_are_similar( arrExpectedValues, obColony )
  iLooper = 0
  obColony.each{ |iRow, iCol|
    assert_equal( arrExpectedValues[iLooper], obColony.isCellAlive(iRow, iCol),
      "Mismatch at " + iRow.to_s + ", " + iCol.to_s )
    iLooper += 1
  }
end

refactored test looks like :

def test_Evolve_Overcrowding
  arrExpected = [false, false, true, true,
                false, false, false, false,
                false, false, false, true]
              
  obColony = Colony.readFromFile("Colony_Overcrowding.txt");

  assert_colonies_are_similar( arrExpected, GameOfLife.new.evolve(obColony) )
end

And that’s a wrap !!
Finally I quickly write up what I learn is called a “Driver”
ARGV is an array that contains the command line parameters. I’ll take two.. thank you!
One for the input colony text file and the second for the number of generations.
We then just evolve and keep printing the colony.

if (ARGV.length != 2) then
puts "Usage : ruby GameOfLife.rb [ColonyTextFile] [No of generations]"
exit
end
if (!File.exist?(ARGV[0])) then
puts "Specified Colony File does not exist"
exit
end


obColony = Colony.readFromFile(ARGV[0]);

0.upto(ARGV[1].to_i) { |iGenNo|
puts obColony.to_s + "Gen:" + iGenNo.to_s

obColony = GameOfLife.new.evolve(obColony)
}

Run it as …
L:\Gishu\Ruby\GameOfLife>ruby GameOfLife.rb TestColony.txt 100

You can also redirect output to a file
L:\Gishu\Ruby\GameOfLife>ruby GameOfLife.rb TestColony.txt 100 > a.txt

Open it up in Notepad for example… resize the height such that you can see one line below the Gen : X line. Now use the PgUp or PgDown keys to see evolution in action!!

By the way the TestColony.txt file contains the colony called Gosper’s glider gun. Watch the output and read the wiki to know why ! 

Hey this program is slow for 100+ generations.. I am at chapter 2 and find that there is another better way to implement this… a different perspective on this problem that cuts down the grid traversal for better performance.

Till next time….
Gishu
Feb 18, 2006

[Update : ]
A special Thanks to http://blog.wolfman.com/articles/2006/05/26/howto-format-ruby-code-for-blogs
for a good tip and an even cooler ruby script on pretty-formatting ruby code for html display.

Also the ruby-185-21 windows package seems to be broken. the gem install fails with a
"getaddrinfo: no address associated with hostname". I went back to 1.8.2 to get this done today !

Test driving Conway's Game of Life in Ruby : Part I

Well I had Ruby on my to-learn list for some time now. The pickaxe (don't leave your ruby-home without it) was getting rusty in a corner. I also had another book, Data Structures and Program Design in C, something I had picked up for the interview of my first job. So I decided why not translate the examples in the latter in Ruby – two birds with one stone ??

One that I liked up front (Chapter 1) is Conway’s Game of Life. The rules are explained here along with some cool information. This is basically a “cellular automaton”.. sounds ultra nerdy doesn’t it? Don’t worry sounds as greek to me as it does to you. In simple terms, it is a simulation of a colony of cells evolving. There are some rules governing the birth and mortality of cells. See the wikipedia page for details

Anyways, the writeup is also present in the uploaded zip -
http://tech.groups.yahoo.com/group/testdrivendevelopment/files/
"TDD_Conways_GameOfLife_Ruby.zip"


Let’s begin.
First I need to figure out how to write a test in Ruby. Pick up the pickaxe… What the…. now it can’t be that easy… can it?
Let’s create a file called GameOfLife.rb. Important items in bold below

require "test/unit"
class Test_GameOfLife < Test::Unit::TestCase

 def test_GetOne
   assert_equal(1, GameOfLife.new.getOne);
 end
end


class GameOfLife
end


L:\Gishu\Ruby\GameOfLife>ruby GameOfLife.rb
Loaded suite GameOfLife
Started
E
Finished in 0.016 seconds.

 1) Error:
test_GetOne(Test_GameOfLife):
NoMethodError: undefined method `getOne' for #<GameOfLife:0x2ba14d8>
   GameOfLife.rb:5:in `test_GetOne'

1 tests, 0 assertions, 0 failures, 1 errors

Ok we have a code red !! Let’s get it green… quick to the test mobile..

require "test/unit"
class Test_GameOfLife < Test::Unit::TestCase

 def test_GetOne
   assert_equal(1, GameOfLife.new.getOne);
 end
end


class GameOfLife
end


L:\Gishu\Ruby\GameOfLife>ruby GameOfLife.rb
Loaded suite GameOfLife
Started
E
Finished in 0.016 seconds.

 1) Error:
test_GetOne(Test_GameOfLife):
NoMethodError: undefined method `getOne' for #<GameOfLife:0x2ba14d8>
   GameOfLife.rb:5:in `test_GetOne'

1 tests, 0 assertions, 0 failures, 1 errors

require "test/unit"
class Test_GameOfLife < Test::Unit::TestCase

def test_GetOne
   assert_equal(1, GameOfLife.new.getOne);
 end
end

class GameOfLife
 def getOne
   return 1
 end
end


L:\Gishu\Ruby\GameOfLife>ruby GameOfLife.rb
Loaded suite GameOfLife
Started
.
Finished in 0.0 seconds.

1 tests, 1 assertions, 0 failures, 0 errors

Woo hoo !!! I have my first green light in Ruby. I feel the confidence running through my veins now… I had heard about Ruby’s principle of least surprise.. I’m fascinated. Beam me up, Scotty !!

The advent of colonization
Let’s make the input to the program a file. This file would contain the current snapshot of a “colony” of cells. The first line in the file shall tell us the max rows and columns in the colony

Colony1.txt
3, 4

So we need a colony class that can tell us the bounds of a colony in an input file.
Colony.ReadFromFile - ReadBounds
Naming conventions : Test case classes are saved in files prefixed with tc_

tc_Colony.rb

require 'test/unit'
require 'Colony'

class Test_Colony < Test::Unit::TestCase

 def test_ReadFromFile
   c = Colony.readFromFile("Colony1.txt");
   assert_equal(3, c.maxRows);
   assert_equal(4, c.maxCols);
 end
end

Colony.rb
class Colony
 def Colony.readFromFile( sColonyFile )
 end
end

Green
Initialize is a method that would be called whenever a Colony.new is issued. We take in 2 parameters for maxRows and maxCols to know the bounds.

Colony.readFromFile: We also have our first taste of File I/O. We read the first line and use regular expressions to break the line into 2 parts. We convert them to integers via to_i() and use them to create a Colony instance.

class Colony
 attr_reader :maxRows, :maxCols

 def initialize( iRows, iCols )
   @maxRows=iRows
   @maxCols=iCols
 end

 def Colony.readFromFile( sColonyFile )
     sColonyRows = sColonyCols = ""
     File.open(sColonyFile) { |obFile|
       sDimensions = obFile.gets
       sColonyRows, sColonyCols = sDimensions.scan(/\d+/)
     }
     return Colony.new(sColonyRows.to_i, sColonyCols.to_i)
 end
end

Refactor
Inline the variable sDimensions.

def Colony.readFromFile( sColonyFile )
     sColonyRows = sColonyCols = ""
     File.open(sColonyFile) { |obFile|
       sColonyRows, sColonyCols = obFile.gets.scan(/\d+/)
     }
     return Colony.new(sColonyRows.to_i, sColonyCols.to_i)
end

Colony.IsCellAlive
Since I am new to this.. I wrote the “read from file” test in 2 parts. Part 2 – now we read the actual colony. Update the Colony1.txt file as follows

Colony1.txt
3, 4
0 0 0 0
1 1 0 0
0 0 0 1

Red

tc_Colony.rb
def test_IsCellAlive
   c = Colony.readFromFile("Colony1.txt");
   expected = [
     false, false, false, false,
     true, true, false, false,
     false, false, false, true ]
    
   iExpectedLooper = 0;
   (0...c.maxRows).each{ |iRow|
     (0...c.maxCols).each{ |iCol|
       assert_equal( expected[iExpectedLooper], c.isCellAlive( iRow, iCol ) )
       iExpectedLooper = iExpectedLooper.succ
     }
   }
end

Colony.rb
def isCellAlive( iRow, iCol )
   return false;
end

Now to show that I’m not making all this up…

L:\Gishu\Ruby\GameOfLife>ruby tc_Colony.rb
Loaded suite tc_Colony
Started
F.
Finished in 0.094 seconds.

 1) Failure:
test_IsCellAlive(Test_Colony)
   [tc_Colony.rb:23:in `test_IsCellAlive'
    tc_Colony.rb:21:in `each'
    tc_Colony.rb:21:in `test_IsCellAlive'
    tc_Colony.rb:20:in `each'
    tc_Colony.rb:20:in `test_IsCellAlive']:
<true> expected but was
<false>.

2 tests, 7 assertions, 1 failures, 0 errors

Green
String.scan can parse a line and return an array. So this should work for us…
sRow.scan(/\d/) - > [“0”, “0”, “0”, 0”]
So I build up a 2D Array like this and stash it away in the Colony object.
[ [“0”, “0”, “0”, 0”], [“1”, “1”, “0”, “0”], [“0”, “0”, ”0”, “1” ] ]

class Colony
 attr_reader :maxRows, :maxCols

 def initialize( iRows, iCols, obColony2DArray )
   @maxRows=iRows
   @maxCols=iCols
   @colonyGrid=obColony2DArray
 end

 def Colony.readFromFile( sColonyFile )
     sColonyRows = sColonyCols = ""
     ob2DArray ||= []
    
     File.open(sColonyFile) { |obFile|
       sColonyRows, sColonyCols = obFile.gets.scan(/\d+/)
      
       while(sRow = obFile.gets)
         ob2DArray.insert(-1, sRow.scan(/\d/) )
       end
     }
     return Colony.new(sColonyRows.to_i, sColonyCols.to_i, ob2DArray)
 end

 def isCellAlive( iRow, iCol )
   return  ( @colonyGrid[iRow][iCol] == "1" ? true : false )
 end
end

Refactor
For the ones who came in late, I can factor out common code into a setup method, which is guaranteed to be executed before every test. So off with duplication !!

Add a member variable @obColony and initialize it inside setup()

tc_Colony.rb

def setup
   @obColony = Colony.readFromFile("Colony1.txt");
end

to_s() – ToString() for the .Net ters
Red

def test_ToString
   assert_equal( ". . . . \n@ @ . . \n. . . @ \n",
     @obColony.to_s )
end

 1) Failure:
test_ToString(Test_Colony) [tc_Colony.rb:34]:
<". . . . \n@ @ . . \n. . . @ \n"> expected
but was
<"#<Colony:0x2b9c9a8>">.

Green

def to_s
   sGridListing = ""
   (0…maxRows).each{ |iRow|
     (0...maxCols).each{ |iCol|
       sGridListing += ( isCellAlive( iRow, iCol) ? "@ " : ". " )
      }
      sGridListing += "\n"
   }
   return sGridListing
end

On to Part 2