Forum: Ruby Game of Life (#193)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2.  Support Ruby Quiz by submitting ideas and responses
as often as you can! Visit: <http://rubyquiz.strd6.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.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Game of Life (#193)

This weeks quiz is to produce an implementation of [Conway's Game of
Life][1]. The Game of Life is a cellular automaton with simple rules:

   1. Any live cell with fewer than two live neighbours dies, as if by
needs caused by underpopulation.
   2. Any live cell with more than three live neighbours dies, as if
by overcrowding.
   3. Any live cell with two or three live neighbours lives,
unchanged, to the next generation.
   4. Any dead cell with exactly three live neighbours becomes a live 
cell.

It is amazing to see the patterns that can emerge from seemingly
innocuous configurations and a testament to the fact that you don't
need complex rules to generate complex behavior.

If you are new to Ruby then this is a great problem to practice on. It
also offers a good opportunity to become acquainted with some features
of 1.9.1.

[1]: http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Have Fun!

On Fri, Feb 20, 2009 at 6:18 PM, Daniel Moore <yahivin@gmail.com> wrote:

>
> ## Game of Life (#193)
>
> This weeks quiz is to produce an implementation of [Conway's Game of
> Life][1]. The Game of Life is a cellular automaton with simple rules:

Hi,

Thanks for this very interesting quiz. I have to admit that I already
had developed this, so I'm just sending what I had. I think I have
learned some Ruby since I did this, but I haven't had the time to
review this solution, so there might be some things that I'd do
differently now. Anyway, here's what I got. The programs does an
"animation" (printing the grid to the screen, so if you only look to
the lower part of your monitor it "might" look as an animation :-):

class GameOfLifeStateMachine
    DEATH = [0, 1, 4, 5, 6, 7, 8]
    LIFE = [2, 3]
    BIRTH = [3]

    LIVING_CELL = 1
    DEAD_CELL = 0

    def self.next_state(previous, alive_neighbours)
        case previous
        when DEAD_CELL
            if BIRTH.include? alive_neighbours
                LIVING_CELL
            else
                DEAD_CELL
            end
        when LIVING_CELL
            if DEATH.include? alive_neighbours
                DEAD_CELL
            else
                LIVING_CELL
            end
        else
            DEAD_CELL
        end
    end
end


class GameOfLife
    attr_reader :grid

    def initialize(rows, columns)
        @rows = rows
        @columns = columns
        @grid = Array.new(rows) {Array.new(columns,
GameOfLifeStateMachine::DEAD_CELL)}
    end

    # State is an array of arrays containing points to make alive
    def set_initial_state(state)
        state.each {|a,b| 
@grid[a][b]=GameOfLifeStateMachine::LIVING_CELL}
    end

    def next_state
        new_grid = []
        @grid.each_with_index do |row, i|
            new_row = []
            row.each_with_index do |column, j|
                new_row <<
GameOfLifeStateMachine.next_state(@grid[i][j], alive_neighbours(i,j))
            end
            new_grid << new_row
        end
        @grid = new_grid
    end

    def alive_neighbours(row, column)
        count = 0
        (-1..1).each do |i|
            (-1..1).each do |j|
                next if (i.zero? and j.zero?)
                row_index = row + i
                col_index = column + j
                if row_index >= 0 and row_index < @rows and col_index
>= 0 and col_index < @columns
                    count += 1 if @grid[row_index][col_index] ==
GameOfLifeStateMachine::LIVING_CELL
                end
            end
        end
        count
    end


    def to_s
        s = ""
        @grid.each {|row| row.each {|col| s << col.to_s << " "}; s << 
"\n"}
        s
    end
end

rows = 10
cols = 20
game = GameOfLife.new rows,cols


# Oscillators
#game.set_initial_state([[5,5],[5,6],[5,7]])
#game.set_initial_state([[5,5],[5,6],[5,7],[6,4],[6,5],[6,6]])

# Glider
game.set_initial_state([[0,1],[1,2],[2,0],[2,1],[2,2]])

puts game.to_s.gsub(/1/,"#")
puts


while true
#    puts "Press enter for next state"
#    gets
    game.next_state
    puts game.to_s.gsub(/1/,"#")
    puts "-" * cols
    sleep(0.5)
end

Jesus.

On Feb 20, 11:18 am, Daniel Moore <yahi...@gmail.com> wrote:
>
> This weeks quiz is to produce an implementation of [Conway's Game of
> It is amazing to see the patterns that can emerge from seemingly
>
> --
> -Danielhttp://rubyquiz.strd6.com

here is my really hideous code (but it uses opengl so its pretty!):

### gol.rb ###

class Cell

  attr_accessor :state, :next_state

  def initialize( state )

    @state = state

  end

  def alive?

    @state == 1

  end

end

class Game

  attr_accessor :board

  def initialize( board_size )

    @board = Array.new

    board_size.times do |i|

      @board[i] = Array.new

      board_size.times do |j|

        @board[i][j] = Cell.new( rand(2) ) # 0 means start with no
cell, 1 means start with a living cell

      end

    end

  end

  def update_board

    @board.each_index do |i|

      @board[i].each_index do |j|

        if ( @board[i][j].alive? and ( ( count_living_neighbors( i,
j ) < 2 ) or ( count_living_neighbors( i, j ) > 3 ) ) )

          @board[i][j].next_state = 0

        elsif ( @board[i][j].alive? and ( count_living_neighbors( i,
j ) == 2 or ( count_living_neighbors( i, j ) == 3 ) ) )

          @board[i][j].next_state = 1

        elsif ( !@board[i][j].alive? and count_living_neighbors( i,
j ) == 3 )

          @board[i][j].next_state = 1

        else

          @board[i][j].next_state = @board[i][j].state

        end

      end

    end

    @board.each_index do |i|

      @board[i].each_index do |j|

        @board[i][j].state = @board[i][j].next_state

      end

    end

  end

  def count_living_neighbors( i, j )

    sum = 0

    sum += 1 if i - 1 >= 0 and j - 1 >= 0 and @board[i - 1][j -
1].alive?
    sum += 1 if i - 1 >= 0 and @board[i - 1][j].alive?
    sum += 1 if i - 1 >= 0 and j + 1 < @board.size and @board[i - 1][j
+ 1].alive?
    sum += 1 if j - 1 >= 0 and @board[i][j - 1].alive?
    sum += 1 if j + 1 < @board.size and @board[i][j + 1].alive?
    sum += 1 if i + 1 < @board.size and j - 1 >= 0 and @board[i + 1][j
- 1].alive?
    sum += 1 if i + 1 < @board.size and @board[i + 1][j].alive?
    sum += 1 if i + 1 < @board.size and j + 1 < @board.size and @board
[i + 1][j + 1].alive?

    return sum

  end

end

### end gol.rb ###

### display.rb ###

require 'opengl'
require 'glut'
require 'gol'

$dot_size = 5.0
$board_size = 200
$gol = Game.new( $board_size )

display = Proc.new {

  GL.Clear( GL::COLOR_BUFFER_BIT );
  GL.PushMatrix();
  GL.Begin( GL::POINTS );

    $gol.board.each_index { |i|

      $gol.board[i].each_index { |j|

        GL.Vertex2f( i.to_f * $dot_size, j.to_f * $dot_size ) if
$gol.board[i][j].alive?

      }

    }

  GL.End();
  GL.PopMatrix();
  GLUT.SwapBuffers();

}

idle = Proc.new {

  $gol.update_board
  display.call

}


init = Proc.new {

  GL.ClearColor( 0.0, 0.0, 0.0, 0.0 )
  GL.MatrixMode( GL::PROJECTION )
  GL.LoadIdentity()
  GLU.Ortho2D( 0.0, $dot_size * $board_size.to_f, 0.0, $dot_size *
$board_size.to_f )
  GL.PointSize( $dot_size )
  GL.Enable( GL::POINT_SMOOTH )
  GL.Enable( GL::BLEND )
  GL.BlendFunc( GL::SRC_ALPHA, GL::ONE_MINUS_SRC_ALPHA )

}

GLUT.Init()
GLUT.InitDisplayMode( GLUT_DOUBLE | GLUT_RGB )
GLUT.InitWindowSize( $dot_size.to_i * $board_size, $dot_size.to_i *
$board_size )
GLUT.InitWindowPosition( 0, 0 )
GLUT.CreateWindow( "game of life" )
init.call
GLUT.DisplayFunc( display )
GLUT.IdleFunc( idle )
GLUT.MainLoop()

### end display.rb ###

Responding to Daniel Moore:

> ## Game of Life (#193)

Nice. :) I have given it a quick'n'dirty try and hope to get some hints
for improvement from others' solution and forum comments.

Initially I naively started with a 2-dimensional array, which worked but
was very slow - 100 generations on a 100x100 grid containing a single
glider took > 12 sec. Switching to an array containing simple RYO BigNum
based bit sets seemed to do insignificantly better. Then I switched to a
single-dimensional array - much better. The corresponding setup with a
single bit set performed disastrous, somewhere in the > 20 sec range -
discarded. Still it seemed way too slow, so I resorted to
unrolling/inlining the neighbor check and the "edge wrapping", ending up
with ~1.3 sec. This is okish for the animation, but still I think there
must be a more performant and/or more elegant way. I haven't tried yet
to reuse the grid data structure over iterations, perhaps there's some
improvement waiting there...

module RLife

  class RLifeGrid
    attr_reader :width, :height

    # nevermind the initializer, this is an artifact of benchmarking
    # array vs bit set
    def initialize(width, height,
        initializer = lambda { |size| Array.new(size, false) })
      @initializer = initializer
      @width = width
      @height = height
      @grid = initializer.call(@width * @height)
    end

    def[](horiz, vert)
      @grid[(horiz * @height) + vert]
    end

    def []=(horiz, vert, value)
      @grid[(horiz * @height) + vert] = value
    end

    def neighbors(horiz, vert)
      hpw = wrap(horiz - 1, @width) * @height
      hw = horiz * @height
      hsw = wrap(horiz + 1, @width) * @height
      vpw = wrap(vert - 1, @height)
      vsw = wrap(vert + 1, @height)
      count = 0
      count += 1 if @grid[hpw + vpw]
      count += 1 if @grid[hpw + vert]
      count += 1 if @grid[hpw + vsw]
      count += 1 if @grid[hw + vpw]
      count += 1 if @grid[hw + vsw]
      count += 1 if @grid[hsw + vpw]
      count += 1 if @grid[hsw + vert]
      count += 1 if @grid[hsw + vsw]
      count
    end

    def tick
      next_grid = RLifeGrid.new(@width, @height, @initializer)
      @width.times { |horiz|
        @height.times { |vert|
          next_grid[horiz, vert] = true if lives(horiz, vert)
        }
      }
      next_grid
    end

    def display_string
      str = ''
      @height.times { |vert|
        @width.times { |horiz|
          str << (self[horiz, vert] ? 'X' : '.')
        }
        str << "\n"
      }
      str
    end

    def RLifeGrid::parse(grid_def)
      lines = grid_def.lines.to_a
      width, height = lines[0].strip.size, lines.size
      grid = RLifeGrid.new(width, height)
      for vert in 0...height
        for horiz in 0...width
          grid[horiz, vert] = true if(lines[vert][horiz] == ?X)
        end
      end
      grid
    end

    private

    def wrap(index, size)
      index += size if(index < 0)
      index -= size if(index >= size)
      index
    end

    def lives(horiz, vert)
      neighbors = neighbors(horiz, vert)
      neighbors == 3 ||
          (neighbors == 2 && @grid[horiz * @height + vert])
    end
  end
end

module RLifeGUI
  include RLife

  class RLifeTk
    def initialize(parent, grid, time)
      @grid = grid
      @parent = parent
      @time = time
      @canvas = TkCanvas.new(parent)
      @canvas.pack
      @parent.after(@time) { rlife_tick }
    end

    private

    def rlife_tick
      @grid = @grid.tick
      paint_grid
      @parent.after(@time) { rlife_tick }
    end

    def paint_grid
      width, height = @canvas.winfo_width, @canvas.winfo_height
      background = TkcRectangle.new(@canvas, 0, 0, width, height)
      background.fill('white')
      cellsize =
          [1, [ width / @grid.width, height / @grid.height].min].max
      @grid.width.times do |horiz|
        @grid.height.times do |vert|
          if(@grid[horiz, vert])
            cell = TkcRectangle.new(
                @canvas, horiz * cellsize, vert * cellsize,
                (horiz + 1) * cellsize, (vert + 1) * cellsize)
            cell.fill('black')
          end
        end
      end
    end
  end
end

(This is also my very first attempt at Ruby/Tk, any hints for
improvement appreciated, too.)

Best regards,
Patrick

On Feb 23, 2009, at 2:43 AM, Jesús Gabriel y Galán wrote:

> Thanks for this very interesting quiz. I have to admit that I already
> had developed this, so I'm just sending what I had.

I too built the attached version some time ago.

You can run it with commands like:

   ruby life.rb 100 patterns/glider.txt

or:

   ruby ppm_life.rb 1000 patterns/puffer_train.txt

That second one builds some big images though, so it eats hard drive
space.  The number in both commands is a max turn count.

Thanks for the fun quiz!

James Edward Gray II

Daniel Moore ha scritto:
> ## Game of Life (#193)
>
>   
Hi all,

here below there is my solution.

For update revisions please check the link below:

http://github.com/remogatto/quizzes/blob/896064d504c236487b473423d8d9d94929395dd4/193/lib/gol.rb

To play the game:

ruby gol.rb [width] [height] [numbers of ticks]

class Grid
  include Enumerable
  class Cell
    attr_reader :x, :y
    [['born', 1], ['die', 0], ['unchanged', '@status']].each do |method,
status|
      module_eval(%{def #{method}; @grid[@x, @y] = #{status}; end})
    end
    def initialize(grid, x, y, status)
      @grid = grid
      @x, @y = x, y
      @status = status
    end
    def alive?
      @status == 1
    end
    def alive_neighbours
      [[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1,
0]].inject(0) do |sum, cell|
        sum += @grid[@x + cell[0], @y + cell[1]]
      end
    end
    def to_s
      alive? ? "o" : "."
    end
  end
  def self.generate(width, height)
    self.new(Array.new(height).collect { Array.new(width).collect {
rand(2) } })
  end
  def initialize(seed)
    @w, @h = seed.first.size, seed.size
    @cells = seed
  end
  def [](x, y)
    @cells[y % @h][x % @w]
  end
  def []=(x, y, value)
    @nextgen[y % @h][x % @w] = value
  end
  def each(&blk)
    @cells.each_with_index do |row, y|
      row.each_with_index { |col, x| yield Cell.new(self, x, y, self[x,
y]) }
    end
  end
  def tick!
    @nextgen = Array.new(@h).map { Array.new(@w).dup }
    each do |cell|
      if cell.alive?
        (cell.alive_neighbours < 2 || cell.alive_neighbours > 3) ?
cell.die : cell.unchanged
      else
        cell.alive_neighbours == 3 ? cell.born : cell.unchanged
      end
    end
    @cells = @nextgen
  end
  def to_s
    inject("") do |result, cell|
      result << cell.to_s << (cell.x == (@w - 1) ? "\n" : "")
    end
  end
end

if $0 == __FILE__
  grid = Grid.generate(ARGV[0] || 75, ARGV[1] || 20)
  (ARGV[2] || 2000).times do |gen_id|
    grid.tick!
    puts "#" * (ARGV[0] || 75)
    print grid
    puts "#" * (ARGV[0] || 75)
    puts "Generation n.#{gen_id + 1}"
  end
end

> ## Game of Life (#193)

It's about time I solve one of my own quizzes! My solutions only goal
was to teach me how to user Fibers in 1.9. Fibers are definitely worth
puzzling over. Reading about them is fine but you won't really get
that "Aha!" moment until you start using them.

Quiz summary coming tomorrow. Thanks everyone for your participation 
this week!

#!/usr/bin/ruby1.9

class Cell < Fiber
  def initialize
    super do
      alive = rand(2) == 1

      loop do
        neighbors = Fiber.yield(alive)
        if(alive)
          alive = ((2..3) === neighbors)
        else
          alive = (3 == neighbors)
        end
        Fiber.yield(alive)
      end
    end

    @alive = resume
  end

  def step
    @alive = resume
  end

  def set_neighbors(neighbors)
    resume(neighbors)
  end

  def alive?
    @alive
  end

  def to_s
    alive? ? '0' : '.'
  end
end

class Life
  def initialize(width=5, height=5)
    @width, @height = width, height
    @board = Array.new(height) {Array.new(width) {Cell.new}}
  end

  def step
    @board.each_with_index do |row, y|
      row.each_with_index do |cell, x|
        cell.set_neighbors(alive_neighbours(y, x))
      end
    end

    @board.each{|row| row.each{|cell| cell.step }}
  end

  # Based on code by Andrea Fazzi
  def alive_neighbours(y, x)
    [[-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1,
0]].inject(0) do |sum, cell|
      sum += @board[(y + cell[0])%@height][(x + cell[1])%@width].alive? 
? 1 : 0
    end
  end

  def to_s
    @board.map{|row| row.join('')}.join("\n")
  end
end

game = Life.new(30, 30)

250.times do
  game.step
  #puts game.counts
  puts game
end

Great job everyone on the response this week. (To view the images
inline go to http://rubyquiz.strd6.com/quizzes/193/#summary )

Despite all the commonalities, a two dimensional array and a simple
state machine, these solutions have something for everyone.

Jesus's solution is straightforward and comes with some nice pre-set
configurations: a glider and two oscillators. Like my solution Jesus
uses a 'poor mans' animation of printing the grid directly out to the
console.

![Game of Life - Jesus][1]

snex's solution uses an OpenGL display. Check it out if you are
interested in calling OpenGL from Ruby. My suggestion for improving
Object Oriented class design here is to [Tell, Don't Ask][2]. The
Board is asking the Cell for it's data and then changing it's state.
This functionality would be best pushed into the Cell class so the
Board can tell the Cell "Do your thing!"

![Game of Life - snex][3]

Patrick uses Ruby/Tk and focuses on performance. In place of a two
dimensional Array a single dimension is used. Additionally, instead of
iterating through the neighbor count with a loop they are all placed
explicitly in the code to remove loop overhead. The wrap() method may
not be necessary as Ruby's % operator handles -1 % size as expected at
size-1. With all of these tuning tweaks Patrick was able to go from a
time of 12s to a time of 1.3s about a 10x speed improvement. Patrick's
summary of the changes also say how some of the attempted
modifications actually worsened performance, like using a single bit
set. This illustrates the importance of measurement and trying
multiple approaches until acceptable performance is reached.

James submitted a solution that can reads in patterns from files and
can display either on the screen or by saving a sequence of images to
the disc. To prevent unnecessary computation James's solution keeps
track of a list of active locations and processes those each update.

![Game of Life - James][4]

Andrea submitted a complex and compact solution involving mixing in
Enumerable to the Grid class and a pinch of meta-programming for the
'born', 'die', and 'unchanged' methods. The next generation cells are
created by duplicating the Arrays and creating new Cells in the each
method. This keeps the effects of state changes from interfering with
the previous calculations. Afterwards the cell array is switched to
the new array for the process to begin again.

![Game of Life - Andrea][5]

Daniel (me) submitted a solution using/abusing ruby 1.9 Fibers.
Figuring out exactly when execution leaves the Fiber and what data
comes back in was a bit of a challenge, but after wrestling with it
for a while it started to click. Take a look if you are interested in
learning some more about Fibers. There are also many good tutorials on
the net.

Great turnout this week everyone, let's keep it up!

[1]: http://rubyquiz.strd6.com/quizzes/193/jesus.png
[2]: http://www.pragprog.com/articles/tell-dont-ask
[3]: http://rubyquiz.strd6.com/quizzes/193/snex.png
[4]: http://rubyquiz.strd6.com/quizzes/193/james.png
[5]: http://rubyquiz.strd6.com/quizzes/193/andrea.png