G'day everyone,
I'm a Scala n00b (but am experienced with other languages) and am learning the language as I find time - very much enjoying it so far!
Usually when learning a new language the first thing I do is implement Conway's Game of Life, since it's just complex enough to give a good sense of the language, but small enough in scope to be able to whip up in a couple of hours (most of which is spent wrestling with syntax).
Anyhoo, having gone through this exercise with Scala I was hoping the Scala gurus out there might take a look at the code I've ended up with and provide feedback on it. I'm after anything - algorithmic improvements (particularly concurrent solutions!), stylistic improvements, alternative APIs or language constructs, disgust at the length of my function names - whatever feedback you've got, I'm keen to hear it!
You should be able to run the following script via "scala GameOfLife.scala" - by default it will run a 20x20 board with a single glider on it - please feel free to experiment.
// CONWAY'S GAME OF LIFE (SCALA)
abstract class GameOfLifeBoard(val aliveCells : Set[Tuple2[Int, Int]])
{
// Executes a "time tick" - returns a new board containing the next generation
def tick : GameOfLifeBoard
// Is the board empty?
def empty : Boolean = aliveCells.size == 0
// Is the given cell alive?
protected def alive(cell : Tuple2[Int, Int]) : Boolean = aliveCells contains cell
// Is the given cell dead?
protected def dead(cell : Tuple2[Int, Int]) : Boolean = !alive(cell)
}
class InfiniteGameOfLifeBoard(aliveCells : Set[Tuple2[Int, Int]])
extends GameOfLifeBoard(aliveCells)
{
// Executes a "time tick" - returns a new board containing the next generation
override def tick : GameOfLifeBoard = new InfiniteGameOfLifeBoard(nextGeneration)
// The next generation of this board
protected def nextGeneration : Set[Tuple2[Int, Int]] = aliveCells flatMap neighbours filter shouldCellLiveInNextGeneration
// Should the given cell should live in the next generation?
protected def shouldCellLiveInNextGeneration(cell : Tuple2[Int, Int]) : Boolean = (alive(cell) && (numberOfAliveNeighbours(cell) == 2 || numberOfAliveNeighbours(cell) == 3)) ||
(dead(cell) && numberOfAliveNeighbours(cell) == 3)
// The number of alive neighbours for the given cell
protected def numberOfAliveNeighbours(cell : Tuple2[Int, Int]) : Int = aliveNeighbours(cell) size
// Returns the alive neighbours for the given cell
protected def aliveNeighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = aliveCells intersect neighbours(cell)
// Returns all neighbours (whether dead or alive) for the given cell
protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = Set((cell._1-1, cell._2-1), (cell._1, cell._2-1), (cell._1+1, cell._2-1),
(cell._1-1, cell._2), (cell._1+1, cell._2),
(cell._1-1, cell._2+1), (cell._1, cell._2+1), (cell._1+1, cell._2+1))
// Information on where the currently live cells are
protected def xVals = aliveCells map { cell => cell._1 }
protected def xMin = (xVals reduceLeft (_ min _)) - 1
protected def xMax = (xVals reduceLeft (_ max _)) + 1
protected def xRange = xMin until xMax + 1
protected def yVals = aliveCells map { cell => cell._2 }
protected def yMin = (yVals reduceLeft (_ min _)) - 1
protected def yMax = (yVals reduceLeft (_ max _)) + 1
protected def yRange = yMin until yMax + 1
// Returns a simple graphical representation of this board
override def toString : String =
{
var result = ""
for (y <- yRange)
{
for (x <- xRange)
{
if (alive (x,y)) result += "# "
else result += ". "
}
result += "\n"
}
result
}
// Equality stuff
override def equals(other : Any) : Boolean =
{
other match
{
case that : InfiniteGameOfLifeBoard => (that canEqual this) &&
that.aliveCells == this.aliveCells
case _ => false
}
}
def canEqual(other : Any) : Boolean = other.isInstanceOf[InfiniteGameOfLifeBoard]
override def hashCode = aliveCells.hashCode
}
class FiniteGameOfLifeBoard(val boardWidth : Int, val boardHeight : Int, aliveCells : Set[Tuple2[Int, Int]])
extends InfiniteGameOfLifeBoard(aliveCells)
{
override def tick : GameOfLifeBoard = new FiniteGameOfLifeBoard(boardWidth, boardHeight, nextGeneration)
// Determines the coordinates of all of the neighbours of the given cell
override protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = super.neighbours(cell) filter { cell => cell._1 >= 0 && cell._1 < boardWidth &&
cell._2 >= 0 && cell._2 < boardHeight }
// Information on where the currently live cells are
override protected def xRange = 0 until boardWidth
override protected def yRange = 0 until boardHeight
// Equality stuff
override def equals(other : Any) : Boolean =
{
other match
{
case that : FiniteGameOfLifeBoard => (that canEqual this) &&
that.boardWidth == this.boardWidth &&
that.boardHeight == this.boardHeight &&
that.aliveCells == this.aliveCells
case _ => false
}
}
override def canEqual(other : Any) : Boolean = other.isInstanceOf[FiniteGameOfLifeBoard]
override def hashCode : Int =
{
41 * (
41 * (
41 + super.hashCode
) + boardHeight.hashCode
) + boardWidth.hashCode
}
}
class GameOfLife(initialBoard: GameOfLifeBoard)
{
// Run the game of life until the board is empty or the exact same board is seen twice
// Important note: this method does NOT necessarily terminate!!
def go : Unit =
{
var currentBoard = initialBoard
var previousBoards = List[GameOfLifeBoard]()
while (!currentBoard.empty && !(previousBoards contains currentBoard))
{
print(27.toChar + "[2J") // ANSI: clear screen
print(27.toChar + "[;H") // ANSI: move cursor to top left corner of screen
println(currentBoard.toString)
Thread.sleep(75)
// Warning: unbounded list concatenation can result in OutOfMemoryExceptions ####TODO: replace with LRU bounded list
previousBoards = List(currentBoard) ::: previousBoards
currentBoard = currentBoard tick
}
// Print the final board
print(27.toChar + "[2J") // ANSI: clear screen
print(27.toChar + "[;H") // ANSI: move cursor to top left corner of screen
println(currentBoard.toString)
}
}
// Script starts here
val simple = Set((1,1))
val square = Set((4,4), (4,5), (5,4), (5,5))
val glider = Set((2,1), (3,2), (1,3), (2,3), (3,3))
val initialBoard = glider
(new GameOfLife(new FiniteGameOfLifeBoard(20, 20, initialBoard))).go
//(new GameOfLife(new InfiniteGameOfLifeBoard(initialBoard))).go
// COPYRIGHT PETER MONKS 2010
Thanks!
Peter