aoc2021/fifteen/path.go

package fifteen

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type path struct {
	riskLevel [][]int
	width     int
	height    int
}

type point struct {
	x int
	y int
}

func (p *path) load(filename string) error {
	file, err := os.Open(filename)
	if err != nil {
		return err
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)

	p.riskLevel = [][]int{}
	for scanner.Scan() {
		row := []int{}
		for _, n := range strings.Split(scanner.Text(), "") {
			v, err := strconv.Atoi(string(n))
			if err != nil {
				return err
			}

			row = append(row, v)
		}
		p.riskLevel = append(p.riskLevel, row)
	}

	p.height = len(p.riskLevel)
	p.width = len(p.riskLevel[0])

	return nil
}

func (p *path) scale(sizeX int, sizeY int) *path {
	scaledPath := &path{
		width:  p.width * sizeX,
		height: p.height * sizeY,
	}

	scaledPath.riskLevel = make([][]int, scaledPath.height)
	for i := 0; i < scaledPath.height; i++ {
		scaledPath.riskLevel[i] = make([]int, scaledPath.width)
	}

	for i := 0; i < sizeX; i++ {
		for j := 0; j < sizeY; j++ {
			for y := 0; y < p.height; y++ {
				for x := 0; x < p.width; x++ {
					risk := p.riskLevel[y][x] + i + j
					for risk > 9 {
						risk -= 9
					}

					scaledPath.riskLevel[(j*p.height)+y][(i*p.width)+x] = risk
				}
			}
		}
	}

	return scaledPath
}

func (p *path) print() {
	for y := 0; y < p.height; y++ {
		row := ""
		for x := 0; x < p.width; x++ {
			row += fmt.Sprintf("%d", p.riskLevel[y][x])
		}
		fmt.Println(row)
	}
}

func (p *path) totalRisk() int {
	start := point{
		x: 0,
		y: 0,
	}
	end := point{
		x: p.width - 1,
		y: p.height - 1,
	}

	path := p.path(start, end)
	total := 0

	for i, point := range path {
		if i == 0 {
			continue
		}
		total += p.riskLevel[point.y][point.x]
	}

	return total
}

func minValue(distance map[point]int, nodes []point) (point, []point) {
	var min *point
	remaining := []point{}

	for i := range nodes {
		if min == nil {
			min = &nodes[i]
			continue
		}

		if distance[nodes[i]] < distance[*min] {
			remaining = append(remaining, *min)
			min = &nodes[i]
		} else {
			remaining = append(remaining, nodes[i])
		}
	}

	return *min, remaining
}

func contains(nodes []point, x int, y int) bool {
	for _, n := range nodes {
		if n.x == x && n.y == y {
			return true
		}
	}
	return false
}

func (p *path) path(start point, end point) []point {
	dist := map[point]int{}
	prev := map[point]point{}
	nodes := []point{}

	for y := 0; y < p.height; y++ {
		for x := 0; x < p.width; x++ {
			point := point{x: x, y: y}
			// Virtually infinite for worst case
			dist[point] = 10 * (p.width + p.height)
			nodes = append(nodes, point)
		}
	}
	dist[start] = 0

	for len(nodes) > 0 {
		current, newNodes := minValue(dist, nodes)

		// Check neigbours
		neighbours := []point{}
		// left
		if current.x > 0 && contains(newNodes, current.x-1, current.y) {
			left := point{
				x: current.x - 1,
				y: current.y,
			}
			neighbours = append(neighbours, left)
		}
		// up
		if current.y > 0 && contains(newNodes, current.x, current.y-1) {
			up := point{
				x: current.x,
				y: current.y - 1,
			}
			neighbours = append(neighbours, up)
		}
		// right
		if current.x < p.width-1 && contains(newNodes, current.x+1, current.y) {
			right := point{
				x: current.x + 1,
				y: current.y,
			}
			neighbours = append(neighbours, right)
		}
		// down
		if current.y < p.height-1 && contains(newNodes, current.x, current.y+1) {
			down := point{
				x: current.x,
				y: current.y + 1,
			}
			neighbours = append(neighbours, down)
		}

		for _, n := range neighbours {
			cost := dist[current] + p.riskLevel[n.y][n.x]
			if cost < dist[n] {
				dist[n] = cost
				prev[n] = current
			}
		}

		nodes = newNodes
	}

	path := []point{end}
	index := end
	for index != start {
		prefix := []point{prev[index]}
		path = append(prefix, path...)
		index = prev[index]
	}

	return path
}