advent2022

commit 768cb5c7831dda700d425cf2cef81dfa88cd7c32
parent 372f49797eca9eabd5d8d1dfa88a2d2de55056e1
Author: bsandro <email@bsandro.tech>
Date:   Thu, 15 Dec 2022 17:36:23 +0000

Day 15 part 2

Diffstat:
M
day15/main.go
 | 
155
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----

1 file changed, 146 insertions(+), 9 deletions(-)
diff --git a/day15/main.go b/day15/main.go
@@ -4,8 +4,8 @@ import (
 	"bufio"
 	"fmt"
 	"log"
-	"os"
 	"math"
+	"os"
 	"strconv"
 )
 
@@ -15,24 +15,85 @@ type Pos interface {
 }
 
 func Distance(p1 Pos, p2 Pos) int {
-	return int(math.Abs(float64(p1.GetX()-p2.GetX()))+math.Abs(float64(p1.GetY()-p2.GetY())))
+	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 {
@@ -44,8 +105,10 @@ func (bs Beacons) Have(b1 Vec2) bool {
 
 func main() {
 	if len(os.Args) > 2 {
-		y, err:=strconv.Atoi(os.Args[2])
-		if err!=nil{log.Fatal(err)}
+		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])
@@ -84,17 +147,91 @@ func day15(input_file string, target_y int) {
 
 	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, 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
+						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)
 			}
 		}
 	}
 
-	fmt.Println("points:", len(points))
+	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
+		}
+	}
 }