path: root/day13/main.go

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
}