«

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

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!

--
-Daniel
http://rubyquiz.strd6.com

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:EAD_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:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> 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%27s_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[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:OINTS );

$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:ROJECTION )
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:OINT_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:arse(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

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/...193/lib/gol.rb

To play the game:

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

class Grid
include Enumerable
class Cell
attr_reader , :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


--
-Daniel
http://strd6.com

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