Skip to content

Instantly share code, notes, and snippets.

@andreisavu
Created May 8, 2011 13:40
Show Gist options
  • Save andreisavu/961376 to your computer and use it in GitHub Desktop.
Save andreisavu/961376 to your computer and use it in GitHub Desktop.
Scala Conway's Game of Life #2
/**
* Conway's Game of Life
*
* @author Andrei Savu <asavu@apache.org>
*/
case class Cell(row: Int, col: Int)
/**
* Unlimited universe for storing a set of cells
*/
class Universe(val cells: Set[Cell] = Set()) {
/**
* Create a new universe with one more newCell
*/
def add(newCell: Cell) = new Universe(cells + newCell)
def :: = add _
/**
* Get a sequence of neighbour cells dead and alive
*/
def neighbours(cell: Cell) =
for (row <- (cell.row - 1) to (cell.row + 1);
col <- (cell.col - 1) to (cell.col + 1)
if (row != cell.row || col != cell.col))
yield Cell(row, col)
/**
* Count the number of alive neighbour cells
*/
def countNeighbours(cell: Cell) =
neighbours(cell).filter(cells.contains(_)).size
/**
* Cell evolution rules for the game
*/
def rule(alive: Boolean, neighbours: Int) =
if (neighbours == 2) alive else (neighbours == 3)
/**
* Build the next generation by applying the rules
*/
def next(): Universe = {
var aliveCells = Set[Cell]()
for (cell <- cells) {
if (rule(true, countNeighbours(cell)))
aliveCells += cell
for(neighbour <- neighbours(cell))
if (rule(cells.contains(neighbour), countNeighbours(neighbour)))
aliveCells += neighbour
}
Universe(aliveCells)
}
/**
* Make a string representation for a window
*/
def mkString(topLeft: Cell, size: Int): String = {
require(size > 0)
def renderSingleRow(row: Int) =
for (col <- (topLeft.col - size) to (topLeft.col + size))
yield if (cells.contains(Cell(row, col))) '*' else '_'
val rows = for(row <- (topLeft.row - size) to (topLeft.row + size))
yield renderSingleRow(row).mkString
rows.mkString("\n")
}
/**
* Basic raw universe string representation
*/
override def toString = cells.toString
override def equals(that: Any) =
cells == that.asInstanceOf[Universe].cells
override def hashCode = cells.hashCode
}
/**
* Helper methods for constructing Universe instances
*/
object Universe {
def apply(cells: Set[Cell]) = new Universe(cells)
def apply(cells: Cell*) = new Universe(cells.toSet);
}
import org.scalatest.FunSuite
class UniverseTest extends FunSuite {
test("Create empty universe") {
val u = new Universe()
assert(u.cells.size === 0)
}
test("Add one new cell") {
val u = new Universe()
val c = Cell(5,5)
val nu = c :: u
assert(nu.cells.size == 1)
}
test("Render a small window") {
val u = Universe(Cell(1,1))
assert(u.mkString(Cell(1, 1), 1) === "___\n_*_\n___")
}
test("Count neighbours for a cell") {
assert(Universe(Cell(1,1)).countNeighbours(Cell(1,2)) === 1)
}
test("Any live cell with fewer that two live neighbours dies") {
assert(Universe().rule(true, 1) === false)
}
test("Any live cell with two or three live neighbours lives to next generation") {
assert(Universe().rule(true, 2) === true)
assert(Universe().rule(true, 3) === true)
}
test("Any live cell with more than three live neighbours dies") {
assert(Universe().rule(true, 4) === false)
}
test("Any dead cell with exactly three live neighbours becomes a live cell") {
assert(Universe().rule(false, 3) === true)
}
test("Compute two generations for an oscillator") {
val init = Universe(Cell(1,1), Cell(1,2), Cell(1, 3))
assert(init === init.next.next)
assert(init.next === init.next.next.next)
}
test("Still lives") {
val block = Universe(Cell(1,1), Cell(1, 2),
Cell(2, 1), Cell(2, 2))
assert(block === block.next())
val boat = Universe(Cell(1, 1), Cell(1, 2),
Cell(2, 1), Cell(2, 3), Cell(3, 2))
assert(boat === boat.next())
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment