HackerRank NCR codesprint: Spiral Message

Question

Problem statement: https://www.hackerrank.com/contests/ncr-codesprint/challenges/spiral-message

You've intercepted an encoded spy message! The message originated as a single line of one or more space-separated words, but it was encoded into an matrix as a clockwise spiral starting in the lower left-hand corner. For example, the diagram below shows the decoding process for an encoded message:

The message is decoded spirally starting from the lower left-hand corner of the matrix and moving in the clockwise direction (i.e., up, right, down, left, up, right, etc.). From the starting position, you must clockwise-traverse the matrix, scanning characters and switching to the next clockwise direction each time you reach a boundary (i.e., an already-scanned character or the end of the matrix). Continue scanning characters in this manner until you've scanned all the matrix's characters into a single decoded string. The word separator for the decoded string is the hash mark (#).

Given n, m, and an encoded message, decode the message and print the number of words in the decoded message.

Input Format

The first line contains two space-separated positive integers describing the respective values of n and m. Each line i of the n subsequent lines contains a string of m characters describing row i of the encoded message.

Constraints

Each word consists of lowercase English alphabetic characters (a to z). The encoded message consists of words and hash marks (#). Each hash mark denotes a single space. 0

Print an integer denoting the number of decoded words.

Sample Input

3 5

a##ar

a#aa#

xxwsr

Sample Output

4

Explanation

The diagram at the top of the challenge demonstrates the decoding process for the given Sample Input. The decoded message is xaa##ar#rswx#aa. Because hash marks denote spaces, we can break the message into four words: xaa, ar, rswx, and aa. Thus, we print 4 as our answer.

My introduction of the algorithm: The algorithm is an easy one of NCR codesprint on HackerRank in Nov. 2016, but I like to ask help for code review. Since in the contest, I made a few mistakes, instead of starting from lower-left corner, the algorithm I did is from upper-left corner; Secondly, base cases: one node, one row, one column I did not test my algorithm.

After the contest, the submission of other players are not available, so I like to ask help here.

I made a few changes, for example, name function to include requirements: 1. start point: lowerLeft 2. spiral message: clockwise Instead of returning the count of decoded message, the function returns the spiral message, I added several test cases to test the spiral message's order is correct.

But, I like to get advice, make the C# solution better. Here is the code:

  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using System.Text;
  using System.Threading.Tasks;

  namespace SpiralMessage
  {
    class Program
    {
    /*
     * https://www.hackerrank.com/contests/ncr-codesprint/challenges/spiral-message
     *       
     * 
     */
    static void Main(string[] args)
    {
        //RunSampleTestCase(); 
        SpiralMessage();      
    }

    private static void RunTestcases()
    {
        TestOneChar();
        TestOneRow();
        TestingOneColumn();
        RunSampleTestCase(); 
    }       

    private static void RunSampleTestCase()
    {
        IList<string> input = new List<string>();
        input.Add("a##ar");
        input.Add("a#aa#");
        input.Add("xxwsr");

        string spiralMessage = SpiralMessageFromLowerLeftClockWise(input);
        Debug.Assert(spiralMessage.CompareTo("xaa##ar#rswx#aa") == 0);

        var result = spiralMessage.Split('#').ToList(); 
        result.RemoveAll(str => string.IsNullOrEmpty(str)); 
        Debug.Assert(result.Count == 4); 
    }        

    /*
     * One column test
     */
    private static void TestingOneColumn()
    {
        IList<string> input = new List<string>();
        input.Add("a");
        input.Add("#");
        input.Add("#");
        input.Add("a");
        input.Add("#");

        Debug.Assert(SpiralMessageFromLowerLeftClockWise(input).CompareTo("#a##a") == 0);
    }

    private static void TestOneRow()
    {
        IList<string> input = new List<string>();
        input.Add("a##a#");
        Debug.Assert(SpiralMessageFromLowerLeftClockWise(input).CompareTo("a##a#") == 0);
    }

    private static void TestOneChar()
    {
        IList<string> input = new List<string>();
        input.Add("a");
        Debug.Assert(SpiralMessageFromLowerLeftClockWise(input).CompareTo("a") == 0);
    }

    private static void SpiralMessage()
    {
        int[] arr = ToInt(Console.ReadLine().Split(' '));
        int rows = arr[0], cols = arr[1];

        IList<string> input = new List<string>();
        for (int i = 0; i < rows; i++)
        {
            input.Add(Console.ReadLine().Trim());
        }
        var result = SpiralMessageFromLowerLeftClockWise(input).Split('#').ToList(); 
        result.RemoveAll(str => string.IsNullOrEmpty(str));

        Console.WriteLine(result.Count());
    }

    /*
     * Dec. 8, 2016
     * Function spec: 
     * 1. Clockwise direction
     * 2. Start from lower left corner
     * 3. String can be counted using the hash mark (#)
     * Return: 
     * Spiral message instead of count of words
     */
    private static string SpiralMessageFromLowerLeftClockWise(IList<string> data)
    {
        int rows = data.Count;
        int cols = data[0].Length;

        int startX = 0, endX = rows - 1;
        int startY = 0, endY = cols - 1;

        StringBuilder sb = new StringBuilder();

        while (startX <= endX &&
               startY <= endY
            )
        {
            int nRows = endX - startX + 1;
            int mCols = endY - startY + 1;

            bool isOneNode = nRows == 1 && mCols == 1;
            bool isOneRow = nRows == 1;
            bool isOneCol = mCols == 1;

            bool downToUp    = false;
            bool leftToRight = false;
            bool upToDown    = false;
            bool rightToLeft = false;                

            // special case handling - one node, one row, one column
            if (isOneNode)                     
                downToUp = true;
            else if (isOneRow)   
            {
                downToUp = true;
                leftToRight = true;
            }
            else if (isOneCol)   
            {
                downToUp = true;
            }
            else
            {
                downToUp    = true;
                leftToRight = true;
                upToDown    = true;
                rightToLeft = true;
            }

            // 1. to upward
            if (downToUp)
                for (int i = endX; i >= startX; i--)
                {
                    char runner = data[i][startY];
                    sb.Append(runner);
                }

            // 2. to right   
            if (leftToRight)
                for (int j = startY + 1; j <= endY; j++)
                {
                    char runner = data[startX][j];
                    sb.Append(runner);
                }

            // 3. downward
            if (upToDown)
                for (int i = startX + 1; i <= endX; i++)
                {
                    char runner = data[i][endY];
                    sb.Append(runner);
                }

            // 4. to left 
            if (rightToLeft)
                for (int j = endY - 1; j > startY; j--)
                {
                    char runner = data[endX][j];
                    sb.Append(runner);
                }             

            startX++;
            endX--;
            startY++;
            endY--;
        }

        return sb.ToString(); 
    }                            

    private static int[] ToInt(string[] arr)
    {
        int len = arr.Length;
        int[] result = new int[len];
        for (int i = 0; i < len; i++)
        {
            result[i] = Convert.ToInt32(arr[i]);
        }

        return result;
    }
}
}

Because in the contest, test cases are kept private, I think that it is a good idea to design some test cases in the design process, special base cases. Best performer spends only less than 10% time I spent in the contest.

"Don't practice 'til you get it right. Practice 'til you can't get it wrong." I like to practice until I cannot get it wrong, specially on easy algorithm. Detail see my coding blog: http://juliachencoding.blogspot.ca/2016/12/hackerrank-ncr-codesprint-spiral-message.html

Answer 1

I think this needs to be separated into multiple modules and functions. If you do this, you can even docode messages encoded in various ways starting at any corner or (counter)clockwise.

This can be achieved by mixing functional and oo-programming.

---

The core part should be a class that can generate spiral coordinates and return them as IEnumerable<Point> like this totaly overengineered one.

static class Spiral
{
    public static IEnumerable<Point> Generate(int m, int n, Corner startAt, Direction direction)
    {
        var length = m * n;

        m--;
        n--;

        var corners = new Dictionary<Corner, Point>
        {
            [Corner.TopLeft] = new Point(0, 0),
            [Corner.TopRight] = new Point(m, 0),
            [Corner.BottomLeft] = new Point(0, n),
            [Corner.BottomRight] = new Point(m, n),
        };

        var boundary = new Dictionary<Tuple<Corner, Direction>, Boundary>
        {
            [Tuple.Create(Corner.TopLeft, Direction.Clockwise)] = new Boundary(0, m, 1, n),
            [Tuple.Create(Corner.TopRight, Direction.Clockwise)] = new Boundary(0, m - 1, 0, n),
            [Tuple.Create(Corner.BottomRight, Direction.Clockwise)] = new Boundary(0, m, 0, n - 1),
            [Tuple.Create(Corner.BottomLeft, Direction.Clockwise)] = new Boundary(1, m, 0, n),

            [Tuple.Create(Corner.TopRight, Direction.Counterclockwise)] = new Boundary(0, m, 1, n),
            [Tuple.Create(Corner.TopLeft, Direction.Counterclockwise)] = new Boundary(1, m, 0, n),
            [Tuple.Create(Corner.BottomLeft, Direction.Counterclockwise)] = new Boundary(0, m, 0, n - 1),
            [Tuple.Create(Corner.BottomRight, Direction.Counterclockwise)] = new Boundary(0, m - 1, 0, n),
        }
        [Tuple.Create(startAt, direction)];

        var pt = corners[startAt];

        var moveUp = new Func<bool>(() =>
        {
            pt.Y--;

            if (pt.Y == boundary.yMin)
            {
                boundary.yMin++;
                return false;
            }

            return true;
        });

        var moveRight = new Func<bool>(() =>
        {
            pt.X++;

            if (pt.X == boundary.xMax)
            {
                boundary.xMax--;
                return false;
            }

            return true;
        });

        var moveDown = new Func<bool>(() =>
        {
            pt.Y++;

            if (pt.Y == boundary.yMax)
            {
                boundary.yMax--;
                return false;
            }

            return true;
        });

        var moveLeft = new Func<bool>(() =>
        {
            pt.X--;

            if (pt.X == boundary.xMin)
            {
                boundary.xMin++;
                return false;
            }

            return true;
        });

        var moves = new Dictionary<Direction, Func<bool>[]>
        {
            [Direction.Clockwise] = new[] { moveRight, moveDown, moveLeft, moveUp },
            [Direction.Counterclockwise] = new[] { moveLeft, moveDown, moveRight, moveUp, },
        }
        [direction];

        var moveId = new Dictionary<Tuple<Corner, Direction>, int>
        {
            [Tuple.Create(Corner.TopLeft, Direction.Clockwise)] = 0,
            [Tuple.Create(Corner.TopRight, Direction.Clockwise)] = 1,
            [Tuple.Create(Corner.BottomRight, Direction.Clockwise)] = 2,
            [Tuple.Create(Corner.BottomLeft, Direction.Clockwise)] = 3,

            [Tuple.Create(Corner.TopRight, Direction.Counterclockwise)] = 0,
            [Tuple.Create(Corner.TopLeft, Direction.Counterclockwise)] = 1,
            [Tuple.Create(Corner.BottomLeft, Direction.Counterclockwise)] = 2,
            [Tuple.Create(Corner.BottomRight, Direction.Counterclockwise)] = 3,
        }
        [Tuple.Create(startAt, direction)];

        while (length > 0)
        {
            yield return pt;
            length--;

            if (moves[moveId]())
            {
                continue;
            }

            moveId++;
            if (moveId > moves.Length - 1)
            {
                moveId = 0;
            }
        }
    }
}

Internally it uses four methods to move in each direction: moveLeft, moveRight, moveTop, moveBottom. You can call them in the desired order to move in the desired direction and the few dictionaries let you configure each movement type, its starting points and starting boundaries.

---

To track the current boundaries you should create a struct for this.

struct Boundary
{
    public Boundary(int xMin, int xMax, int yMin, int yMax)
    {
        this.xMin = xMin;
        this.xMax = xMax;
        this.yMin = yMin;
        this.yMax = yMax;
    }

    public int xMin;
    public int xMax;
    public int yMin;
    public int yMax;
}

It's easier to use then separate variables that can be grouped together.

---

You can define some enums to specify where to start and in which direction.

enum Corner
{
    TopLeft,
    TopRight,
    BottomLeft,
    BottomRight
}

enum Direction
{
    Clockwise,
    Counterclockwise
}

---

The final part should be a method that utilizes the Spiral class to decode the message. It works as an extension for the string.

static class SpiralMessage
{ 
    public static IEnumerable<string> Decode(this string[] value)
    {
        var word = new StringBuilder();
        foreach (var pt in Spiral.Generate(value.First().Length, value.Length, Corner.BottomLeft, Direction.Clockwise))
        {
            var c = value[pt.Y][pt.X];
            if (c == '#')
            {
                if (word.Length > 0)
                {
                    yield return word.ToString();
                    word = new StringBuilder();
                }
            }
            else
            {
                word.Append(c);
            }
        }

        // yield the last word if any
        if (word.Length > 0)
        {
            yield return word.ToString();
            word = new StringBuilder();
        }
    }
}

---

Example:

var arr = new[]
{
    "a##ar",
    "a#aa#",
    "xxwsr"
};

var words = arr.Decode().ToList(); // xaa, ar, rswx, aa