Conway's Game of Life Code Kata

In preparation for my first code retreat later today, we were asked to study the problem at hand - Conway's Game of Life. Wikipedia has an excellent article describing the rules.

At my first attempt; I focused on the cell and tried to use a state machine. It didn't take too long before it felt cumbersome, so I stopped (although the state machine tests passed ;-)).

Then I tried to mimic "the real world" (oh, what a fallacy...) again, but this time I implemented a Grid<Coordinate> with an internal List<List<Coordinate>>. This was also a mistake... Imagine keeping a reference for all empty cells as well as making the grid infinite.

Third time's the charm, right? Why not just let a logical Grid instance keep a set of live cells? And why not remove all state changes, hence making both the Coordinate and the Grid types immutable? That way the Grid is asked to create a new immutable Grid for each generation.

By using these ideas, I quickly arrived at the solution below which I really like. It'll be very interesting to see what other solutions we'll come up with at the retreat.

using System;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;
using SharpTestsEx;

namespace ConwaysGameOfLifeKatas.GridAsListOfAliveCells.UnitTests
{
    public class GridAsListOfAliveCellsTests {
        [Test]
        public void new_generation_should_kill_alive_cell_with_fewer_than_two_live_neighbours() {
            var grid = new Grid(new Coordinate(1, 1), new Coordinate(0, 1));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(1, 1)).Should().Be.False();
        }

        [Test]
        public void new_generation_should_keep_alive_cell_with_two_live_neighbours_alive() {
            var grid = new Grid(new Coordinate(1, 1), new Coordinate(0, 1), new Coordinate(2, 1));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(1, 1)).Should().Be.True();
        }

        [Test]
        public void new_generation_should_keep_alive_cell_with_three_alive_neighbours_alive() {
            var grid = new Grid(new Coordinate(1, 1), new Coordinate(0, 1), new Coordinate(2, 1), new Coordinate(0, 0));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(1, 1)).Should().Be.True();
        }

        [Test]
        public void new_generation_should_kill_alive_cell_with_more_than_three_alive_neighbours() {
            var grid = new Grid(new Coordinate(0, 0), new Coordinate(1, 0), new Coordinate(2, 0), 
                new Coordinate(0, 1), new Coordinate(1, 1));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(1, 1)).Should().Be.False();
        }

        [Test]
        public void new_generation_should_revive_dead_cell_with_three_alive_neighbours() {
            var grid = new Grid(new Coordinate(0, 0), new Coordinate(1, 0), new Coordinate(2, 0));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(1, 1)).Should().Be.True();
        }

        [Test]
        public void blinker_oscillator_should_oscillate_according_to_wikipedia() {
            var grid = new Grid(new Coordinate(0, 1), new Coordinate(1, 1), new Coordinate(2, 1));

            grid = grid.CreateNextGeneration();

            grid.IsAlive(new Coordinate(0, 0)).Should().Be.False();
            grid.IsAlive(new Coordinate(1, 0)).Should().Be.True();
            grid.IsAlive(new Coordinate(2, 0)).Should().Be.False();
            grid.IsAlive(new Coordinate(0, 1)).Should().Be.False();
            grid.IsAlive(new Coordinate(1, 1)).Should().Be.True();
            grid.IsAlive(new Coordinate(2, 1)).Should().Be.False();
            grid.IsAlive(new Coordinate(0, 2)).Should().Be.False();
            grid.IsAlive(new Coordinate(1, 2)).Should().Be.True();
            grid.IsAlive(new Coordinate(2, 2)).Should().Be.False();
        }
    }

    public class Grid {
        private readonly ISet<Coordinate> _aliveCoordinates;

        public Grid(params Coordinate[] aliveCoordinatesSeed) {
            _aliveCoordinates = new HashSet<Coordinate>(aliveCoordinatesSeed);
        }

        public Grid CreateNextGeneration() {
            var keepAliveCoordinates = _aliveCoordinates
                .Where(c => GetNumberOfAliveNeighboursOf(c) == 2 || GetNumberOfAliveNeighboursOf(c) == 3);

            var reviveCoordinates = _aliveCoordinates
                .SelectMany(GetDeadNeighboursOf)
                .Where(c => GetNumberOfAliveNeighboursOf(c) == 3);

            return new Grid(keepAliveCoordinates.Union(reviveCoordinates).ToArray());
        }

        private IEnumerable<Coordinate> GetDeadNeighboursOf(Coordinate coordinate) {
            return GetNeighboursOf(coordinate).Where(c => !IsAlive(c)); 
        }

        private static IEnumerable<Coordinate> GetNeighboursOf(Coordinate coordinate) {
            return Enumerable.Range(-1, 3).SelectMany(
                    x => Enumerable.Range(-1, 3).Select(y => new Coordinate(coordinate.X + x, coordinate.Y + y)))
                    .Except(new []{coordinate});
        }

        private int GetNumberOfAliveNeighboursOf(Coordinate coordinate) {
            return GetNeighboursOf(coordinate).Count(IsAlive); 
        }

        public bool IsAlive(Coordinate coordinate) {
            return _aliveCoordinates.Contains(coordinate);
        }
    }

    public struct Coordinate : IEquatable<Coordinate> {
        private readonly int _x;
        private readonly int _y;

        public Coordinate(int x, int y) {
            _x = x;
            _y = y;
        }

        public int Y { get { return _y; } }

        public int X { get { return _x; } }

        public bool Equals(Coordinate other) {
            return other._x == _x && other._y == _y;
        }

        public override bool Equals(object obj) {
            if (ReferenceEquals(null, obj)) return false;
            if (obj.GetType() != typeof (Coordinate)) return false;
            return Equals((Coordinate) obj);
        }

        public override int GetHashCode() {
            unchecked {
                return (_x*397) ^ _y;
            }
        }
    }
}