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,
- 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). - 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 aGrid
class in another application and in that case it's better to haveCell
as a generic class since I can't know what I will store in the cells.