Conway's Game of Life Code Kata #2

After yesterday's code retreat, I've refined, refactored, and added some IEnumerable plumbing to the solution I implemented in preparation for the retreat.

It would be a really fun exercise to visualize the generations with WPF, Silverlight or something else. I'd also like to finish the attempts made at the retreat to implement this solution with JavaScript. As one of my pairing partners pointed out, visualization could be done by manipulating the DOM of an ordinary web page.

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

namespace ConwaysGameOfLifeKatas.Generations.UnitTests {
    [Description("en.wikipedia.org/wiki/Conway's_Game_of_Life")]
    public class GenerationsUnitTests {
        [Test]
        public void new_generation_should_kill_alive_cell_with_fewer_than_two_live_neighbours() {
            var generations = new Generations(new Cell(1, 1), new Cell(0, 1));

            generations.First().Contains(new Cell(1, 1)).Should().Be.False();
        }

        [Test]
        public void new_generation_should_keep_alive_cell_with_two_live_neighbours_alive() {
            var generations = new Generations(new Cell(1, 1), new Cell(0, 1), new Cell(2, 1));

            generations.First().Contains(new Cell(1, 1)).Should().Be.True();
        }

        [Test]
        public void new_generation_should_keep_alive_cell_with_three_alive_neighbours_alive() {
            var generations = new Generations(new Cell(1, 1), new Cell(0, 1), new Cell(2, 1), new Cell(0, 0));

            generations.First().Contains(new Cell(1, 1)).Should().Be.True();
        }

        [Test]
        public void new_generation_should_kill_alive_cell_with_more_than_three_alive_neighbours() {
            var generations = new Generations(new Cell(0, 0), new Cell(1, 0), new Cell(2, 0),
                                              new Cell(0, 1), new Cell(1, 1));

            generations.First().Contains(new Cell(1, 1)).Should().Be.False();
        }

        [Test]
        public void new_generation_should_revive_dead_cell_with_three_alive_neighbours() {
            var generation = new Generations(new Cell(0, 0), new Cell(1, 0), new Cell(2, 0));

            generation.First().Contains(new Cell(1, 1)).Should().Be.True();
        }

        [TestCase(0,0,0,false)]
        [TestCase(1,0,0,true)]
        [TestCase(2,0,0,false)]
        [TestCase(0,1,0,false)]
        [TestCase(1,1,0,true)]
        [TestCase(2,1,0,false)]
        [TestCase(0,2,0,false)]
        [TestCase(1,2,0,true)]
        [TestCase(2,2,0,false)]
        [TestCase(0,0,1,false)]
        [TestCase(1,0,1,false)]
        [TestCase(2,0,1,false)]
        [TestCase(0,1,1,true)]
        [TestCase(1,1,1,true)]
        [TestCase(2,1,1,true)]
        [TestCase(0,2,1,false)]
        [TestCase(1,2,1,false)]
        [TestCase(2,2,1,false)]
        public void blinker_oscillator_should_oscillate_according_to_wikipedia(int x, int y, int generationIndex, bool isAlive) {
            var generations = new Generations(new Cell(0, 1), new Cell(1, 1), new Cell(2, 1));

            generations[generationIndex].Contains(new Cell(x, y)).Should().Be.EqualTo(isAlive);
        }
    }

    public class Generations : IEnumerable<Generation> {
        private readonly Generation _seedGeneration;

        public Generations(params Cell[] seed) {
            _seedGeneration= new Generation(seed);
        }

        public IEnumerator<Generation> GetEnumerator() {
            return new GenerationEnumerator(_seedGeneration);
        }

        public Generation this[int index] { 
            get {
                return this.ElementAt(index);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        public class GenerationEnumerator : IEnumerator<Generation> {
            public GenerationEnumerator(Generation generation) {
                Current = generation;
            }

            public void Dispose() {}

            public bool MoveNext() {
                Current = Current.Tick();

                return true;
            }

            public void Reset() {}

            public Generation Current { get; private set; }

            object IEnumerator.Current {
                get { return Current; }
            }
        }
    }

    public class Generation {
        private readonly ISet<Cell> _aliveCells;

        public Generation(params Cell[] aliveCellsSeed) {
            _aliveCells = new HashSet<Cell>(aliveCellsSeed);
        }

        private IEnumerable<Cell> KeepAlives {
            get {
                return _aliveCells
                    .Where(c => GetNumberOfAliveNeighboursOf(c) == 2
                                || GetNumberOfAliveNeighboursOf(c) == 3);
            }
        }

        private IEnumerable<Cell> Revives {
            get {
                return _aliveCells
                    .SelectMany(GetDeadNeighboursOf)
                    .Where(c => GetNumberOfAliveNeighboursOf(c) == 3);
            }
        }

        public Generation Tick() {
            return new Generation(KeepAlives.Union(Revives).ToArray());
        }

        private IEnumerable<Cell> GetDeadNeighboursOf(Cell cell) {
            return GetNeighboursOf(cell).Where(c => !Contains(c));
        }

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

        private int GetNumberOfAliveNeighboursOf(Cell cell) {
            return GetNeighboursOf(cell).Count(Contains);
        }

        public bool Contains(Cell cell) {
            return _aliveCells.Contains(cell);
        }
    }

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

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

        public int Y {
            get { return _y; }
        }

        public int X {
            get { return _x; }
        }

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

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

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

    public static class Extensions {
        public static IEnumerable<T> Except<T>(this IEnumerable<T> @this, T element) {
            return @this.Except(new[] {element});
        }
    }
}

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