The question I am attempting to solve (and have solved successfully):
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the ×ばつ20 grid?
(In case you need a link to the challenge.)
The purpose of this code review to to see if there are some obvious improvements that could be made to remove the massive amount of boilerplate code (or maybe even implement more lambda expressions).
public static void euler_11()
{
string inp = @"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";
int[] best4 = new int[4];
int biggestnum = 0;
int[][] workon = inp.Replace("\r", "").Split('\n').Select(n=>n.Split(' ').Select(m=>Int32.Parse(m)).ToArray()).ToArray(); //turning input into 2d int array
for (int i = 0; i < 20; i++)
for (int j = 0; j < 20; j++)
{
if (j <= 16) //horizontal "-"
{
if (workon[i][j] * workon[i][j + 1] * workon[i][j + 2] * workon[i][j + 3] > biggestnum)
{
best4 = new int[]{ workon[i][j] , workon[i][j + 1] , workon[i][j + 2] , workon[i][j + 3] };
biggestnum = workon[i][j] * workon[i][j + 1] * workon[i][j + 2] * workon[i][j + 3];
}
}
if (i <= 16) //vertical "|"
{
if (workon[i][j] * workon[i + 1][j] * workon[i + 2][j] * workon[i + 3][j] > biggestnum)
{
best4 = new int[] { workon[i][j] , workon[i + 1][j] , workon[i + 2][j] , workon[i + 3][j] };
biggestnum = workon[i][j] * workon[i + 1][j] * workon[i + 2][j] * workon[i + 3][j];
}
}
if (i <= 16 && j <= 16) //diagonal "X"
{
if (workon[i][j] * workon[i + 1][j + 1] * workon[i + 2][j + 2] * workon[i + 3][j + 3] > biggestnum) //down+right "\"
{
best4 = new int[] { workon[i][j] , workon[i + 1][j + 1] , workon[i + 2][j + 2] , workon[i + 3][j + 3] };
biggestnum = workon[i][j] * workon[i + 1][j + 1] * workon[i + 2][j + 2] * workon[i + 3][j + 3];
}
if (workon[i + 3][j] * workon[i + 2][j + 1] * workon[i + 1][j + 2] * workon[i][j + 3] > biggestnum) //up+right "/"
{
best4 = new int[] { workon[i + 3][j] , workon[i + 2][j + 1] , workon[i + 1][j + 2] , workon[i][j + 3] };
biggestnum = workon[i + 3][j] * workon[i + 2][j + 1] * workon[i + 1][j + 2] * workon[i][j + 3];
}
}
}
Console.WriteLine("best numbers were: " + best4[0] + " : " + best4[1] + " : " + best4[2] + " : " + best4[3] +"\n" + biggestnum);
}
1 Answer 1
LINQ's method syntax (which uses lambda expressions) is not that good for this problem because the problem has nested loops, and it would be nice to store intermediate values. LINQ's query syntax is great for both these things. First we create a helper method for calculating the product of a collection of integers:
public static int Product(IEnumerable<int> numbers) => numbers.Aggregate(1, (x, y) => x * y);
Then we declare the main method for getting the highest combination. I decided to make a line in four different directions for each point and check to make sure the line's points are in bounds before creating it.
public static int[] GetHighestCombo(int[][] numbers)
{
int height = numbers.Count();
int width = numbers[0].Count();
// Four directions to get combos: right, down-right, down, down-left
Point[] directions = new[] { new Point(1, 0), new Point(1, 1), new Point(0, 1), new Point(-1, 1) };
var combos =
(from y in Enumerable.Range(0, height)
from x in Enumerable.Range(0, width)
from direction in directions
let points = Enumerable.Range(0, 4).Select(i => new Point(x + i * direction.X, y + i * direction.Y)).ToArray()
where points.All(i => i.X >= 0 && i.X < width && i.Y < height)
let combo = points.Select(i => numbers[i.Y][i.X]).ToArray()
select combo).ToArray();
int max = combos.Max(Product);
return combos.First(x => Product(x) == max);
}
Then you can call the method like this:
int[] best4 = GetHighestCombo(workon);
int biggestnum = Product(best4);
A MaxBy() method would be useful and more efficient here. You can implement your own or find it in a library. I believe all the Project Euler problems have a solution that is a lot faster and more memory efficient than brute force. So you can try to figure that out for this problem next. For the later Project Euler problems, brute force is not an option.