1 files changed, 241 insertions, 0 deletions
diff --git a/day13/main.go b/day13/main.go
new file mode 100644
index 0000000..c4261c3
--- /dev/null
+++ b/day13/main.go
@@ -0,0 +1,241 @@
+package main
+
+import (
+	"bufio"
+	"container/heap"
+	"fmt"
+	"math"
+	"os"
+	"strconv"
+	"strings"
+)
+
+func main() {
+	// fmt.Println(part1(readData("example.txt", 0)), 480)
+	// fmt.Println(part1(readData("data.txt", 0)))
+	fmt.Println(part2(readData("example.txt", 0)), 480)
+	fmt.Println(part2(readData("data.txt", 0)), 31623)
+	fmt.Println(part2(readData("example.txt", 10000000000000)))
+	fmt.Println(part2(readData("data.txt", 10000000000000)))
+}
+
+type Machine struct {
+	PrizeX, PrizeY int64
+	DxA, DyA       int64
+	DxB, DyB       int64
+}
+
+type Position struct {
+	X, Y int64
+}
+
+type Candidate struct {
+	Pos          Position
+	EstimateCost int64
+}
+
+type CandidateItem struct {
+	Cnd   *Candidate
+	Index int
+}
+
+type CandidateQueue struct {
+	elements []*CandidateItem
+	index    map[Position]*CandidateItem
+}
+
+func MakeCandidateQueue() *CandidateQueue {
+	queue := new(CandidateQueue)
+	queue.index = make(map[Position]*CandidateItem)
+	return queue
+}
+
+func (queue *CandidateQueue) Len() int {
+	return len(queue.elements)
+}
+
+func (queue *CandidateQueue) Less(i, j int) bool {
+	return queue.elements[i].Cnd.EstimateCost < queue.elements[i].Cnd.EstimateCost
+}
+
+func (queue *CandidateQueue) Swap(i, j int) {
+	queue.elements[i], queue.elements[j] = queue.elements[j], queue.elements[i]
+	queue.elements[i].Index = i
+	queue.elements[j].Index = j
+}
+
+func (queue *CandidateQueue) Push(x any) {
+	candidate := x.(Candidate)
+	item := &CandidateItem{&candidate, len(queue.elements)}
+	queue.elements = append(queue.elements, item)
+	queue.index[candidate.Pos] = item
+}
+
+func (queue *CandidateQueue) AddElement(candidate Candidate) {
+	item, alreadyIn := queue.index[candidate.Pos]
+	if alreadyIn {
+		item.Cnd = &candidate
+		heap.Fix(queue, item.Index)
+	} else {
+		heap.Push(queue, candidate)
+	}
+}
+
+func (queue *CandidateQueue) Pop() any {
+	if len(queue.elements) == 0 {
+		return nil
+	} else {
+		elmt := queue.elements[len(queue.elements)-1]
+		queue.elements = queue.elements[:len(queue.elements)-1]
+		delete(queue.index, elmt.Cnd.Pos)
+		return elmt.Cnd
+	}
+}
+
+func part1(machines []Machine) (totalPrice int64) {
+	for _, m := range machines {
+		sol := part1Machine(m)
+		if sol >= 0 {
+			totalPrice += sol
+		}
+	}
+	return
+}
+
+func part1Machine(machine Machine) (price int64) {
+	fmt.Println(machine)
+
+	maxStepX := max(machine.DxA, machine.DxB)
+	maxStepY := max(machine.DyA, machine.DyB)
+
+	estimateCost := func(x, y int64) int64 {
+		distX := machine.PrizeX - x
+		distY := machine.PrizeY - y
+		return int64(math.Floor(min(float64(distX)/float64(maxStepX), float64(distY)/float64(maxStepY))))
+	}
+
+	realCost := make([][]int64, machine.PrizeY+1)
+	for y := range machine.PrizeY + 1 {
+		realCost[y] = make([]int64, machine.PrizeX+1)
+		for x := range machine.PrizeX + 1 {
+			realCost[y][x] = math.MaxInt
+		}
+	}
+
+	realCost[0][0] = 0
+
+	queue := MakeCandidateQueue()
+	queue.AddElement(Candidate{Position{0, 0}, estimateCost(0, 0)})
+
+	for queue.Len() > 0 {
+		candidate := heap.Pop(queue).(*Candidate)
+
+		xa := candidate.Pos.X + machine.DxA
+		ya := candidate.Pos.Y + machine.DyA
+		realCostA := realCost[candidate.Pos.Y][candidate.Pos.X] + 3
+		if xa == machine.PrizeX && ya == machine.PrizeY {
+			return realCostA
+		} else if xa <= machine.PrizeX && ya <= machine.PrizeY && realCostA < realCost[ya][xa] {
+			realCost[ya][xa] = realCostA
+			queue.AddElement(Candidate{Position{xa, ya}, realCostA + estimateCost(xa, ya)})
+		}
+
+		xb := candidate.Pos.X + machine.DxB
+		yb := candidate.Pos.Y + machine.DyB
+		realCostB := realCost[candidate.Pos.Y][candidate.Pos.X] + 1
+		if xb == machine.PrizeX && yb == machine.PrizeY {
+			return realCostB
+		} else if xb <= machine.PrizeX && yb <= machine.PrizeY && realCostB < realCost[yb][xb] {
+			realCost[yb][xb] = realCostB
+			queue.AddElement(Candidate{Position{xb, yb}, realCostB + estimateCost(xb, yb)})
+		}
+	}
+
+	return -1
+}
+
+func part2(machines []Machine) (totalPrice int64) {
+	for _, m := range machines {
+		sol := part2Machine(m)
+		if sol >= 0 {
+			totalPrice += sol
+		}
+	}
+	return
+}
+
+func part2Machine(machine Machine) (price int64) {
+	// This is fucking dumb.
+	// The general problem uses annoying math with diophantine stuff and shit.
+	// But they constructed the dataset so that we can do the dumb thing of
+	// solving the equations like dumb fucks and it so happens that the real solutions
+	// minimize the cost metric. So fucking useless and stupid.
+
+	// ax a + bx b = tx
+	// ay a + by b = ty
+	//
+	// (ax bx) * (a) = (tx)
+	// (ay by)   (b)   (ty)
+	//
+	// (a) = ( by -bx) * (tx)
+	// (b)   (-ay  ax)   (ty) / (ax by - ay bx)
+
+	det := machine.DxA*machine.DyB - machine.DyA*machine.DxB
+	if det == 0 {
+		return -1
+	}
+
+	a := int64(float64(machine.DyB*machine.PrizeX-machine.DxB*machine.PrizeY) / float64(det))
+	b := int64(float64(machine.DxA*machine.PrizeY-machine.DyA*machine.PrizeX) / float64(det))
+
+	if machine.DxA*a+machine.DxB*b == machine.PrizeX && machine.DyA*a+machine.DyB*b == machine.PrizeY {
+		return a*3 + b
+	} else {
+		return -1
+	}
+}
+
+func trimAll(strs []string) {
+	for i, s := range strs {
+		strs[i] = strings.TrimSpace(s)
+	}
+}
+
+func parseCoordinateValue(s string) (value int) {
+	value, _ = strconv.Atoi(s[2:])
+	return
+}
+
+func parsePair(s string) (x, y int64) {
+	parts := strings.Split(strings.Split(s, ":")[1], ",")
+	trimAll(parts)
+
+	x = int64(parseCoordinateValue(parts[0]))
+	y = int64(parseCoordinateValue(parts[1]))
+
+	return
+}
+
+func readData(fileName string, offset int64) (machines []Machine) {
+	fp, _ := os.Open(fileName)
+	scanner := bufio.NewScanner(fp)
+
+	var machine Machine
+
+	for line := 0; scanner.Scan(); line++ {
+		switch line % 4 {
+		case 0:
+			machine = Machine{}
+			machine.DxA, machine.DyA = parsePair(scanner.Text())
+		case 1:
+			machine.DxB, machine.DyB = parsePair(scanner.Text())
+		case 2:
+			machine.PrizeX, machine.PrizeY = parsePair(scanner.Text())
+			machine.PrizeX += offset
+			machine.PrizeY += offset
+			machines = append(machines, machine)
+		}
+	}
+
+	return
+}