Project Euler: Problem 11

In the 20x20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is $26 \times 63 \times 78 \times 14 = 1\,788\,696$.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the $20 \times 20$ grid?

– Project Euler Problem 11

Solution

Not really much interesting you can do with this one really. Going through the whole grid while checking every single possibility is really the only way you can do it. We have to take every number in the grid and multiply it with the three numbers to the left of it, below it, diagonally up to the right, and so on, like shown in the table below:

However, this way we would actually be checking all the possibilities twice though, because a product doesn't care in what order its factors are. This means we can for example just check the ones to the right and not the ones to the left, and pretty much cut the number of checks in half. We then end up with only four of the original eight "arms" of factors to multiply, as shown in the table below:

I put the grid in a two dimensional array and then just looped through all of them looking for the highest product. It is very simple to make. Only thing that can be a bit tricky is to make sure you do try out all the possibilities without going out the side the array bounds. Anyways, you can see my result below.

var grid = new[,]
    {
        {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 rows = grid.GetLength(0);
var columns = grid.GetLength(1);

var greatest = 0;

for (var r = 0; r < rows; r++)
    for (var c = 0; c < columns; c++)
    {
        if (c < columns - 3)
        {
            // Right and "Left"
            greatest = Math.Max(greatest, Grid[r, c] * Grid[r, c + 1] * Grid[r, c + 2] * Grid[r, c + 3]);
        }

        if (r < rows - 3)
        {
            // Down and "Up"
            greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c] * Grid[r + 2, c] * Grid[r + 3, c]);

            // Diagonally, down to the right
            if (c < columns - 3)
                greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c + 1] * Grid[r + 2, c + 2] * Grid[r + 3, c + 3]);

            // Diagonally, down to the left
            if (c > 3)
                greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c - 1] * Grid[r + 2, c - 2] * Grid[r + 3, c - 3]);
        }
    }

var answer = greatest;

And that's pretty much it! Takes around 150 ticks, and is not really interesting to be honest. 😛

Next Euler problem however is a bit more tricky... will write about that one next, so stay tuned. 🙂