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