HackerRank NCR代码打印:螺旋信息

Question

问题陈述：https://www.hackerrank.com/contests/ncr-codesprint/challenges/spiral-message

你截获了一条被编码的间谍消息！该消息起源于一个或多个空格分隔单词的一行，但它被编码成一个矩阵，作为顺时针螺旋开始于左下角。例如，下图显示了编码消息的解码过程：

从矩阵的左下角开始对消息进行螺旋解码，并沿顺时针方向移动(即向上、右、下、左、上、右等)。从起始位置开始，每次到达边界(即已经扫描的字符或矩阵的末尾)时，必须顺时针遍历矩阵、扫描字符并切换到下一个顺时针方向。继续以这种方式扫描字符，直到将矩阵的所有字符扫描成一个已解码的字符串为止。解码字符串的单词分隔符是散列标记(#)。

给定n，m和编码消息，解码消息并打印解码消息中的字数。

输入格式

第一行包含两个空格分隔的正整数，分别描述n和m的值，n行后继行的每一行I都包含描述编码消息的第一行的m个字符串。

约束条件

每个单词由小写英文字母组成(a到z)。编码的消息由单词和散列标记(#)组成。每个散列标记表示单个空格。0

打印一个整数，表示已解码的字数。

样本输入

3 5

a##ar

a#aa#

xxwsr

样本输出

4.

解释

质询顶部的图表演示了给定示例输入的解码过程。解码的消息是xaa##ar#rswx#aa。因为散列标记表示空格，所以我们可以将消息分解为四个单词: xaa、ar、rswx和aa。因此，我们打印4作为我们的答案。

我对算法的介绍:该算法是2016年11月HackerRank上的一种简单的NCR代码，但我喜欢寻求代码评审的帮助。因为在比赛中，我犯了一些错误，而不是从左下角开始，我做的算法是从左上角开始的；第二，基本情况:一个节点，一行，一个列，我没有测试我的算法。

比赛结束后，其他选手都无法投稿，所以我想在这里寻求帮助。

我做了一些修改，例如，名称函数包括要求: 1.开始点: lowerLeft 2.螺旋消息:顺时针方向返回螺旋消息的计数，函数返回螺旋消息，我添加了几个测试用例来测试螺旋消息的顺序是否正确。

但是，我喜欢得到建议，使C#解决方案更好。以下是代码：

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

因为在比赛中，测试用例是保密的，所以我认为在设计过程中设计一些测试用例是个好主意。最好的表演者只花了不到10%的时间在比赛中。

“在你正确之前不要练习，直到你不能弄错为止。”我喜欢练习直到我不能弄错，特别是在简单算法上。详情见我的编码博客：http://juliachencoding.blogspot.ca/2016/12/hackerrank-ncr-codesprint-spiral-message.html。

Answer 1

我认为这需要分成多个模块和功能。如果这样做，您甚至可以从顺时针的任意角或(计数器)开始以各种方式对编码的消息进行编码。

这可以通过混合函数和对象编程来实现。

核心部分应该是一个类，它可以生成螺旋坐标，并将它们作为IEnumerable<Point>返回，就像这样完全过度设计了一个。

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

在内部，它使用四种方法向每个方向移动：moveLeft、moveRight、moveTop、moveBottom。您可以按所需的顺序调用它们，使其朝着所需的方向移动，而少数字典则允许您配置每种移动类型、其起点和起始边界。

要跟踪当前的边界，您应该为此创建一个结构。

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

它更容易使用，然后单独的变量，可以分组在一起。

您可以定义一些枚举来指定从何处开始和向哪个方向开始。

enum Corner
{
    TopLeft,
    TopRight,
    BottomLeft,
    BottomRight
}

enum Direction
{
    Clockwise,
    Counterclockwise
}

最后一部分应该是利用Spiral类解码消息的方法。它作为字符串的扩展。

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

示例：

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

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