193 Game of Life

Description

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!

Summary

Great job everyone on the response this week.

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!


Sunday, February 22, 2009