2011-01-27

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

3 comments:

  1. No pair finished the task within the 45 minutes that were available to us.

    Improvements to the solution above would be renaming Coordinate to Cell, and Grid to Generation.

    The CreateNextGeneration() method should probably be called Tick().

    I'd make «extract method» refactorings of the keepAlives and revives of the same method, hence it should read something like return KeepAlives.Union(Revives);

    I've never played with graphics and WPF/Silverlight, so that would be an interesting exercise.

    As one of my pairing partners pointed out, making the Generation enumerable could be smart (hence replacing the Tick method).

    My response to that was that one maybe should look into Rx (http://msdn.microsoft.com/en-us/devlabs/ee794896) as well?

    ReplyDelete
  2. Hi Martin,

    Really interesting post, I hope you don't mind I blogged about it...
    http://bit.ly/XCsRMT

    ReplyDelete
  3. Not at all. I really enjoyed your blog post. I personally love F#, but have never written any production code with it, unfortunately.

    I have since this post, updated the Life code somewhat (https://github.com/MartinRL/ConwaysGameOfLife), but I think your premise still holds true.

    ReplyDelete