solve

2022 advent day 15

I also spent too long thinking this problem in the wrong way. It's basically just checking values in a row to see if it's observable by a beacon. We mark all values as checked for each observation.

package problems

import (
	"os"
	"strings"

	"github.com/xxxx/advent/internal"
)

type day15 struct {
	lines []string
}

func Day15(part int, file string) int {

	in := day15{
		lines: internal.Read(file),
	}

	switch part {
	case 1:
		return in.part_one()
	case 2:
		return in.part_two()
	default:
		return 0
	}

}

func read_beacon_readings(lines []string) map[coordinate][]coordinate {
	beacon_readings := make(map[coordinate][]coordinate)

	for _, line := range lines {
		split := strings.Split(line, "=")
		sensor_x := internal.StrToInt(strings.Split(split[1], ",")[0])
		sensor_y := internal.StrToInt(strings.Split(split[2], ":")[0])
		beacon_x := internal.StrToInt(strings.Split(split[3], ",")[0])
		beacon_y := internal.StrToInt(split[4])

		beacon_coordinate := coordinate{beacon_x, beacon_y}
		sensor_coordiante := coordinate{sensor_x, sensor_y}

		if _, ok := beacon_readings[beacon_coordinate]; !ok {
			beacon_readings[beacon_coordinate] = []coordinate{}
		}
		beacon_readings[beacon_coordinate] = append(beacon_readings[beacon_coordinate], sensor_coordiante)
	}

	return beacon_readings
}

func get_manhattan_distance(a coordinate, b coordinate) int {
	x_dist := a.x - b.x

	if x_dist < 0 {
		x_dist = x_dist * -1
	}

	y_dist := a.y - b.y

	if y_dist < 0 {
		y_dist = y_dist * -1
	}

	return x_dist + y_dist
}

func populate_x(no_beacons_x map[int]bool, sensor coordinate, beacon coordinate, const_y int) map[int]bool {

	manhattan_distance := get_manhattan_distance(sensor, beacon)

	// sensor.y >= const_y
	y_dist := sensor.y - const_y
	if y_dist >= 0 && y_dist <= manhattan_distance {
		x_dist := manhattan_distance - y_dist
		for i := sensor.x - x_dist; i <= sensor.x+x_dist; i++ {
			no_beacons_x[i] = true
		}
	}

	// sensor.y <= const_y
	y_dist = const_y - sensor.y
	if y_dist >= 0 && y_dist <= manhattan_distance {
		x_dist := manhattan_distance - y_dist
		for i := sensor.x - x_dist; i <= sensor.x+x_dist; i++ {
			no_beacons_x[i] = true
		}
	}

	return no_beacons_x
}

func (input day15) part_one() int {
	beacon_readings := read_beacon_readings((input.lines))
	no_beacons_x := make(map[int]bool)

	const_y := 2000000
	if os.Getenv("ENV") == "test" {
		const_y = 10
	}

	for beacon, sensors := range beacon_readings {
		for _, sensor := range sensors {
			// maps passed as references
			populate_x(no_beacons_x, sensor, beacon, const_y)
		}
	}

	for beacon := range beacon_readings {
		if beacon.y == const_y {
			delete(no_beacons_x, beacon.x)
		}
	}

	return len(no_beacons_x)
}

func get_possible_distress_locations(sensor coordinate, distance int) []coordinate {
	result := []coordinate{}
	d := distance + 1
	for i := 0; i <= d; i++ {

		coordinates := []coordinate{
			{sensor.x - d + i, sensor.y + i},
			{sensor.x - d + i, sensor.y - i},
			{sensor.x + d - i, sensor.y + i},
			{sensor.x + d - i, sensor.y - i},
		}

		for _, c := range coordinates {
			if is_in_bound(c) {
				result = append(result, c)
			}
		}

	}
	return result
}

func is_in_bound(c coordinate) bool {
	if os.Getenv("ENV") == "test" {
		if c.x >= 0 && c.x <= 20 && c.y >= 0 && c.y <= 20 {
			return true
		}
	} else {
		if c.x >= 0 && c.x <= 4000000 && c.y >= 0 && c.y <= 4000000 {
			return true
		}
	}
	return false
}

func is_reachable(sensors map[coordinate]int, target coordinate) bool {
	for sensor, max_distance := range sensors {
		if get_manhattan_distance(sensor, target) <= max_distance {
			return true
		}
	}
	return false
}

func (input day15) part_two() int {
	beacon_readings := read_beacon_readings((input.lines))
	distances := make(map[coordinate]int)

	// check possible locations outside of sensor range

	for beacon, sensors := range beacon_readings {
		for _, sensor := range sensors {
			distance := get_manhattan_distance(sensor, beacon)
			if d, ok := distances[sensor]; ok {
				if d < distance {
					distances[sensor] = distance
				}
			} else {
				distances[sensor] = distance
			}
		}
	}

	for sensor, distance := range distances {
		possible_distress_locations := get_possible_distress_locations(sensor, distance)
		for _, possible_distress_location := range possible_distress_locations {
			if !is_reachable(distances, possible_distress_location) {
				return get_tuning_frequency(possible_distress_location)
			}
		}
	}

	return 0
}

func get_tuning_frequency(c coordinate) int {
	return 4000000*c.x + c.y
}