A MapReduce algorithm for Conway's Game of Life

mapreduce_conway.rb

#!/usr/bin/env ruby

require 'rubygems'
require 'wukong'

# Given a file with the coordinate pair of a live cell on each line,
# generate the next iteration of Game of Life, using MapReduce
#
# The map phase takes each live cell, and outputs 9 key value pairs, 1 for
# each of the adjacent cells and itself.  The reduce phase dedupes, detects
# whether the cell is alive or dead in this iteration, and hence what it
# should be in the next iteration.
#
# Can be run locally, or using Hadoop to distribute processing of large worlds
#
# e.g. Given a file called iter1 containing:
# 1,1
# 1,2
# 1,3
#
# Running the command:
# $ ruby mapreduce_conway.rb --run=local iter1 iter2
# results in a file iter2 containing:
# 0,2
# 1,2
# 2,2
#
# Which is equivalent to:
# o x o         o o o
# o x o   ==>   x x x
# o x o         o o o
#
# This output can be fed to the script as the input for the next
# iteration.

module Conway
  class Mapper < Wukong::Streamer::LineStreamer
    def process line
      cell = line.chomp
      zone_of_effect(cell).each {|c| yield [c, cell]} rescue nil
    end

    private

    def zone_of_effect(cell)
      zones = []
      x,y = cell.split(",").map{|coord| coord.to_i}
      (x-1).upto(x+1) do |i|
        (y-1).upto(y+1) do |j|
          zones << "#{i},#{j}"
        end
      end
      zones
    end
  end

  class Reducer < Wukong::Streamer::ListReducer
    def finalize
      neighbours = values.map(&:last)
      cell_is_alive = neighbours.include? key
      yield [key] if alive_next?(cell_is_alive, key, neighbours.reject{|c| c==key})
    end

    private

    def alive_next?(alive_now, cell, neighbours)
      neighbours.size==3 or (neighbours.size==2 and alive_now)
    end
  end
end

Wukong::Script.new(Conway::Mapper, Conway::Reducer).run

So one reducer for one alive cell?