1 files changed, 204 insertions, 0 deletions
diff --git a/day18/main.go b/day18/main.go
new file mode 100644
index 0000000..073a0bf
--- /dev/null
+++ b/day18/main.go
@@ -0,0 +1,204 @@
+package main
+
+import (
+	"bufio"
+	"container/heap"
+	"fmt"
+	"math"
+	"os"
+	"strconv"
+	"strings"
+)
+
+func main() {
+	positions := readData("example.txt")
+	maze := makeMaze(positions[:12], 7)
+	fmt.Println(part1(maze), 22)
+
+	positions2 := readData("data.txt")
+	maze2 := makeMaze(positions2[:1024], 71)
+	fmt.Println(part1(maze2), 284)
+
+	fmt.Println(6, 1)
+	fmt.Println(part2(positions, 7, 11))
+
+	fmt.Println(part2(positions2, 71, 1023))
+}
+
+type Position struct {
+	x, y int
+}
+
+type Candidate struct {
+	pos          Position
+	estimateCost int
+}
+
+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[j].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 makeMaze(walls []Position, size int) (maze [][]byte) {
+	maze = make([][]byte, size+2)
+	for y := range maze {
+		maze[y] = make([]byte, size+2)
+		maze[y][0] = '#'
+		maze[y][size+1] = '#'
+	}
+	for x := range size + 2 {
+		maze[0][x] = '#'
+		maze[size+1][x] = '#'
+	}
+	for _, p := range walls {
+		maze[p.y+1][p.x+1] = '#'
+	}
+	return
+}
+
+func IntAbs(x int) int {
+	if x < 0 {
+		return -x
+	} else {
+		return x
+	}
+}
+
+func part1(maze [][]byte) (steps int) {
+	startX, startY := 1, 1
+	endX, endY := len(maze)-2, len(maze)-2
+
+	estimateCost := func(x, y int) int {
+		return IntAbs(x-endX) + IntAbs(y-endY)
+	}
+
+	realCost := make([][]int, len(maze))
+	for y := range realCost {
+		realCost[y] = make([]int, len(maze))
+		for x := range realCost[y] {
+			realCost[y][x] = math.MaxInt
+		}
+	}
+
+	realCost[startY][startX] = 0
+
+	queue := MakeCandidateQueue()
+	queue.AddElement(Candidate{Position{1, 1}, estimateCost(1, 1)})
+
+	for queue.Len() > 0 {
+		candidate := heap.Pop(queue).(*Candidate)
+
+		tryDirection := func(dx, dy int) int {
+			xNext := candidate.pos.x + dx
+			yNext := candidate.pos.y + dy
+			realCostNext := realCost[candidate.pos.y][candidate.pos.x] + 1
+			if xNext == endX && yNext == endY {
+				return realCostNext
+			} else if maze[yNext][xNext] != '#' && realCostNext < realCost[yNext][xNext] {
+				realCost[yNext][xNext] = realCostNext
+				queue.AddElement(Candidate{Position{xNext, yNext}, realCostNext + estimateCost(xNext, yNext)})
+			}
+			return -1
+		}
+
+		if cost := tryDirection(1, 0); cost >= 0 {
+			return cost
+		}
+
+		if cost := tryDirection(-1, 0); cost >= 0 {
+			return cost
+		}
+
+		if cost := tryDirection(0, 1); cost >= 0 {
+			return cost
+		}
+
+		if cost := tryDirection(0, -1); cost >= 0 {
+			return cost
+		}
+	}
+
+	return -1
+}
+
+func part2(walls []Position, size int, okAt int) (blockX, blockY int) {
+	koAt := len(walls)
+	for koAt-okAt > 1 {
+		pivot := (okAt + koAt) / 2
+		maze := makeMaze(walls[:pivot+1], size)
+		result := part1(maze)
+		if result < 0 {
+			koAt = pivot
+		} else {
+			okAt = pivot
+		}
+	}
+	return walls[koAt].x, walls[koAt].y
+}
+
+func readData(fileName string) (positions []Position) {
+	fp, _ := os.Open(fileName)
+	scanner := bufio.NewScanner(fp)
+
+	for scanner.Scan() {
+		line := strings.Split(strings.TrimSpace(scanner.Text()), ",")
+		x, _ := strconv.Atoi(line[0])
+		y, _ := strconv.Atoi(line[1])
+		positions = append(positions, Position{x, y})
+	}
+
+	return
+}