项目Euler 11 -网格中最大的产品

Question

我不得不直截了当地说，因为我只是一个新手，但是在看了别人的解决方案之后，我的解决方案肯定不是最短和最轻量级的解决方案，甚至可能还没有接近最优化的解决方案之一。但!我认为我已经做了一个非常易读的解决方案，并且我认为它对OOP范式是正确的。

无论如何，考虑到这一点，一切都可以改进，我期待你的反馈。

问题11网格中的最大乘积是20×20网格中四个相邻数在同一方向(上、下、左、右、对角)的最大乘积？

程序

static void Main(string[] args)
{
            var grid = new Grid           (20, 20, // This is the size of the grid <-
                                           08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08,
                                           49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
                                           81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
                                           52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
                                           22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
                                           24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50,
                                           32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
                                           67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21,
                                           24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
                                           21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
                                           78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92,
                                           16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
                                           86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
                                           19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
                                           04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
                                           88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
                                           04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36,
                                           20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
                                           20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
                                           01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48);
            
            var greatestProducts = new HashSet<int>();

            // Okay let's loop through all numbers in the grid and find the one with the greatest product

            foreach (Cell<int> cell in grid)
            {
                int[] sums = new int[8];
                for (int i = 0; i < 8; i++)
                {
                    var neighbours = grid.GetNeighbours(cell, (Direction)i, 4);
                    if(neighbours.Count > 0 ) 
                    {
                        sums[i] = neighbours.Aggregate((a, b) => a * b);
                    }
                }
                greatestProducts.Add(sums.Max());
            }

            Console.WriteLine(greatestProducts.Max());
            Console.ReadKey();
        }

位置

struct Position
    {
        public readonly int Row;
        public readonly int Column;

        public Position(int row, int column)
        {
            Row = row;
            Column = column;
        }
    } 

细胞

class Cell<T>
    {
        public readonly T Value;
        public readonly Position Position;

        public Cell(Position position, T value)
        {
            Value = value;
            Position = position;
        }
    }

网格

enum Direction
    {
        Left, Right, Up, Down,
        DiagonalUpperLeft, DiagonalLowerLeft,
        DiagonalUpperRight, DiagonalLowerRight
    }

    class Grid
    {
        private Cell<int>[,] cells;
        public Cell<int> this[int row, int column]
        {
            get { return cells[row, column]; }
        }

        public Grid(int sizeY, int sizeX, params int[] numbers)
        {
            cells = new Cell<int>[sizeY, sizeX];
            int m = 0;

            for (int i = 0; i < cells.GetLength(0); i++)
            {
                for (int j = 0; j < cells.GetLength(1); j++)
                {
                    cells[i, j] = new Cell<int>(new Position(i, j), numbers[m++]);
                }
            }
        }

        public System.Collections.IEnumerator GetEnumerator()
        {
            return cells.GetEnumerator();
        }

        public List<int> GetNeighbours(Cell<int> cell, Direction direction, int neighboursToGet)
        {
            return GetNeighbours(cell, direction, neighboursToGet, new List<int>());
        }

        public List<int> GetNeighbours(Cell<int> cell, Direction direction, int neighboursToGet, List<int> neighbours)
        {
            if (neighboursToGet > 0)
            {
                int x = 0;
                int y = 0;
                Cell<int> neighbour;

                switch (direction)
                {
                    case Direction.Left:
                        x = cell.Position.Column - 1;
                        break;
                    case Direction.Right:
                        x = cell.Position.Column + 1;
                        break;
                    case Direction.Up:
                        y = cell.Position.Row - 1;
                        break;
                    case Direction.Down:
                        y = cell.Position.Row + 1;
                        break;
                    case Direction.DiagonalLowerLeft:
                        y = cell.Position.Row + 1;
                        x = cell.Position.Column - 1;
                        break;
                    case Direction.DiagonalUpperLeft:
                        y = cell.Position.Row - 1;
                        x = cell.Position.Column - 1;
                        break;
                    case Direction.DiagonalLowerRight:
                        y = cell.Position.Row + 1;
                        x = cell.Position.Column + 1;
                        break;
                    case Direction.DiagonalUpperRight:
                        y = cell.Position.Row - 1;
                        x = cell.Position.Column + 1;
                        break;
                }

                //Check so there are more cells to get
                if (x < cells.GetLowerBound(0) || x > cells.GetUpperBound(0) || y < cells.GetLowerBound(0) || y > cells.GetUpperBound(0))
                {
                    return neighbours;
                }

                neighbour = cells[y, x];
                neighbours.Add(neighbour.Value);
                GetNeighbours(neighbour, direction, neighboursToGet - 1, neighbours);
            }
            return neighbours;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < cells.GetLength(0); i++)
            {
                for (int j = 0; j < cells.GetLength(1); j++)
                {
                    if (cells[j, i].Value < 10)
                    {
                        sb.Append("0" + cells[j, i].Value + " ");
                    } 
                    else
                    {
                        sb.Append(cells[j, i].Value + " ");
                    }
                }
                sb.AppendLine(); // Line break here
            }
            return sb.ToString();
        }

    }
}

最后几句话，

1. 在Grid构造函数中，我知道当我意识到它会更聪明时，我应该选择接受int数组而不是params int[]，但是，更改它意味着我必须重新格式化整个构造函数调用(缩进、换行等等)。
2. 在这个应用程序中，不需要Cell类是泛型的，但我的基本原理是，我和许多其他应用程序一样重复使用代码，我可能需要在另一个应用程序中使用Grid类，在这种情况下，最好将Cell作为泛型类，因为我不知道我将在单元格中存储什么。

Answer 1

您已经为这个非常过程化的任务构建了非常面向对象的结构。您的两个类是简单的结构，我认为它们甚至不需要：

Cell包含一个Value和一个Position，但是两者都不需要--外部循环所关心的只是位置，它可以简单地迭代(从[0,0]到[sizeY, sizeX])，而根本不关心Cell。给定位置(x和y)，Grid类不需要Cell对象，因为它知道它在哪里，并且可以简单地获取值，所以您最好在网格中保存一个二维值数组，而不是单元格。

您选择将GetNeighbours实现为递归，这是一个奇怪的选择。为什么不简单地按照所需的方向迭代4步呢？

其他一些小滴答：

1. 如果您确实决定将其作为递归，则GetNeighbours方法与内部List<int>的重载应该是private。
2. GetNeighbours实际上不是邻居，而是邻居的值，应该命名为GetNeighbourValues。
3. 不要使用Direction值迭代int -对值进行迭代: var方向=Enum.GetValues(类型(方向))；foreach (指向方向){ // .
4. 你只需要一半的方向-因为你会得到相同的结果Left和Right，Up和Down等。

我建议一个简单、程序性的解决办法：

public static void Main(string[] args) {
    var grid = new int[20,20] { ... };
    Console.WriteLine(MaxProduct(grid));
}

public int MaxProduct(int[,] grid) {
    var products = new HashSet<int>();
    var directions = Enum.GetValues(typeof(Direction));

    for (int y = 0; y < grid.getLength(0); y++) {
        for (int x = 0; x < grid.getLength(1); x++) {
            foreach (Direction direction in directions) {
                products.Add(GetProductFor(grid, x, y, direction, 4))
            }
        }
    }
    return products.Max();
}

private directionMap = new Dictionary<Direction, int[]>()
{
    {Right, {0, 1}},
    {Down, {1, 0}},
    {DiagonalUpperLeft, {-1, -1}},
    {DiagonalLowerLeft, {1, -1}}
};

public int GetProductFor(int[,] grid, int x, int y, Direction direction, int length) {
    int result = 1;
    for (int i = 0; i < length; i++) {
        result *= grid[y + directionMap[direction][0]*length]
                      [x + directionMap[direction][1]*length];
    }
    return result;
}