# 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
}

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 <= cell._1 && cell._1 < height &&
0 <= cell._2 && cell._2 < width
}

def nextGen(): GameOfLife = {
val candidates = liveCells.flatMap(neighbors).union(liveCells)
GameOfLife(living, dead, height, width, candidates.filter(c => {
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(Files.readAllBytes(new File(args(0)).toPath))
val initGame = GameOfLife().parse(initBoard)
lazy val generations: Stream[GameOfLife] = initGame #:: generations.map(_.nextGen)
generations.takeWhile(!_.liveCells.isEmpty).foreach(println)
}
}


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.

# 2. 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)
}
}
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".

# 3. 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
}).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.

# 4. 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 produce less garbage)
• Favour direct-talking (law of Demeter): ask GameOfLife itself if it's empty, not the cells. Provide a method hasLiveCells.
• Scala-style: don't specify an empty parameter list () if your function is pure (has no side-effects)
• Name the "main" object (where the main-method is) other than your game-logic-class, since they are not related (the reader could mistaken the object as the companion object of the case-class). Suggestion: GameOfLifeMain.
• Something minor: it does not seem right to me that width and height come from "outside". Although less performant I think this could be computed by GameOfLife itself, internally, as soon as it's instantiated.

# 5. Case-class or not?

To close I want to address another question you had, which I will paraphrase as this:

Does it have to be a case-class?

The decision is subtle, probably personal, and we enter in philosophical arena. There is of course nothing wrong for this to be a case-class. But personally, in this case, I would not make it so. This is the criteria I use to decide if to make it a case class or not:

Case class if:

• It has little to no logic
• I expect to do pattern matching on it
• I expect for it to be put into collections

Not case class if:

• It does contain "business" logic
• It does not make sense to put it into a collection
• I don't expect to do pattern matching on it

Whether the class is immutable, or I need a "quick" way to instantiate it and have getters (additional features of a case class) is irrelevant to me.

So, I hope this has helped and gave you some insights.