advent of code day 8 O(n) solution

main.go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	file, err := os.Open("input.txt")
	if err != nil {
		panic(err)
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)

	// the grid
	values := [][]int{}

	// for each tree how far left can it see
	maxLeft := [][]int{}
	maxRight := [][]int{}

	for scanner.Scan() {
		s := scanner.Text()

		// maintain a mapping of the closest index we saw a value
		// e.g "the closest tree height 3 was at index 5"
		seenLeft := make([]int, 10)
		for i := range seenLeft {
			seenLeft[i] = -1
		}
		seenRight := make([]int, 10)
		for i := range seenRight {
			seenRight[i] = -1
		}

		currentLeft := make([]int, len(s))
		currentRight := make([]int, len(s))
		maxLeft = append(maxLeft, currentLeft)
		maxRight = append(maxRight, currentRight)
		current := make([]int, len(s))
		values = append(values, current)

		for i := range s {
			j := len(s) - 1 - i
			// turn "9" -> 9
			valueI := int(s[i]) - 48
			valueJ := int(s[j]) - 48

			current[i] = valueI

			if i == 0 {
				seenLeft[valueI] = i
				currentLeft[i] = 0

				seenRight[valueJ] = j
				currentRight[j] = 0

				continue
			}

			// find the closest tree of greater or equal height
			// this is O(1) and it's 0->9, not the grid width/height
			minIndexI := 0
			for lol := valueI; lol <= 9; lol++ {
				if seenLeft[lol] != -1 && seenLeft[lol] > minIndexI {
					minIndexI = seenLeft[lol]
				}
			}
			// how far to this greater or equal height tree
			currentLeft[i] = i - minIndexI

			minIndexJ := len(s) - 1
			for lol := valueJ; lol <= 9; lol++ {
				if seenRight[lol] != -1 && seenRight[lol] < minIndexJ {
					minIndexJ = seenRight[lol]
				}
			}
			currentRight[j] = minIndexJ - j

			seenLeft[valueI] = i
			seenRight[valueJ] = j

		}
	}

	maxTop := make([][]int, len(values))
	maxBottom := make([][]int, len(values))

	for x := 0; x < len(values[0]); x++ {

		seenTop := make([]int, 10)
		for i := range seenTop {
			seenTop[i] = -1
		}
		seenBottom := make([]int, 10)
		for i := range seenBottom {
			seenBottom[i] = -1
		}

		currentTop := make([]int, len(values))
		maxTop[x] = currentTop
		currentBottom := make([]int, len(values))
		maxBottom[x] = currentBottom

		for y := 0; y < len(values); y++ {
			y2 := len(values) - 1 - y
			valueI := values[y][x]
			valueJ := values[y2][x]

			if y == 0 {
				seenTop[valueI] = y
				currentTop[y] = 0

				seenBottom[valueJ] = y2
				currentBottom[y2] = 0
				continue
			}

			minIndexI := 0
			for lol := valueI; lol <= 9; lol++ {
				if seenTop[lol] != -1 && seenTop[lol] > minIndexI {
					minIndexI = seenTop[lol]
				}
			}
			currentTop[y] = y - minIndexI

			minIndexJ := len(values) - 1
			for lol := valueJ; lol <= 9; lol++ {
				if seenBottom[lol] != -1 && seenBottom[lol] < minIndexJ {
					minIndexJ = seenBottom[lol]
				}
			}
			currentBottom[y2] = minIndexJ - y2

			seenTop[valueI] = y
			seenBottom[valueJ] = y2
		}
	}

	maxScore := 0
	for y := 0; y < len(values); y++ {
		for x := 0; x < len(values[y]); x++ {
			score := 1

			score *= maxTop[x][y]
			score *= maxBottom[x][y]

			score *= maxLeft[y][x]
			score *= maxRight[y][x]

			if score > maxScore {
				maxScore = score
			}
		}
	}

	fmt.Println("done", maxScore)

}