advent2022

main.go (4716B)

---

 package main
 
 import (
 	"bufio"
 	"fmt"
 	"log"
 	"math"
 	"os"
 	"strconv"
 )
 
 type Pos interface {
 	GetX() int
 	GetY() int
 }
 
 func Distance(p1 Pos, p2 Pos) int {
 	return int(math.Abs(float64(p1.GetX()-p2.GetX())) + math.Abs(float64(p1.GetY()-p2.GetY())))
 }
 
 type Sensor struct {
 	x, y, r int
 }
 
 func (s Sensor) GetX() int { return s.x }
 func (s Sensor) GetY() int { return s.y }
 
 type Vec2 struct {
 	x, y int
 }
 
 func (v Vec2) GetX() int { return v.x }
 func (v Vec2) GetY() int { return v.y }
 
 func max(a, b int) int {
 	if a > b {
 		return a
 	}
 	return b
 }
 func min(a, b int) int {
 	if a < b {
 		return a
 	}
 	return b
 }
 
 func abs(a int) int {
 	return int(math.Abs(float64(a)))
 }
 
 type Line [2]Vec2
 
 func (l1 Line) Intersection(l2 Line) (Vec2, bool) {
 	var v Vec2
 	x1, x2, x3, x4 := l1[0].x, l1[1].x, l2[0].x, l2[1].x
 	y1, y2, y3, y4 := l1[0].y, l1[1].y, l2[0].y, l2[1].y
 
 	d := (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
 	if d == 0 {
 		return v, false
 	}
 
 	pre := (x1*y2 - y1*x2)
 	post := (x3*y4 - y3*x4)
 	x := (pre*(x3-x4) - (x1-x2)*post) / d
 	y := (pre*(y3-y4) - (y1-y2)*post) / d
 
 	if x < min(x1, x2) || x > max(x1, x2) ||
 		x < min(x3, x4) || x > max(x3, x4) {
 		return v, false
 	}
 	if y < min(y1, y2) || y > max(y1, y2) ||
 		y < min(y3, y4) || y > max(y3, y4) {
 		return v, false
 	}
 
 	v.x = x
 	v.y = y
 
 	return v, true
 }
 
 type Sensors []Sensor
 
 func (ss Sensors) Have(s1 Sensor) bool {
 	for _, s := range ss {
 		if s1.x == s.x && s1.y == s.y {
 			return true
 		}
 	}
 	return false
 }
 
 type Beacons []Vec2
 
 func (bs Beacons) Have(b1 Vec2) bool {
 	for _, b := range bs {
 		if b1.x == b.x && b1.y == b.y {
 			return true
 		}
 	}
 	return false
 }
 
 func main() {
 	if len(os.Args) > 2 {
 		y, err := strconv.Atoi(os.Args[2])
 		if err != nil {
 			log.Fatal(err)
 		}
 		day15(os.Args[1], y)
 	} else if len(os.Args) == 1 {
 		fmt.Printf("usage: %s inputfile.txt ROW_NUM\n", os.Args[0])
 	} else {
 		fmt.Println("No input data")
 	}
 }
 
 func day15(input_file string, target_y int) {
 	fmt.Printf("day 15 input filename: %s\n", input_file)
 	input, err := os.Open(input_file)
 	if err != nil {
 		log.Fatal(err)
 	}
 	defer input.Close()
 	scanner := bufio.NewScanner(input)
 	var sensors Sensors
 	var beacons Beacons
 	for scanner.Scan() {
 		in := scanner.Text()
 		var s Sensor
 		var b Vec2
 		num, err := fmt.Sscanf(in, "Sensor at x=%d, y=%d: closest beacon is at x=%d, y=%d", &s.x, &s.y, &b.x, &b.y)
 		if num != 4 || err != nil {
 			log.Fatal("Parsing error", err)
 		}
 		s.r = Distance(s, b)
 		sensors = append(sensors, s)
 		if !beacons.Have(b) {
 			beacons = append(beacons, b)
 		}
 	}
 	if err = scanner.Err(); err != nil {
 		log.Fatal(err)
 	}
 
 	points := make(map[int]bool)
 	for _, s := range sensors {
 		if Distance(s, Vec2{x: s.x, y: target_y}) <= s.r {
 			for x := s.x - s.r; x <= s.x+s.r; x++ {
 				p := Vec2{x: x, y: target_y}
 				if Distance(s, p) <= s.r {
 					if !beacons.Have(p) {
 						points[x] = true
 					}
 				}
 			}
 		}
 	}
 	fmt.Println("Points covered:", len(points))
 
 	// search all pairs of sensors with areas distanced 1 point away from each other borders
 	var pairs []Sensors
 	for i, s1 := range sensors {
 		for j, s2 := range sensors {
 			if i == j {
 				continue
 			}
 			if Distance(s1, s2) == s1.r+s2.r+2 && s1.x != s2.x && s1.y != s2.y {
 				add := true
 				for _, p := range pairs {
 					if p.Have(s1) && p.Have(s1) {
 						add = false
 						break
 					}
 				}
 				if add {
 					pairs = append(pairs, Sensors{s1, s2})
 				}
 			}
 		}
 	}
 
 	var lines []Line
 	for _, p := range pairs {
 		s1 := p[0]
 		s2 := p[1]
 		var line Line
 		if s1.x > s2.x && s1.y > s2.y { // top-left
 			line[0].x = s1.x - s1.r - 1
 			line[0].y = s1.y
 			line[1].x = s1.x
 			line[1].y = s1.y - s1.r - 1
 		} else if s1.x < s2.x && s1.y > s2.y { // top-right
 			line[0].x = s1.x
 			line[0].y = s1.y - s1.r - 1
 			line[1].x = s1.x + s1.r + 1
 			line[1].y = s1.y
 		} else if s1.x < s2.x && s1.y < s2.y { // bottom-right
 			line[0].x = s1.x
 			line[0].y = s1.y + s1.r + 1
 			line[1].x = s1.x + s1.r + 1
 			line[1].y = s1.y
 		} else if s1.x > s2.x && s1.y < s2.y { // bottom-left
 			line[0].x = s1.x - s1.r - 1
 			line[0].y = s1.y
 			line[1].x = s1.x
 			line[1].y = s1.y + s1.r + 1
 		} else {
 			log.Fatal("invalid line")
 		}
 		lines = append(lines, line)
 	}
 
 	// those are actually points but I don't want to rename Beacons to something else at this point since they did carry me so far
 	var pts Beacons
 	for i, l1 := range lines {
 		for j, l2 := range lines {
 			if i == j {
 				continue
 			}
 			p, found := l1.Intersection(l2)
 			if found && !pts.Have(p) {
 				pts = append(pts, p)
 			}
 		}
 	}
 
 	for _, p := range pts {
 		if p.x >= 0 && p.x <= target_y*2 &&
 			p.y >= 0 && p.y <= target_y*2 {
 			fmt.Println("Point checksum:", p.x*4000000+p.y)
 			break
 		}
 	}
 }