aoc2023/day24/day24.go

package day24

import (
	"math"
	"strings"

	"gitea.paas.celticinfo.fr/oabrivard/aoc2023/utils"
)

type Hailstone struct {
	px, py, pz, vx, vy, vz int64
}

type Line struct {
	m, b float64
}

func getLine(h Hailstone) Line {
	y2 := h.py + h.vy
	x2 := h.px + h.vx
	m := float64((y2 - h.py)) / float64((x2 - h.px))
	b := float64(y2) - m*float64(x2)
	return Line{m, b}
}

func crossCoord(h1, h2 Hailstone) (bool, float64, float64) {
	l1 := getLine(h1)
	l2 := getLine(h2)

	if l1.m == l2.m {
		return false, -1, -1
	}

	x := (l2.b - l1.b) / (l1.m - l2.m)
	y := l2.m*x + l2.b

	if h1.px > int64(x) && h1.vx >= 0 || h1.px < int64(x) && h1.vx <= 0 {
		return false, -1, -1
	}

	if h2.px > int64(x) && h2.vx >= 0 || h2.px < int64(x) && h2.vx <= 0 {
		return false, -1, -1
	}

	return true, x, y
}

func Part1(lines []string, min, max float64) int {
	stones := []Hailstone{}

	for _, line := range lines {
		values := utils.ParseInt64Array(strings.Replace(line, " @", ",", -1), ", ")
		stone := Hailstone{values[0], values[1], values[2], values[3], values[4], values[5]}
		stones = append(stones, stone)
	}

	result := 0
	for i := range stones {
		for j := i + 1; j < len(stones); j++ {
			areCrossing, x, y := crossCoord(stones[i], stones[j])
			if !areCrossing {
				continue
			}
			if x >= min && y >= min && x <= max && y <= max {
				result++
			}
			//fmt.Println("x : ", x, ", y : ", y)
		}
	}

	return result
}

// Adapted from Java code given here : https://github.com/ash42/adventofcode/blob/main/adventofcode2023/src/nl/michielgraat/adventofcode2023/day24/Day24.java
// Explanations can be found here : https://www.cs.emory.edu/~cheung/Courses/170/Syllabus/09/gaussian-elim.html
func gaussianElimination(coefficients [][]float64, rhs []float64) {
	size := len(coefficients)
	for i := 0; i < size; i++ {
		// Select pivot
		pivot := coefficients[i][i]
		// Normalize row i
		for j := 0; j < size; j++ {
			coefficients[i][j] = coefficients[i][j] / pivot
		}
		rhs[i] = rhs[i] / pivot
		// Sweep using row i
		for k := 0; k < size; k++ {
			if k != i {
				factor := coefficients[k][i]
				for j := 0; j < size; j++ {
					coefficients[k][j] = coefficients[k][j] - factor*coefficients[i][j]
				}
				rhs[k] = rhs[k] - factor*rhs[i]
			}
		}
	}
}

// Adapted from solution given here : https://www.reddit.com/r/adventofcode/comments/18q40he/2023_day_24_part_2_a_straightforward_nonsolver/
// and from Java code given here : https://github.com/ash42/adventofcode/blob/main/adventofcode2023/src/nl/michielgraat/adventofcode2023/day24/Day24.java
func getCoordinates(stones []Hailstone) Hailstone {
	coefficients := [][]float64{{0.0, 0.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0}}
	rhs := []float64{0.0, 0.0, 0.0, 0.0}

	// Get X,Y,VX,VY
	for i := 0; i < 4; i++ {
		s1 := stones[i]
		s2 := stones[i+1]
		coefficients[i][0] = float64(s2.vy - s1.vy)
		coefficients[i][1] = float64(s1.vx - s2.vx)
		coefficients[i][2] = float64(s1.py - s2.py)
		coefficients[i][3] = float64(s2.px - s1.px)
		rhs[i] = float64(-s1.px*s1.vy + s1.py*s1.vx + s2.px*s2.vy - s2.py*s2.vx)
	}

	gaussianElimination(coefficients, rhs)

	var x int64 = int64(math.Round(rhs[0]))
	var y int64 = int64(math.Round(rhs[1]))
	var vx int64 = int64(math.Round(rhs[2]))
	var vy int64 = int64(math.Round(rhs[3]))

	// Get X,VZ
	coefficients = [][]float64{{0.0, 0.0}, {0.0, 0.0}}
	rhs = []float64{0.0, 0.0}
	for i := 0; i < 2; i++ {
		s1 := stones[i]
		s2 := stones[i+1]
		coefficients[i][0] = float64(s1.vx - s2.vx)
		coefficients[i][1] = float64(s2.px - s1.px)
		rhs[i] = float64(-s1.px*s1.vz + s1.pz*s1.vx + s2.px*s2.vz - s2.pz*s2.vx - ((s2.vz - s1.vz) * x) - ((s1.pz - s2.pz) * vx))
	}

	gaussianElimination(coefficients, rhs)

	var z int64 = int64(math.Round(rhs[0]))
	var vz int64 = int64(math.Round(rhs[1]))

	return Hailstone{x, y, z, vx, vy, vz}
}

func Part2(lines []string) int64 {
	stones := []Hailstone{}

	for _, line := range lines {
		values := utils.ParseInt64Array(strings.Replace(line, " @", ",", -1), ", ")
		stone := Hailstone{values[0], values[1], values[2], values[3], values[4], values[5]}
		stones = append(stones, stone)
	}

	stone := getCoordinates(stones)

	return stone.px + stone.py + stone.pz
}