# [Golang] Largest product in a grid - Problem 11 - Project Euler

Problem: [1]

In the 20×20 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 × 63 × 78 × 14 = 1788696.

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

Solution:

87 x 97 x 94 x 89 = 70600674

First number located at (15, 3) (zero based indexing)

direction: right*up to left*down

```package main

import (
"fmt"
"strconv"
"strings"
)

const grid20x20 = `
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
`

func parseLine(l string) []int64 {
var dl []int64

numbers := strings.Split(l, " ")
for _, number := range numbers {
n, err := strconv.ParseInt(number, 10, 0)
if err != nil {
panic(err)
}
dl = append(dl, n)
}
return dl
}

func parseGrid20x20(g string) (grid [][]int64) {
lines := strings.Split(g, "\n")
for _, line := range lines[1 : len(lines)-1] {
dl := parseLine(line)
grid = append(grid, dl)
}
return
}

func printMaxProductInfo(m int64, i, j int, a, b, c, d int64, dir string) {
fmt.Println(m)
fmt.Println(i, j)
fmt.Println("direction: ", dir)
fmt.Println(a, b, c, d)
}

func findGreatesProduct(grid [][]int64) {
var max int64
var maxi, maxj int
var direction string
var a, b, c, d int64

// left-right
for i := 0; i <= 19; i++ {
for j := 0; j <= 16; j++ {
prd := grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3]
if prd > max {
max = prd
maxi = i
maxj = j
direction = "left-right"
a = grid[i][j]
b = grid[i][j+1]
c = grid[i][j+2]
d = grid[i][j+3]
}
}
}

// up-down
for i := 0; i <= 16; i++ {
for j := 0; j <= 19; j++ {
prd := grid[i][j] * grid[i+1][j] * grid[i+2][j] * grid[i+3][j]
if prd > max {
max = prd
maxi = i
maxj = j
direction = "up-down"
a = grid[i][j]
b = grid[i+1][j]
c = grid[i+2][j]
d = grid[i+3][j]
}
}
}

// diagonal: left*up to right*down
for i := 0; i <= 16; i++ {
for j := 0; j <= 16; j++ {
prd := grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3]
if prd > max {
max = prd
maxi = i
maxj = j
direction = "left*up to right*down"
a = grid[i][j]
b = grid[i+1][j+1]
c = grid[i+2][j+2]
d = grid[i+3][j+3]
}
}
}

// diagonal: right*up to left*down
for i := 3; i <= 19; i++ {
for j := 0; j <= 16; j++ {
prd := grid[i][j] * grid[i-1][j+1] * grid[i-2][j+2] * grid[i-3][j+3]
if prd > max {
max = prd
maxi = i
maxj = j
direction = "right*up to left*down"
a = grid[i][j]
b = grid[i-1][j+1]
c = grid[i-2][j+2]
d = grid[i-3][j+3]
}
}
}

printMaxProductInfo(max, maxi, maxj, a, b, c, d, direction)
}

func main() {
grid := parseGrid20x20(grid20x20)
findGreatesProduct(grid)
}
```

Tested on: Go Playground

References: