From: Patrick Roemer <sangamon@...>
Date: 2009-02-24T01:09:26+09:00
Subject: Re: [QUIZ] Game of Life (#193)

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