I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Conway's Game of Life/Scala

Conway's Game of Life/Scala is part of Conway's Game of Life. You may find other members of Conway's Game of Life at Category:Conway's Game of Life.
Works with: Scala version 2.8

A Conway "board" has infinite dimensions -- in fact, Conway's Game of Life is Turing complete -- so the algorithm below avoids using fixed-size structures such as arrays. Instead, each generation is represented by a set of the coordinates which are "alive".

The solution will be presented in four sections: coordinates, generations, sample patterns and tester. The first two implement everything that is needed for Conway's Game of Life. The sample patterns includes four classes of patterns that are tested. The tester checks some specific characteristic of each pattern, and then shows the three generations of blinker, as requested.

Coordinates

The coordinates to any cell in the board is represented as an immutable tuple of integers. To speed up computation speed, each coordinate keeps a list of all its neighbors. This is computed on demand, as some coordinates may never become alive and, thus, never require it.

All coordinates are memoized (cached), so that the list of neighbors will never need to be recomputed for any coordinate. This can lead to memory starvation, however.

No coordinate will be accepted at the limits of the representation (Int). If any such coordinate is created, an exception will be thrown to indicate the board can no longer be correctly represented.

`class Coord private (val x: Int, val y: Int) {  private val offsets = List(-1, 0, 1)  private def offsetsOf(n: Int) = offsets map (_ + n)   /**   * A memoized list of all neighbors of a coordinate   */  lazy val neighbors = for {    xn <- offsetsOf(x) if Coord.legal(xn)    yn <- offsetsOf(y) if Coord.legal(yn) && (x, y) != (xn, yn)  } yield Coord(xn, yn)   // Coordinates can be used as offsets  def +(c: Coord) = Coord(x + c.x, y + c.y)  def -(c: Coord) = Coord(x - c.x, y - c.y)   override def equals(other: Any) = other match {    case that: Coord => this.x == that.x && this.y == that.y    case _ => false  }  override def hashCode = ((x * 41) + y) * 41 + 41  override def toString = "Coord(%d, %d)" format (x, y)} object Coord {  // A Conway board is infinite in size; throw an exception if our hard limits are reached  private def legal(n: Int) = {    n.ensuring(Int.MinValue < _, "Coord too low").ensuring(_ < Int.MaxValue, "Coord too high")    true  }  private val cache = new scala.collection.mutable.HashMap[(Int,Int), Coord]   /**   * Factory for coordinates. All coordinates are memoized.   */  def apply(x: Int, y: Int) = {    require(legal(x) && legal(y))    cache getOrElseUpdate ((x,y), new Coord(x, y))  }   /**   * Coordinate extractor   */  def unapply(c: Coord) = Some((c.x, c.y))   /**   * An Ordering for coordinates which sorts by the X coordinate   */  val xOrdering = Ordering.fromLessThan((_: Coord).x < (_: Coord).x)   /**   * An Ordering for coordinates which sorts by the Y coordinate   */  val yOrdering = Ordering.fromLessThan((_: Coord).y < (_: Coord).y)   /**   * Any Tuple2[Int, Int] can be used as a Coordinate through this implict   * conversion.   */  implicit def coordFromTuple(t: (Int, Int)) = apply(t._1, t._2)}`

Generation

Generations are represented as immutable sets of coordinates for the cells which are alive at that generation. They extend Scala's immutable Set, but adds a few methods. They can return the next generation, of course, and also have a few methods to help with that. When converted to string, it will return a representation of the smallest board that fully contains the pattern. It can also return representation for fixed-coordinates windows. Last, it can return a new generation with the pattern recentered.

`class Generation(val alive: Set[Coord]) extends Set[Coord] {  import Generation._   // Abstract methods that need to be defined as a Set  def contains(elem: Coord): Boolean = alive contains elem  def iterator: Iterator[Coord] = alive.iterator  def +(elem: Coord): Generation = if (alive contains elem) this else Generation(alive + elem)  def -(elem: Coord): Generation = if (alive contains elem) Generation(alive - elem) else this   // Helper methods to be able to pass tuples of Int instead of Coord  def apply(x: Int, y: Int): Boolean = apply(Coord(x, y))  def +(x: Int, y: Int): Generation = this.+(Coord(x, y))  def -(x: Int, y: Int): Generation = this.-(Coord(x, y))  def ++(coords: Iterator[(Int,Int)]): Generation = Generation(alive ++ (coords map (c => c: Coord)))   def ++(coords: Traversable[(Int,Int)]): Generation = Generation(alive ++ (coords map (c => c: Coord)))   /**   * A list containing all coordinates that are neighbors of a cell which is alive, together   * with the number of alive cells it is neighbor of.   */  lazy val neighbors = alive.toList flatMap (_ neighbors) groupBy identity map { case (c, l) => (c, l.size) }   // Filter all neighbors for desired characteristics       def neighborhood(filter: Filter) = for (filter(coord) <- neighbors) yield coord  def babies = neighborhood(Fecund)  def adults = alive & neighborhood(Stable).toSet   /**   * The next generation is composed of babies from fecund neighborhoods and adults on stable   * neighborhoods.   */  def nextGeneration = Generation(adults ++ babies)   /**   * Return a string with the representation of this generation on a window   * defined by its upper-left and lower-right coordinates.   */  def windowToString(upperLeft: Coord, lowerRight: Coord) = {    def toChar(c: Coord) = if (alive contains c) 'X' else ' '    def toRow(y: Int) = for (x <- upperLeft.x to lowerRight.x) yield toChar(Coord(x, y))    def toMatrix = for (y <- upperLeft.y to lowerRight.y by -1) yield toRow(y).mkString    toMatrix mkString "\n"  }   /**   * This generation's upper left corner   */  lazy val upperLeft = {    val x = alive min Coord.xOrdering x;    val y = alive max Coord.yOrdering y;    Coord(x, y)  }   /**   * This generation's lower right corner   */  lazy val lowerRight = {    val x = alive max Coord.xOrdering x;    val y = alive min Coord.yOrdering y;    Coord(x, y)  }   /**   * Recenter the pattern without altering its disposition   */  def recenter = {    val offset = Coord(      upperLeft.x + (lowerRight.x - upperLeft.x) / 2,      lowerRight.y + (upperLeft.y - lowerRight.y) / 2    )    Generation(alive map (_ - offset))  }   override def equals(other: Any) = other match {    case that: Generation => this.alive == that.alive    case _ => false  }  override def hashCode = alive.hashCode  override def toString = windowToString(upperLeft, lowerRight)} object Generation {  def apply(coords: Iterator[Coord]): Generation = apply(coords.toSeq)  def apply(coords: Traversable[Coord]): Generation = apply(coords.toSet)  def apply(alive: Set[Coord]) = new Generation(alive)  def apply() = new Generation(Set.empty[Coord])   // Helper class to filter neighbors for desired qualities  class Filter(f: ((Coord, Int)) => Option[Coord]) {    def unapply(t: (Coord, Int)): Option[Coord] = f(t)  }  object Filter {    def apply(f: ((Coord, Int)) => Option[Coord]) = new Filter(f)  }   // A fecund filter will return all coordinates with three neighbors alive  val Fecund = Filter {    case (c, 3) => Some(c)    case _ => None  }   // A stable filter will return all coordinates with two or three neighbors alive  val Stable = Filter {    case (c, 2) => Some(c)    case (c, 3) => Some(c)    case _ => None  }}`

Conway's Game of Life Patterns

A number of patterns are provided, which are used to test the program. They are divided into still lives, oscillators, spaceships and methuselahs. Still lives are immutable patterns. Oscillators are patterns that follow a fixed length cycle, after which they repeat themselves. Spaceships are patterns that move across the board -- they also have a fixed length cycle, after which they repeat themselves at some offset from their original position. Methuselahs are patterns that take a long time to stabilize. When stabilized, they consist of still lives, oscillators and gliders, but have a fixed population size.

A few helper methods are provided to get these patterns into use.

`object ConwayPatterns {  // Lists for all patterns available  def stillLives = List(block, beehive, loaf, boat) map ((_, 1))  def oscillators = oscillators2.map((_, 2)) ::: oscillators3.map((_, 3))   def oscillators2 = List(blinker, toad, beacon)  def oscillators3 = List(pulsar)  def spaceships = List(glider, LWSS) map ((_, 4))   def methuselahs = List((diehard, 130), (acorn, 5206), (rPentomino, 1103))   // Still Lives patterns  val block = """|                 | XX                 | XX                 |"""  val beehive = """|                   |  XX                   | X  X                   |  XX                   |"""  val loaf = """|                |  XX                | X  X                |  X X                |   X                |"""  val boat = """|                | XX                | X X                |  X                |"""   // Oscillators patterns  val blinker = """|                   |                   | XXX                   |                   |"""  val toad = """|                |                |  XXX                | XXX                |                |"""  val beacon = """|                  | XX                  | XX                  |   XX                  |   XX                  |"""  val pulsar = """|                  |                  |    XXX   XXX                  |                  |  X    X X    X                  |  X    X X    X                  |  X    X X    X                  |    XXX   XXX                  |                  |    XXX   XXX                  |  X    X X    X                  |  X    X X    X                  |  X    X X    X                  |                  |    XXX   XXX                  |                  |"""   // Spaceship patterns  val glider = """|                  |   X                  | X X                  |  XX                  |"""  val LWSS = """|                |                |  XXXX                | X   X                |     X                | X  X                |"""   // Methuselah patterns  val diehard = """|                   |       X                   | XX                   |  X   XXX                   |"""   val acorn = """|                 |  X                 |    X                 | XX  XXX                 |"""   val rPentomino = """|                      | XX                      |  XX                      |  X                      |"""   // Helper methods  // Enable constructing sets of coordinates from string patterns.  implicit def coordsFromPattern(pattern: String) = for {    (xs, y) <- pattern.stripMargin.split('\n').map(_.zipWithIndex).zipWithIndex.iterator    (c, x) <- xs.iterator    if c != ' '  } yield Coord(x, y)   // Move a set of coordinates to a point  def moveTo(pattern: String, to: Coord) = (pattern: Iterator[Coord]) map (_ + to)  def moveTo(coords: Iterator[Coord], to: Coord) = coords map (_ + to)  def moveTo(coords: Traversable[Coord], to: Coord) = coords map (_ + to) }`

Tester

We test still lives, oscillators and spaceships for their cycle length -- where still lives are considered to have a cycle length of 1 -- it repeats itself every generation. Methuselahs are tested for the number of generations until the population stabilizes. The test for stabilization is not fully accurate, as it just checks that the population is the same after a number of generations.

It also prints three generations of a blinker, as requested.

`object ConwayTester {  import ConwayPatterns._  val MaxGenerations = 5500 // Give up at MaxGenerations to avoid spending too much time on errors  val WindowSize = 10 // To check for stable populations, use a window this big  import Coord.{xOrdering, yOrdering}    /**   * Return an iterator for the generations of a starting pattern   */  def conwayIterator(first: Generation) = Iterator.iterate(first)(_.nextGeneration)   /**   * Return the period (number of different generations) for oscillators   */  def getPeriod(first: Generation) = {    val it = conwayIterator(first)    it.next // drop first generation    (it take MaxGenerations takeWhile (_ != first) length) + 1  }   /**   * Return the period (number of different generations, ignoring offset) for   * spaceships.   */  def getSpaceshipPeriod(first: Generation) = {    val it = conwayIterator(first) map (_.recenter)    it.next // drop first generation    (it take MaxGenerations takeWhile (_ != first) length) + 1  }   /**   * Return the number of generations until the population of a pattern   * stabilizes. This test only checks a window of generations for   * population size, as the test for spaceships won't work when multiple   * spaceships are present.   */  def getUnstableGenerations(first: Generation) = (    conwayIterator(first)     take MaxGenerations    map (_.size)    sliding WindowSize    map (_.removeDuplicates.length)    takeWhile (_ > 1)     length  )   /**   * Return the first generation, properly centered, for a given pattern   * as represented by a string.   */  def initPattern(pattern: String) =     Generation(pattern: Iterator[Coord]).recenter   /**   * For each pattern passed, apply a function which will measure some characteristic   * of the generations of that pattern, and assert it is equal to expected value.   */  def testHarness(patterns: Traversable[(String, Int)], test: Generation => Int, msg: String) =    assert(patterns forall { case (pattern, period) => test(initPattern(pattern)) == period }, msg)   // Available tests  def testStillLives = testHarness(stillLives, getPeriod _, "Failure in still lives")  def testOscillators = testHarness(oscillators, getPeriod _, "Failure in oscillators")  def testSpaceships = testHarness(spaceships, getSpaceshipPeriod _, "Failure in spaceships")  def testMethuselahs = testHarness(methuselahs, getUnstableGenerations _, "Failure in methuselahs")   /**   * Do all available tests   */  def testAll {    testStillLives    testOscillators    testSpaceships    testMethuselahs  }   /**   * Do all available tests, and print three generations of a blinker on a 3x3 window.   */  def main(args: Array[String]) {    val upperLeft = Coord(-1, 1)    val lowerRight = Coord(1, -1)    testAll    println("Passed all tests. Printing three generations of blinker:")    conwayIterator(initPattern(blinker)).zipWithIndex.take(3).toList zip List("st", "nd", "rd") foreach {       case ((generation, nth), suffix) =>         println((nth + 1) + suffix + " generation: \n"+generation.windowToString(upperLeft, lowerRight)+"\n")    }  }}`

Output:

```Passed all tests. Printing three generations of blinker:
1st generation:

XXX

2nd generation:
X
X
X

3rd generation:

XXX

```