A friend of mine mentioned Conway’s Game of Life in a group chat today, so I ended up thinking, most people implement this with arrays, can we do it in a graph?

I just wrote the introduction post for Hedgehogs, so let’s give it a go:

## Domain

The game is played on a grid, each cell is either alive or dead.

On each time step, the following is performed:

- Any live cell with two or three live neighbours survives
- Any dead cell with three live neighbours becomes alive
- All other cells die

## Domain Modelling

We can just model the alive status as a `Boolean`

, and our grid as `(Int, Int)`

tuples.

We don’t need to care about weights here, so every edge can have weight 1 to keep things simple.

I’ll start off with a 5x5 grid:

```
import net.andimiller.hedgehogs._
// use a starting pattern, this is a blinker, a 2 phase animation from the game
val initialPattern = Set((2, 1), (2, 2), (2, 3))
val nodes = for {
<- 0 to 4
x <- 0 to 4
y } yield Node((x, y), initialPattern.contains((x,y)))
```

And we’d like them to connect to all adjacent cells, including diagonally, so we need some edges:

```
val validRange = (0 to 4).toSet
val edges = for {
<- 0 to 4
x <- 0 to 4
y <- x-1 to x+1
tx <- y-1 to y+1
ty if ((x,y) != (tx, ty)) // don't connect to itself
if (validRange(tx)) // stay in the grid
if (validRange(ty))
} yield Edge((x,y), (tx, ty), weight = 1)
```

We can combine these into our graph:

```
type LifeGraph = Graph[(Int, Int), Boolean, Int]
val graph: LifeGraph = Graph.fromIterables(nodes, edges, bidirectional = true)
.getOrElse(throw new Exception("invalid graph"))
```

And we’d like some way to render out our grid, so let’s do some quick string creation:

```
def render(nodes: Map[(Int, Int), Boolean]): String = nodes.toList
.sortBy(_._1)
.groupBy(_._1._2)
.toList
.sortBy(_._1)
.map { case (_, cells) =>
.map(_._2).map(alive => if (alive) "#" else " ").mkString
cells}
.mkString("\n")
render(graph.nodes)
// res0: String = """
// #
// #
// #
// """
```

## The Algorithm

Okay, I listed the 3 steps we need to perform above, we’re going to want a helper function to map the data inside a graph, maybe I should add this into the base `Hedgehogs`

library, but we’re adding it as an extension for now:

```
implicit class GraphOps[Idx, Data, Distance](g: Graph[Idx, Data, Distance]) {
def mapData[NewData](f: (Idx, Data) => NewData): Graph[Idx, NewData, Distance] =
.copy(nodes = g.nodes.map { case (k, v) => k -> f(k, v) })
g}
```

This just lets us map the data, taking in the index and data, returning the new data.

We’re going to want to ask how many alive neighbours a cell has in a graph:

```
def aliveNeighbours(g: LifeGraph)(id: (Int, Int)): Int =
.neighbours(id).map(_._1).map(g.nodes).count(identity) g
```

And now we can write our main step function:

```
def step(g: LifeGraph): LifeGraph = g.mapData {
case (id, true) if Set(2, 3).contains(aliveNeighbours(g)(id)) => true
case (id, false) if aliveNeighbours(g)(id) == 3 => true
case _ => false
}
```

## Result

```
render(graph.nodes)
// res1: String = """
// #
// #
// #
// """
render(step(graph).nodes)
// res2: String = """
//
// ###
//
// """
```

Get rotated nerd.