2021-advent-09.go

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"sort"
	"strconv"
	"strings"
)

type Cave = [][]int

func adjacent(cave Cave, p point) []point {
	adjacents := make([]point, 0, 4)
	len_y := len(cave)
	len_x := len(cave[p.y])
	if 0 <= p.y-1 {
		adjacents = append(adjacents, point{p.x, p.y - 1})
	}
	if p.y+1 < len_y {
		adjacents = append(adjacents, point{p.x, p.y + 1})
	}
	if 0 <= p.x-1 {
		adjacents = append(adjacents, point{p.x - 1, p.y})
	}
	if p.x+1 < len_x {
		adjacents = append(adjacents, point{p.x + 1, p.y})
	}
	return adjacents
}

func readInput(input string) Cave {
	bytes, err := ioutil.ReadFile(input)
	if err != nil {
		log.Fatal(err)
	}
	lines := strings.Split(string(bytes), "\n")
	cave := make(Cave, 0)
	for _, line := range lines {
		row := make([]int, 0, 16)
		for _, rune := range line {
			height, err := strconv.Atoi(string(rune))
			if err != nil {
				log.Fatal(err)
			}
			row = append(row, height)
		}
		cave = append(cave, row)
	}
	return cave
}

type point struct {
	x, y int
}

func findLowpoints(cave Cave) []point {
	lowpoints := make([]point, 0)
	for y, yend := 0, len(cave)-1; y <= yend; y++ {
		for x, xend := 0, len(cave[y])-1; x <= xend; x++ {
			curr := cave[y][x]

			//look up
			if y != 0 && cave[y-1][x] <= curr {
				continue
			}
			//look down
			if y != yend && cave[y+1][x] <= curr {
				continue
			}
			//look left
			if x != 0 && cave[y][x-1] <= curr {
				continue
			}
			//look right
			if x != xend && cave[y][x+1] <= curr {
				continue
			}
			// fmt.Printf("Low point x:%d, y:%d - %d\n", x, y, curr)
			lowpoints = append(lowpoints, point{x, y})

		}
		// fmt.Println()
	}
	return lowpoints
}

func alreadyVisited(p point, points []point) bool {
	for _, v := range points {
		if p == v {
			return true
		}
	}
	return false
}

func Task1(input string) {
	cave := readInput(input)
	lowpoint := findLowpoints(cave)
	totalRisk := 0
	for _, v := range lowpoint {
		totalRisk += 1 + cave[v.y][v.x]
	}
	fmt.Printf("Day9 task1 file: %s: %d\n", input, totalRisk)
}

func Task2(input string) {
	cave := readInput(input)
	lowpoints := findLowpoints(cave)
	basin_sizes := make([]int, 0)
	for _, lp := range lowpoints {
		// fmt.Printf("Finding basin for lp %v=%v\n", lp, cave[lp.y][lp.x])
		visited := make([]point, 0)
		to_visit := make([]point, 0)
		basin := make([]point, 0)

		to_visit = append(to_visit, lp)
		basin = append(basin, lp)

		for len(to_visit) > 0 {
			//pop
			visiting := to_visit[0]
			to_visit = to_visit[1:]
			for _, adj := range adjacent(cave, visiting) {
				height := cave[adj.y][adj.x]
				if height == 9 {
					continue
				}

				if alreadyVisited(adj, visited) {
					continue
				}

				if !alreadyVisited(adj, basin) {
					basin = append(basin, adj)
				}
				visited = append(visited, visiting)
				to_visit = append(to_visit, adj)
			}
		}
		// fmt.Println(len(basin))
		basin_sizes = append(basin_sizes, len(basin))
	}
	sort.Slice(basin_sizes, func(i, j int) bool { return basin_sizes[i] > basin_sizes[j] })
	fmt.Printf("Top3: %v\n", basin_sizes[:3])
	fmt.Printf("Day9 task2 %s: %d\n", input, basin_sizes[0]*basin_sizes[1]*basin_sizes[3])
}

func main() {
	// contain
	// Task1("example.txt")
	// Task1("input.txt")
	Task2_Alt("example.txt")
	// Task2("example.txt")
	// Task2("input.txt")

	// cave := readInput("example.txt")
	// fmt.Println(adjacent(cave, 8, 3))

	// fmt.Printf("%v", alreadyVisited(point{0, 0}, []point{{0, 1}, {0, 0}}))
}