Game of Life in Scala with a sparse representation

While reviewing another Scala implementation of the Game of Life, I ended up drastically rewriting it. The board is represented as a Set[(Int, Int)] containing the coordinates of the live cells.

I'm not sure whether the case class is appropriate here, and not too happy about the long parameter list. I'm also dissatisfied with the implementation of parse.

``
import java.io.File
import java.nio.file.Files

case class GameOfLife(living: Char='X', dead: Char=' ', height: Int=0, width: Int=0, liveCells: Set[(Int, Int)]=Set()) {

/**
* Parses a string representation of the board. Returns a GameOfLife
* object whose dimensions are at least as large as the current board,
* and expanded if necessary.
*/
def parse(board: String): GameOfLife = {
var h = height
var w = width
val cells = board.lines.zipWithIndex.flatMap({case (line, r) => {
h = h max (r + 1)
line.view.zipWithIndex.flatMap({
w = w max line.length
_ match {
case (living`, c) => Some((r, c))
case _ => None
}
})
}}).toSet
GameOfLife(living, dead, h, w, cells)
}

override def toString = {
(0 to height).map((r) =>
(0 to width).map((c) => if (isLive((r, c))) living else dead).mkString
).mkString("\n")
}

private val neighborOffsets = Set(
(-1, -1), (-1, 0), (-1, +1),
( 0, -1), ( 0, +1),
(+1, -1), (+1, 0), (+1, +1)
)

private def neighbors(cell: (Int, Int)): Set[(Int, Int)] = {
neighborOffsets.map(offset => (cell._1 + offset._1, cell._2 + offset._2))
.filter(isInBounds)
}

def isLive(cell: (Int, Int)): Boolean = liveCells.contains(cell)

def isInBounds(cell: (Int, Int)): Boolean = {
0 {
neighbors(c).count(isLive) match {
case 2 => isLive(c)
case 3 => true
case _ => false
}
}))
}

}

object GameOfLife {
def main(args: Array[String]): Unit = {
val initBoard = new String(F

You have an interesting implementation. I like your approach into making it "boundless" (that it could expand as-needed). I also like how you use "streams" to compute the values lazily. And some other minor gems.

There are of course some things that you could consider in order to make the design better.

1. Separation of Concerns

The most important thing I would do is to keep the parsing and the formatting separate from the "game". For me, these two concerns should be external to both your internal representation (a set of tuples) and logic.

For example I would have an object (or a class) GameParser and GameFormatter, each with one method to respectively parse and produce a "formatted" string-representation of your GameOfLife object.

(Why not just leave the formatting to toString? In my opinion toString is not there to produce complex formatting, much less "parametrised" formatting (as the "living" and "dead" chars are carried around only for this purpose) but to have an useful, but minimal, string-representation of one object instance. The way I see it, toString is for the developer, not the end-user. Note that for this reason toString implementations often "cut" or "summarize" the contents of the object. It gives you an idea of what the object is about).

You could, then have the same symmetry we see in JSON serializers. There we find readers and writers. You could have something like:

object GameFormatter {

  def formatAsGrid(game: GameOfLife, living: Char, dead: Char): String = {
    // ...
  }

}

object GameParser {

  def parseGrid(board: String, living: Char, dead: Char): GameOfLife = {
    // ...
  }

}

And your main class would become simpler:

case class GameOfLife(liveCells: Set[(Int, Int)] = Set(), width: Int = 0, height: Int = 0) { /* ... */ }

Once you extracted the parsing and formatting to external functions, you could further simplify their parameters. I introduced this case class:

case class GridChars(living: Char, dead: Char)

Which now only the parser and formatter need to be concerned about. We could then change the function signatures to:

def parseGrid(board: String, gridChars: GridChars)
def formatAsGrid(game: GameOfLife, gridChars: GridChars): String

Which would only need to be defined once in your main method, and passed as parameter to both parser and formatter (if so inclined, you could go one step further and dictate this to be an implicit parameter).

I think just these changes so far would make your design simpler, separate concerns better and let your main class have less parameters.

1. The parsing

But you also mention that you are not happy with the implementation of your parser. What do you think of this?

def parseGrid(board: String, gridChars: GridChars): GameOfLife = {
  var maxHeight = 0
  var maxWidth = 0
  val cells = mutable.Set[(Int,Int)]()
  for ((line, rowNr) <- board.lines.zipWithIndex) {
    maxHeight = maxHeight max (rowNr + 1)
    for ((cellChar, colNr) <- line.view.zipWithIndex) {
      maxWidth = maxWidth max line.length
      if (cellChar == gridChars.living)
        cells.add((rowNr, colNr))
    }
  }
  GameOfLife(cells.toSet, maxWidth, maxHeight)
}

I simplified things a little bit:

• instead of flatMapping, I am using double-for-loops

• I am indulging in "local-scope" mutability: still using the vars you introduced, and also using a mutable set, which poses to the outside world as "immutable".

1. Formatting

It would seem that my code is less functional, less Scala-idiomatic, less fancy, more boring and more Java-esque. And, you would be right! It is a matter of personal preference. My top priority when I write code is for it to be as readable as possible. For me, code which is obvious to the point of being boring is something positive. But that's just me.

For example, and in case it serves any purpose, here is my refactored version of your toString:

def formatAsGrid(game: GameOfLife, gridChars: GridChars): String = {
  import game.{height, isLive, width}
  (for (rowNr <- 0 to height) yield {
    (for (colNr <- 0 to width) yield {
      if (isLive((rowNr, colNr)))
        gridChars.living
      else
        gridChars.dead
    }).mkString // join chars into line
  }).mkString("\n") // join lines
}

It is longer and more verbose. Yet it does the same. I tend to favour longer, more verbose code, but not to the point where meaning is lost.

1. Other Points

There are some other improvements that I want to mention, which could also be considered:

• Naming: favouring longer, meaningful names instead of one-letter-variables. For example "colNr" / "rowNr" instead or "r" or "c".

• Favouring case-classes over tuples (e.g. Cell, Dimension, etc.)

• This is subjective, but I include it here nonetheless: consider using for loops as much as possible (for readability)

• Allow yourself to use scoped-mutability if it improves readability

(as a bonus: it might improve performance and

StackExchange Code Review Q#134907, answer score: 10