Spiral printing of 2D matrix

Question

Please comment about code complexity, and coding style, I'm preparing for a code interview, so any comment would be appreciated.

Example:

Input

1    2   3   4
5    6   7   8
9   10  11  12
13  14  15  16

Output:

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Code:

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{

    //Spiral printing of 2D matrix.
    [TestClass]
    public class Spiral2Dmatrixprint
    {
        [TestMethod]
        public void TestSpiralPrint()
        {
            int[,] matrix = new int[3, 3];
            matrix[0, 0] = 1; matrix[0, 1] = 2; matrix[0, 2] = 3;
            matrix[1, 0] = 8; matrix[1, 1] = 9; matrix[1, 2] = 4;
            matrix[2, 0] = 7; matrix[2, 1] = 6; matrix[2, 2] = 5;
            SpiralPrint(matrix);

        }

        private void SpiralPrint(int[,] matrix)
        {
            int colRight = 2;
            int colLeft = 0;
            int rowTop = 0;
            int rowEnd = 2;

            PrintRight(matrix, colLeft, colRight, rowTop, rowEnd);
        }

        private void PrintRight(int[,] matrix, int colLeft, int colRight, int rowTop, int rowEnd)
        {
            if (colRight == colLeft && rowTop == rowEnd)
            {
                System.Diagnostics.Debug.Write(matrix[colRight,rowTop]);
                return;
            }
            for (int i = colLeft; i <= colRight; i++)
            {
                System.Diagnostics.Debug.Write(matrix[rowTop, i]);
            }
            PrintDown(matrix, colLeft, colRight, ++rowTop, rowEnd);
        }

        private void PrintDown(int[,] matrix, int colLeft, int colRight, int rowTop, int rowEnd)
        {
            if (colRight == colLeft && rowTop == rowEnd)
            {
                return;
            }
            for (int i = rowTop; i <= rowEnd; i++)
            {
                System.Diagnostics.Debug.Write(matrix[i, colRight]);
            }
            PrintLeft(matrix, colLeft, --colRight, rowTop, rowEnd);
        }

        private void PrintLeft(int[,] matrix, int colLeft, int colRight, int rowTop, int rowEnd)
        {
            if (colRight == colLeft && rowTop == rowEnd)
            {
                return;
            }
            for (int i = colRight; i >= colLeft; i--)
            {
                System.Diagnostics.Debug.Write(matrix[rowEnd, i]);
            }
            PrintUp(matrix, colLeft, colRight, rowTop, --rowEnd);
        }

        private void PrintUp(int[,] matrix, int colLeft, int colRight, int rowTop, int rowEnd)
        {
            if (colRight == colLeft && rowTop == rowEnd)
            {
                return;
            }
            for (int i = rowEnd; i >= rowTop; i--)
            {
                System.Diagnostics.Debug.Write(matrix[i, colLeft]);
            }
            PrintRight(matrix, ++colLeft, colRight, rowTop, rowEnd);
        }
    }
}

Answer 1

The first thing I noticed is that you chose to do it in a test fixture but are creating output it as if it were a console app. Personally, I would have written it as a console app, but I think the test fixture is a better idea .. as long as you stay consistent.

If you're writing a test, you need an assert. A test without an assert is a definite red flag. Something like this would be perfect.

Assert.AreEqual("1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10", outputText);

As for the matrix initialization, I believe you have an off-by-one error (int[3, 3] should be int[4, 4]). I think you should generate the matrix with a nested for loop as well so you can test your algorithm at different sizes; it is pretty simple after all.

Here's the test I would have created

[TestMethod]
public void TestWithSupportingTraversionClass()
{
    // arrange
    var matrix = GenerateMatrix(4, 4);

    // act
    List<int> results = ProcessInQuestion(matrix);

    // assert
    string outputText = string.Join(" ", results.ToArray());
    Assert.AreEqual("1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10", outputText);
}

Now for the meat of the actual test question, the biggest thing for me, is the chaining together of the PrintX() methods is pretty ugly (sorry). It has a very procedural feel to it. SpiralPrint() calls PrintRight(), which calls PrintDown(), which calls PrintLeft(), which calls PrintUp(), which calls PrintRight() ... etc, etc... in an endless daisy chain which is troubling and a total red flag, IMHO.

Ok, so how do you write a loop for this? It appears simple, but admittedly is just enough complexity to make it difficult. Throwing all the complexity of this algorithm into a loop would be a bit of a mess, so you're going to need another class to maintain the state for each dimension (min, max, direction, incrementing, etc...). This additional simple class will allow you to keep your loop relatively clean.

Here's what I came up with for the entire algorithm ...

private static List<int> ProcessInQuestion(int[,] matrix)
{
    var results = new List<int>();
    var y = new DimensionTraversionDetails { MaxIndex = matrix.GetLength(0) - 1 };
    var x = new DimensionTraversionDetails { MaxIndex = matrix.GetLength(1) - 1 };
    var traversingDimension = x;

    results.Add(matrix[y.CurrentIndex, x.CurrentIndex]);
    while (y.CanIncrement || x.CanIncrement)
    {
        if (!traversingDimension.CanIncrement)
        {
            traversingDimension.ToggleDirection();
            traversingDimension = (traversingDimension == x) ? y : x;
            traversingDimension.UpdateBoundary();
        }

        traversingDimension.Increment();
        results.Add(matrix[y.CurrentIndex, x.CurrentIndex]);
    }

    return results;
}

As you can see, the DimensionTraversionDetails class hides a lot of the complexity, even though that class is also extremely simple as well. Here it is ...

internal class DimensionTraversionDetails
{
    public int CurrentIndex { get; private set; }
    public int MinIndex { get; set; }
    public int MaxIndex { get; set; }
    private int Direction { get; set; }

    public DimensionTraversionDetails()
    {
        Direction = 1;
    }

    public void Increment()
    {
        if (!CanIncrement) throw new InvalidOperationException("Cannot increment");
        CurrentIndex = GetNextIndex();
    }

    public void ToggleDirection()
    {
        Direction *= -1;
    }

    public bool CanIncrement
    {
        get
        {
            int nextIndex = GetNextIndex();
            return nextIndex >= MinIndex
                && nextIndex <= MaxIndex;
        }
    }

    private int GetNextIndex()
    {
        return CurrentIndex + Direction;
    }

    internal void UpdateBoundary()
    {
        if (Direction > 0)
            MinIndex = CurrentIndex + 1;
        else
            MaxIndex = CurrentIndex - 1;
    }
}

To be honest, I suspect there's a simpler solution where the DimensionTraversionDetails class isn't necessary and cell padding is discounted based on the number of times around the matrix, but the answer eludes me at the moment.

Answer 2

Hard code col and row counts is not good

int colRight = 2;
int colLeft = 0;
int rowTop = 0;
int rowEnd = 2;

Test method should print out results - not method

I think this will fail if the matrix is not square

if (colRight == colLeft && rowTop == rowEnd)

I think this is cleaner

public static void TestSpiralPrint()
{
    int[,] matrix = new int[5, 4];
    matrix[0, 0] = 1;  matrix[0, 1] = 2;  matrix[0, 2] = 3;  matrix[0, 3] = 4;
    matrix[1, 0] = 5;  matrix[1, 1] = 6;  matrix[1, 2] = 7;  matrix[1, 3] = 8;
    matrix[2, 0] = 9;  matrix[2, 1] = 10; matrix[2, 2] = 11; matrix[2, 3] = 12;
    matrix[3, 0] = 13; matrix[3, 1] = 14; matrix[3, 2] = 15; matrix[3, 3] = 16;
    matrix[4, 0] = 17; matrix[4, 1] = 18; matrix[4, 2] = 19; matrix[4, 3] = 20;
    List<int> output = SpiralPrint(matrix);
    foreach (int i in output)
        Debug.WriteLine(i);
    Debug.WriteLine("");
}
private static List<int> SpiralPrint(int[,] matrix)
{
    List<int> output = new List<int>();
    if (matrix.Length > 0)
    {
        int top = 0;
        int btm = matrix.GetLength(0);
        int lft = 0;
        int rht = matrix.GetLength(1);

        while (lft < rht && top < btm)
        {
            for (int i = lft; i < rht; i++)
                output.Add(matrix[top, i]);
            top++;

            for (int i = top; i < btm; i++)
                output.Add(matrix[i, rht - 1]);
            rht--;

            if (lft < rht)
            {
                for (int i = rht - 1; i >= lft; i--)
                    output.Add(matrix[btm - 1, i]);
                btm--;
            }

            if (top < btm)
            {
                for (int i = btm - 1; i >= top; i--)
                    output.Add(matrix[i, lft]);
                lft++;
            }
        }
    }
    return output;
}