[QUIZ] Game of Life (#193)

Discussion in 'Ruby' started by Daniel Moore, Feb 20, 2009.

  1. Daniel Moore

    Daniel Moore Guest

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

    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's_Game_of_Life

    Have Fun!

    --
    -Daniel
    http://rubyquiz.strd6.com
     
    Daniel Moore, Feb 20, 2009
    #1
    1. Advertising

  2. On Fri, Feb 20, 2009 at 6:18 PM, Daniel Moore <> 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]=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[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.
     
    Jesús Gabriel y Galán, Feb 23, 2009
    #2
    1. Advertising

  3. Daniel Moore

    snex Guest

    Re: Game of Life (#193)

    On Feb 20, 11:18 am, Daniel Moore <> wrote:
    > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    >
    > 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 livecell.
    >
    > 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's_Game_of_Life
    >
    > Have Fun!
    >
    > --
    > -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 = Array.new

    board_size.times do |j|

    @board[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.each_index do |j|

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

    @board[j].next_state = 0

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

    @board[j].next_state = 1

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

    @board[j].next_state = 1

    else

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

    end

    end

    end

    @board.each_index do |i|

    @board.each_index do |j|

    @board[j].state = @board[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[j - 1].alive?
    sum += 1 if j + 1 < @board.size and @board[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.each_index { |j|

    GL.Vertex2f( i.to_f * $dot_size, j.to_f * $dot_size ) if
    $gol.board[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 ###
     
    snex, Feb 23, 2009
    #3
  4. 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
     
    Patrick Roemer, Feb 23, 2009
    #4
  5. Daniel Moore

    Andrea Fazzi Guest

    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
     
    Andrea Fazzi, Feb 24, 2009
    #5
  6. Daniel Moore

    Daniel Moore Guest

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


    --
    -Daniel
    http://strd6.com
     
    Daniel Moore, Feb 28, 2009
    #6
  7. Daniel Moore

    Daniel Moore Guest

    [SUMMARY] Game of Life (#193)

    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
     
    Daniel Moore, Mar 1, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul Morrison

    Game of Life

    Paul Morrison, Mar 5, 2004, in forum: Java
    Replies:
    11
    Views:
    772
    Filip Larsen
    Mar 6, 2004
  2. CPSCmajor

    game of life

    CPSCmajor, Nov 18, 2005, in forum: Java
    Replies:
    15
    Views:
    858
    Patrick May
    Nov 24, 2005
  3. Gina
    Replies:
    1
    Views:
    8,657
    Hendrik Belitz
    Dec 16, 2003
  4. Tim Daneliuk
    Replies:
    0
    Views:
    234
    Tim Daneliuk
    Feb 6, 2005
  5. Replies:
    1
    Views:
    2,302
    Gianni Mariani
    Dec 6, 2006
Loading...

Share This Page