1
\$\begingroup\$

I have to say without sounding arrogant, because I am only a novice coder, yet after looking at other's solutions, my solution is definitely not the shortest and most lightweight one and probably not even close to one of the most optimized ones. But! I think I have made a very readable solution and I think that it is true to the OOP paradigm.

Anyhow with that in mind everything can always be improved, I look forward to your feedback.

Problem 11

Largest product in a grid

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Program

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

Position

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

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

Cell

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

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

Grid

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

    }
}

Some final remarks,

  1. In the Grid constructor I know that I should've opted for accepting a int array instead of params int[] by the time I realized that it would have been smarter it was too late however, and changing it would've meant that I would've had to re-format the whole constructor call (indentations, line breaks and such).
  2. There is no need for the Cell class to be generic in this application, but my rationale behind it was, I re-use code like many others do, I might need to use a Grid class in another application and in that case it's better to have Cell as a generic class since I can't know what I will store in the cells.
\$\endgroup\$
2
\$\begingroup\$

You've built quite the object-oriented structure for this quite procedural assignment. Two of your classes are simple structures, which, I argue, are not even needed:

Cell contains a Value and a Position, but nowhere are both needed - all the outer loop cares about is the position, which it can simply iterate over (from [0,0] to [sizeY, sizeX]) without caring about Cell at all. Given position (x and y), the Grid class doesn't need the Cell object, since it knows where it is, and can simply get the value, so you might as well hold within your grid a two-dimensional array of values rather than cells.

You chose to implement GetNeighbours as a recursion, which is a curious choice. Why not simply iterate 4 steps in the required direction?

Some other minor ticks:

  1. If you do decide to make it a recursion, the overload of the GetNeighbours method with the internal List<int> should be private.
  2. GetNeighbours does not actually get neighbours, it gets neighbours' values, and should be named GetNeighbourValues.
  3. Don't iterate over Direction values using int - iterate over the values:

    var directions = Enum.GetValues(typeof(Direction));
    
    foreach (Direction direction in directions)
    {
       // ...
    
  4. You need only half the directions - since you'll get the same results for Left and Right, Up and Down, etc.

I would suggest a simple, procedural solution:

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.