Finding clusters in a matrix

Question

I got asked at an interview to write a program that, given a NxM matrix with zeros and ones, prints out the list of clusters of 1s. The clusters are defined as patches of 1s connected horizontally, vertically or diagonally.

Here's the code I submitted but I'm wondering if there is a better way, e.g. a well-known algorithm to produce the solution.

namespace ConsoleApplication1
{
    /// <summary>
    /// Usage:
    /// <![CDATA[
    /// 
    ///            var m = 4; // rows
    ///            var n = 5; // cols
    ///            var matrix = new[]
    ///            {
    ///                0,1,0,0,0,  // 0-4
    ///                0,0,1,1,0,  // 5-9
    ///                0,0,0,0,0,  // 10-14
    ///                0,1,1,0,0   // 15-19
    ///            };
    ///
    ///            var finder = new MatrixClusterFinder(matrix, m, n);
    ///            finder.PrintClusters();
    /// PRINTS:
    /// (0,1)(1,2)(1,3)
    /// (3,1)(3,2)
    /// 
    /// ]]>
    /// 
    /// 
    /// 
    /// </summary>
    public class MatrixClusterFinder
    {
        private int m;
        private int n;
        private int[] matrix;

        public MatrixClusterFinder(int[] matrix, int m, int n)
        {
            this.m = m;
            this.n = n;
            this.matrix = matrix;
        }

        public void PrintClusters()
        {
            var visited = new bool[m * n];

            for (var i = 0; i < m * n; i++)
            {
                var isClusterFound = Traverse(i, visited);

                if (isClusterFound)
                {
                    Console.WriteLine(); //crlf
                }
            }

        }

        private bool Traverse(int curr, bool[] visited)
        {
            if (visited[curr])
            {
                return false;
            }

            bool result = false;
            visited[curr] = true;
            if (matrix[curr] == 1)
            {
                result = true;
                var thisM = curr / n;
                var thisN = curr % n;
                Console.Write("({0},{1})", thisM, thisN);

                var adjs = GetAdjacent(curr);
                foreach (var adj in adjs)
                {
                    Traverse(adj, visited);
                }
            }
            return result;
        }

        private int[] GetAdjacent(int curr)
        {
            var thisM = curr / n;
            var thisN = curr % n;
            var result = new List<int>();
            for (var i = thisM; i <= thisM + 1; i++)
            {
                if (i < 0 || i > m - 1)
                {
                    continue;
                }
                for (var j = thisN - 1; j <= thisN + 1; j++)
                {
                    if (j < 0 || j > n - 1 || (i == thisM && j < thisN))
                    {
                        continue;
                    }
                    var res = i * n + j;
                    if (res == curr)
                    {
                        continue;
                    }
                    result.Add(res);
                }
            }
            return result.ToArray();
        }

    }
}

Answer 1

For a problem like this, the interviewer is not actually looking for the most efficient/well-known algorithm possible. They want you to demonstrate that you can solve simple problems, using OO principles (encapsulation, inheritance, polymorphism), C# language features (Generics, LINQ, TPL etc) as well as industry standard patterns and practices like TDD, SOLID, DRY and so on.

The solution you have written is good in that it solves the problem and correctly uses recursion (probably eliminating 90% of the competition). I had some spare time today, so I've written an alternative solution that demonstrates some of the things I just mentioned. It is by no means, "the answer", just one of many possible solutions.

class Program
{
    static void Main()
    {
        var input = new[,]
        {
            {0, 1, 0, 0, 0},
            {0, 0, 1, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 0, 0}
        };

        var locator = new ClustersLocator<int>(1);
        var clusters = locator.LocateClusters(input);

        foreach (var cluster in clusters)
            Console.WriteLine(cluster);

        Console.ReadKey();
    }
}

---

Coord

A 2D coordinate (struct) used by Matrix and Cluster.

public struct Coord : IEquatable<Coord>
{
    public Coord(int n, int m) : this()
    {
        N = n;
        M = m;
    }

    public int N { get; private set; }
    public int M { get; private set; }

    #region ToString() and Equals()
}

Cluster

A list of Coords that is equal to another Cluster if it has the same Coords.

public class Cluster
{
    public Cluster(IEnumerable<Coord> coords)
    {
        if (coords == null)
            throw new ArgumentNullException("coords");

        Coords = coords;
    }

    public IEnumerable<Coord> Coords { get; private set; }

    // Override Equals() and GetHashCode() to compare Coords
    #region Equals() and ToString()
}

Matrix

A 2D matrix of generic values. Implements IEnumerable<Coord> to allow for easy enumeration of all coordinates. Contains helper methods for getting adjacent coordinates.

internal class Matrix<T> : IEnumerable<Coord>
{
    private readonly T[,] _values;

    public Matrix(T[,] values)
    {
        _values = values;
    }

    public Matrix(int rows, int columns)
    {
        _values = new T[rows, columns];
    }

    public T this[Coord coord]
    {
        get { return _values[coord.N, coord.M]; }
        set { _values[coord.N, coord.M] = value; }
    }

    public int Rows { get { return _values.GetLength(0); } }
    public int Columns { get { return _values.GetLength(1); } }

    public IEnumerator<Coord> GetEnumerator()
    {
        for (var n = 0; n < Rows; n++)
            for (var m = 0; m < Columns; m++)
                yield return new Coord(n, m);
    }

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

    public IEnumerable<Coord> GetEqualAdjacentCoords(Coord coord)
    {
        return GetAdjacentCoords(coord)
            .Where(a => this[a].Equals(this[coord]));
    }

    public IEnumerable<Coord> GetAdjacentCoords(Coord coord)
    {
        var adjacent = new[]
        {
            new Coord(coord.N - 1, coord.M + 1),
            new Coord(coord.N - 1, coord.M),
            new Coord(coord.N - 1, coord.M - 1),
            new Coord(coord.N + 1, coord.M + 1),
            new Coord(coord.N + 1, coord.M),
            new Coord(coord.N + 1, coord.M - 1),
            new Coord(coord.N, coord.M + 1),
            new Coord(coord.N, coord.M - 1)
        };

        return adjacent.Where(InRange);
    }

    public bool InRange(Coord coord)
    {
        return coord.N >= 0 && coord.N < Rows
            && coord.M >= 0 && coord.M < Columns;
    }
}

ClusterLocator

The main algorithm. Also generic, and can locate clusters of any value.

public class ClustersLocator<T> : IClustersLocator<T>
{
    private readonly T _clusterValue;

    public ClustersLocator(T clusterValue)
    {
        _clusterValue = clusterValue;
    }

    public IEnumerable<Cluster> LocateClusters(T[,] matrix)
    {
        if (matrix == null)
            throw new ArgumentNullException("matrix");

        return LocateClusters(new Matrix<T>(matrix));
    }

    private IEnumerable<Cluster> LocateClusters(Matrix<T> matrix)
    {
        var clusters = new List<Cluster>();
        var visited = new Matrix<bool>(matrix.Rows, matrix.Columns);

        foreach (var coord in matrix.Where(c => !visited[c]))
        {
            visited[coord] = true;

            if (!matrix[coord].Equals(_clusterValue))
                continue;

            var cluster = new ClusterBuilder<T>(matrix, visited).Build(coord);
            clusters.Add(cluster);
        }
        return clusters;
    }
}

ClusterBuilder

The recursive part of the algorithm. Uses a Matrix and a single member of a cluster to locate the other members in the same cluster.

internal class ClusterBuilder<T>
{
    private readonly Matrix<T> _matrix;
    private readonly Matrix<bool> _visited;

    public ClusterBuilder(Matrix<T> matrix, Matrix<bool> visited)
    {
        _matrix = matrix;
        _visited = visited;
    }

    public Cluster Build(Coord seed)
    {
        var clusterCoords = new List<Coord> {seed};
        Build(clusterCoords, seed);

        return new Cluster(clusterCoords);
    }

    private void Build(List<Coord> cluster, Coord current)
    {
        _visited[current] = true;

        var nextCoords = _matrix.GetEqualAdjacentCoords(current)
            .Where(c => !_visited[c]);

        foreach (var next in nextCoords)
        {
            cluster.Add(next);
            Build(cluster, next);
        }
    }
}

And most importantly, tests for the public API!

[TestFixture]
public class ClusterLocatorTests
{
    [Test]
    public void Throws_if_matrix_is_null()
    {
        var sut = new ClustersLocator<int>(1);

        Assert.Throws<ArgumentNullException>(() => sut.LocateClusters(null));
    }

    [Test]
    public void Returns_empty_collection_if_matrix_is_empty()
    {
        var sut = new ClustersLocator<int>(1);

        var clusters = sut.LocateClusters(EmptyMatrix);

        Assert.That(clusters, Is.Empty);
    }

    [TestCaseSource("GetLocatesClustersTestCases")]
    public void Locates_clusters(int[,] matrix, IEnumerable<Cluster> expectedClusters)
    {
        var sut = new ClustersLocator<int>(1);

        var clusters = sut.LocateClusters(matrix);

        Assert.That(clusters, Is.EqualTo(expectedClusters));
    }

    private static IEnumerable<ITestCaseData> GetLocatesClustersTestCases()
    {
        var testCase1 = new TestCaseData(Matrix1, Clusters1);
        testCase1.SetName("Large matrix of mixed clusters");

        // Add more test cases as needed
        return new[] {testCase1};
    }

    #region Test data
}

Answer 2

I would get rid of the continues on the for loop. They can get rather confusing, especially with three of them in there. You can use Enumerable.Range and Linq to do so:

foreach (var i in Enumerable.Range(thisM - 1, 3).Where(o => o >= 0 && o < m))
{
    foreach (var j in Enumerable.Range(thisN - 1, 3).Where(o => o >= 0 && o < n && i != thisM && o != thisN))
    {
        result.Add(i * n + j);
    }
}

That second for is a bit long, but we can rewrite this to something I think is more readable by creating ranges and using SelectMany as a cross join:

var rowRange = Enumerable.Range(thisM - 1, 3).Where(o => o >= 0 && o < m);
var colRange = Enumerable.Range(thisN - 1, 3).Where(o => o >= 0 && o < n);

result.AddRange(
    rowRange.SelectMany(o => colRange.Select(p => new {
        Row = o,
        Col = p
    })).
    Where(o => o.Row != thisM && o.Col != thisN).
    Select(o => o.Row * n + o.Col));

I changed the logic a little, because i == thisM && j < thisN seems to neglect to grab the item to the left of the current item. Also, var i = thisM in the for loop skips the entire row above the current item.

I would add the enumerable in the traverse method into the for loop:

foreach (var adj in GetAdjacent(curr))

You can cut out some code in Traverse by checking the first condition in the second if:

bool result = false;
if (matrix[curr] == 1 && !visited[curr])
{
    visited[curr] = true;
    ...
}

return result;

Instead of putting the WriteLine logic in the Traverse method, we can change the header of the Traverse method and let it populate a list of items visited by that cluster:

private bool Traverse(int curr, bool[] globalVisited, bool[] clusterVisited)
{
    if (matrix[curr] == 1 && !globalVisited[curr])
    {
        globalVisited[curr] = true;
        clusterVisited[curr] = true;

        foreach (var adj in GetAdjacent(curr))
            Traverse(adj, globalVisited, clusterVisited);
    }
    return clusterVisited.Any(o => o);
}

Then, in the PrintClusters method, we can add the printing logic:

public void PrintClusters()
{
    var globalVisited = new bool[m * n];
    var clusterVisited = new bool[m * n];

    for (var i = 0; i < m * n; i++)
    {
        Array.Clear(clusterVisited, 0, clusterVisited.Length);

        bool wasClusterVisited = Traverse(i, globalVisited, clusterVisited);
        if (wasClusterVisited)
        {
            foreach (var item in clusterVisited.Where(o => o).Select((o, index) => index))
            {
                var thisRow = item / n;
                var thisCol = item % n;
                Console.WriteLine("({0},{1})", thisRow, thisCol);
            }
            Console.WriteLine();
        }
    }
}

We could also beat a dead horse and pass an out parameter:

private bool Traverse(int curr, bool[] globalVisited, out bool[] clusterVisited)
{
    bool result = matrix[curr] == 1 && !globalVisited[curr];
    clusterVisited = new bool[globalVisited.Length];
    TraverseInternal(curr, globalVisited, clusterVisited);
    return result;
}
private void TraverseInternal(int curr, bool[] globalVisited, bool[] clusterVisited)
{
    if (matrix[curr] == 1 && !globalVisited[curr])
    {
        globalVisited[curr] = true;
        clusterVisited[curr] = true;

        foreach (var adj in GetAdjacent(curr))
            TraverseInternal(adj, globalVisited, clusterVisited);
    }
}

The algorithm you used is the way I've always seen it - flooding the matrix. I think my sister had this question at her first interview, and I think she did it the same way as well.

Answer 3

I believe there's a bug in the code. If we run this code:

var matrix = new[]
{
    0, 1, 0, 0,
    1, 1, 1, 1,
    0, 0, 0, 1,
    0, 1, 1, 1
};

new MatrixClusterFinder(matrix, 4, 4).PrintClusters();

It finds two clusters, printing

(0,1)(1,0)(1,1)(1,2)(1,3)(2,3)(3,2)(3,3)
(3,1)