Game of Life (#193)

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

The three rules of Ruby Q.:

  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 Q. 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 T. 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
. 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.

Have Fun!

On Fri, Feb 20, 2009 at 6:18 PM, Daniel M. [email protected] 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 M. [email protected] 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 M.:

Game of Life (#193)

Nice. :slight_smile: 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 G. II

Daniel M. ha scritto:

Game of Life (#193)

Hi all,

here below there is my solution.

For update revisions please check the link below:

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

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

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

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

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

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!