adventofcode/2021/day15/main.go

package main

import (
	"fmt"
	"os"

	h "git.bullercodeworks.com/brian/adventofcode/helpers"
)

var cave h.CoordByteMap
var debug bool

func main() {
	debug = len(os.Args) > 1 && os.Args[1] == "--debug"
	inp := h.StdinToStringSlice()
	cave = h.StringSliceToCoordByteMap(inp)
	fmt.Println("# Part 1")
	part1()
	fmt.Println("# Part 2")
	part2()
}

var visited map[h.Coordinate]bool
var distance map[h.Coordinate]int
var curr h.Coordinate

func part1() {
	distance = make(map[h.Coordinate]int)
	visited = make(map[h.Coordinate]bool)
	for k := range cave.Field {
		visited[k] = false
		distance[k] = h.MAX_INT
	}
	curr = h.Coordinate{
		X: 0,
		Y: 0,
	}
	distance[curr] = 0
	visited[curr] = true

	work()
	fmt.Println(distance[h.Coordinate{X: cave.Width - 1, Y: cave.Height - 1}])
}

func work() {
	// Find the unvisited node with the smallest tentative distance
	var c h.Coordinate
	cDist := h.MAX_INT
	for k, v := range distance {
		if visited[k] {
			continue
		}
		if v < cDist {
			cDist = v
			c = k
		}
	}

	check := getNeighbors(c)
	for _, v := range check {
		if !visited[v] {
			if b, ok := distance[v]; !ok || b > distance[c]+getInt(v) {
				distance[v] = distance[c] + getInt(v)
			}
		}
	}
	visited[c] = true

	// if we still have unvisited nodes, recurse
	if moreWork() {
		work()
	}
}

func moreWork() bool {
	for i := range visited {
		if visited[i] == false {
			return true
		}
	}
	return false
}

func part2() {
	// Build the full cave
	expandCave(5)
	part1()
}

func getInt(c h.Coordinate) int {
	return int(cave.Opt(c, '0')) - int('0')
}

func getNeighbors(c h.Coordinate) []h.Coordinate {
	var ret []h.Coordinate
	for _, n := range []h.Coordinate{c.North(), c.East(), c.South(), c.West()} {
		if v := cave.Opt(n, 'Z'); v != 'Z' {
			ret = append(ret, n)
		}
	}
	return ret
}

func expandCave(size int) {
	oH, oW := cave.Height, cave.Width
	for i := 1; i < size; i++ {
		for y := 0; y < oH; y++ {
			for x := 0; x < oW; x++ {
				ny := (oH*i + y)
				prev := h.Coordinate{
					X: x,
					Y: (oH*(i-1) + y),
				}
				pv := cave.Get(prev)
				var v byte
				if pv == '9' {
					v = '1'
				} else {
					v = pv + 1
				}
				cave.Put(h.Coordinate{X: x, Y: ny}, v)
			}
		}
	}
	for y := 0; y < cave.Height; y++ {
		for i := 1; i < size; i++ {
			for x := 0; x < oW; x++ {
				nx := (oW*i + x)
				prev := h.Coordinate{
					X: (oW*(i-1) + x),
					Y: y,
				}
				pv := cave.Get(prev)
				var v byte
				if pv == '9' {
					v = '1'
				} else {
					v = pv + 1
				}
				cave.Put(h.Coordinate{X: nx, Y: y}, v)
			}
		}
	}
}