adventofcode/2018/internal/day11/power.go

package day11

import (
	"internal/util"
)

const GridSize = 300

func GenerateGrid(serialNumber int) [][]int {
	grid := make([][]int, GridSize)
	for i := 0; i < GridSize; i++ {
		grid[i] = make([]int, GridSize)
	}

	// Calculate the power level in each fuel cell
	for y := 0; y < GridSize; y++ {
		for x := 0; x < GridSize; x++ {
			// Find the fuel cell's rack ID, which is its X coordinate plus 10.
			rackID := (x + 1) + 10
			// Begin with a power level of the rack ID times the Y coordinate.
			// Increase the power level by the value of the grid serial number (your puzzle input).
			// Set the power level to itself multiplied by the rack ID.
			power := ((rackID * (y + 1)) + serialNumber) * rackID

			// Keep only the hundreds digit of the power level (so 12345 becomes 3; numbers with no hundreds digit become 0).
			power = (power % 1000) / 100

			// Subtract 5 from the power level.
			power -= 5

			grid[y][x] = power
		}
	}

	return grid
}

func FindBestWindow3x3(grid [][]int) (int, int) {
	largest := sumNxN(grid, 0, 0, 3)
	bestX := 0
	bestY := 0

	for x := 1; x < GridSize-2; x++ {
		for y := 1; y < GridSize-2; y++ {
			sum := sumNxN(grid, x, y, 3)

			if sum > largest {
				largest = sum
				bestX = x
				bestY = y
			}
		}
	}

	return bestX + 1, bestY + 1
}

func sumNxN(grid [][]int, x, y, n int) int {
	total := 0

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			total += grid[y+i][x+j]
		}
	}

	return total
}

func FindBestWindow(grid [][]int) (int, int, int) {
	largest := grid[0][0]
	bestX := 0
	bestY := 0
	bestN := 1

	for x := 0; x < GridSize; x++ {
		for y := 0; y < GridSize; y++ {
			sum, n := findBestSquare(grid, x, y)

			if sum > largest {
				largest = sum
				bestX = x
				bestY = y
				bestN = n
			}
		}
	}

	return bestX + 1, bestY + 1, bestN
}

func findBestSquare(grid [][]int, x, y int) (int, int) {
	sum := grid[y][x]
	bestSum := sum
	bestN := 1

	for n := 2; n < util.Min(GridSize-y, GridSize-x); n++ {
		for i := y; i < y+n; i++ {
			sum += grid[i][x+n-1]
		}

		for i := x; i < x+n-1; i++ {
			sum += grid[y+n-1][i]
		}

		if sum > bestSum {
			bestSum = sum
			bestN = n
		}
	}

	return bestSum, bestN
}