Game of Beer

Conway’s Game of Life

The Game of Life is a cellular automaton devised by a British Mathematician, it requires no players and depends only on an initial seed state. Like many other games there are rules:

1. Any live cell with fewer than two live neighbour cells dies.
2. Any live cell with two or three live neighbour cells live to the next round.
3. Any live cell with more than three live neighbours dies.
4. Any dead cell with three neighbours becomes live, this is like reproduction according to wikipedia.

There are a number of patters associated with GOL, some are static, others are dynamic. A couple of examples are the beehive (static)

------
--xx--
-x--x-
--xx--
------

the boat (static)

-----
-xx--
-x-x-
--x--
-----

and the blinker (dynamic)

-----  -----
--x--  -----
--x--  -xxx-
--x--  -----
-----  -----

Like the Roman Numeral problem [https://biomunky.wordpress.com/2014/03/22/roman-numerals-the-default-dojo-option/], the Game of Life can frequently be found scrawled on the coding dojo whiteboard, indeed I’ve tried the problem before at one of the London Clojure Dojos [https://github.com/biomunky/ldnclj-dojo-team-5-game-of-life].

An attempt with Scala

Since the problem is generally about cells, my starting point is just that, a cell:

case class Cell(x: Int, y: Int)

The cell is the center of our world! It contains an x:Int – the row – and y: Int – the column. For every cell in our gamewe need to be able to get its neighbours, for this we define a function … let’s call it neighbours. Before we do this, we should sketch out what we want.

Given a simple 5×5 board where the central cell [2,2] is alive:

- - - - - 
- - - - -
- - X - -
- - - - -
- - - - -

what’s going on around the center cell? We can redraw the grid and make it look like a simple list of lists …

[0,0] [0,1] [0,2] [0,3] [0,4]
[1,0] [1,1] [1,2] [1,3] [1,4]
[2,0] [2,1] [2,2] [2,3] [2,4]
[3,0] [3,1] [3,2] [3,3] [3,4]
[4,0] [4,1] [4,2] [4,3] [4,4]

If we focus in on 2,2 we have:

[1,1] [1,2] [1,3]
[2,1] [2,2] [2,3]
[3,1] [3,2] [3,3]

If we look hard at this it becomes clear that there’s a certain pattern in the surrounding cells

[-1,-1][-1,0][-1, 1]
[ 0,-1][ 2,2][ 0, 1]
[ 1,-1][ 1,0][ 1, 1]

We can use this to create our neighbour function – my initial version looked as follows:

def neighbours(cell: Cell): List[Cell] = {
	val positions = List(-1, 0, 1)
	positions flatMap (x =>
		positions.map (y => Cell(cell.x+x, cell.y+y))
	) filterNot (_ == cell )
}

The function takes the cell of interest and calculates the neighbourhood, once all the cell positions (including the ‘cell’ position) we filter out our input cell. So that’s flatMap map and filterNot! Too many things in one place, it’s probably possible to clean that up.

Yup, it is. Rather than using the 3 functions we can use a for comprehension with a filter to only yield the cells we want. This simplifies the previous function to:

  def neighbours(cell: Cell): List[Cell] = {
    val positions = List(-1, 0, 1)
    for (i <- positions; j <- positions; if Cell(cell.x + i, cell.y + j) != cell)
      yield Cell(cell.x+i, cell.y+j)
  }

If you copy that function into the repl and run it with as follows:

neighbours(Cell(2,2))

you will get

List[Cell] = List(Cell(1,1), Cell(1,2), Cell(1,3), Cell(2,1), Cell(2,3), Cell(3,1), Cell(3,2), Cell(3,3))

and that matches the 3×3 grid above – woo hoo.

What we need to do now is work out if the cell is going to live on or die off. However, we aren’t going to be dealing with one cell, but rather a collection of cells – otherwise it’s going to be a very short Game of Life.

To help with this problem I created another case class, which for the current purpose looks as follows:

case class Grid(x: Int, y: Int, livingCells: List[Cell])

The x and y are the size of the grid and livingCells are our seed cells – remember that we only care about the LIVING cells. So, first things first, given a cell, we need to establish it’s local environment – a count of the living cells – but, we need to do it for multiple cells in one sitting. How?

  def candidates(livingCells: List[Cell]): Map[Cell, Int] = {
    livingCells
      .flatMap(neighbours)
      .foldLeft(Map.empty[Cell, Int]) { (amap, acell) => amap ++ Map(acell -> (amap.getOrElse(acell, 0) + 1)) }
  }

The first step is to calculate the neighbourhood – we use the `neighbours` function defined above. To apply it to all cells in the living list and return a simple flattened list, we use flatMap. This function returns a list of all potential cells and the number of count of living neighbours, something like:

Map(...
        Cell(0,3)   -> 1,
        Cell(3,0)   -> 1,
        Cell(1,1)   -> 4,
        Cell(1,-1)  -> 2,
    ...)

The map is going to contain cells that don’t exist! That kind of sucks, but it isn’t the end of the world, as I stated above, we (I) need two functions here.

Enter the second function: step. Step is as follows:

  def step(grid: Grid) = {
    val newCells = candidates(grid.livingCells).filter { case (loc, living) =>
      living == 3 || living == 2 && grid.isAlive(loc)
    }
    .keys
    .toList
    grid.copy(livingCells = newCells)
  }

The step function takes our grid – the list of living cells – and returns a new grid with our updated cells. The first step is to calculate the possible candidates, it then filters the map so that we are left with only cells that have a count of 3 (living cells) or 2 living cells and where the cell is currently alive. Since this will return a Map of cells and counts matching our criteria, we want to keep only the keys (the grid coordinates). We can get only the living cells by calling .keys on the filtered map. This is then converted to a list and a copy of our existing grid is created – with new living cells.

But wait, there’s no .isAlive!?!?

We need to update the grid class. Copy-pastey the following function into the Grid case class

def isAlive(cell: Cell) = livingCells contains cell

This function returns true if the grid.livingCells contains the passed Cell.

I’ve quickly tested this code (only tried a 3×3 with a blinker) and pushed to github – take a look for tests and bad code :)

This post has been fuelled by Meantime Pale Ale and Brooklyn Lager.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s