Day 20 completed

The key feature for part 2 is changing up what the Dijkstra solver views as an "adjacent" node, injecting the appropriate depth as we traverse inner/outer portals. The main thing that tripped me up here from part 1 was that I needed to be carrying more data along with portals than just their locations, and I could no longer get away with storing the portals as pairs of their inner/outer locations, so a small refactor was needed. Once I made those corrections, it was mostly a matter of ironing out the "get neighbors" function to adhere to part 2's rules, which took me a lot of debugging to get just right.

days/18.go

@@ -6,7 +6,6 @@ import (
 	"math"
 	"strings"
 
-	"github.com/edwingeng/deque/v2"
 	u "parnic.com/aoc2019/utilities"
 )
 
@@ -120,14 +119,15 @@ func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, g
 		return retAdjacent
 	}
 
-	queue := deque.NewDeque[u.Pair[int, day18Vec]]()
+	queue := make([]u.Pair[int, day18Vec], 0)
 	visited := make(map[day18Vec]bool)
 	for _, adjacent := range getAdjacent(inPos) {
-		queue.PushBack(u.Pair[int, day18Vec]{First: 1, Second: adjacent})
+		queue = append(queue, u.Pair[int, day18Vec]{First: 1, Second: adjacent})
 	}
 
-	for !queue.IsEmpty() {
+	for len(queue) > 0 {
-		next := queue.PopFront()
+		next := queue[0]
+		queue = queue[1:]
 
 		if _, exists := visited[next.Second]; !exists {
 			visited[next.Second] = true
@@ -157,7 +157,7 @@ func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, g
 
 			for _, neighbor := range getAdjacent(next.Second) {
 				if _, exists := visited[neighbor]; !exists {
-					queue.PushBack(u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
+					queue = append(queue, u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
 				}
 			}
 		}

days/19.go

@@ -77,6 +77,7 @@ func (d *Day19) Part2() string {
 	}
 
 	// find lower bound
+	// this may not be necessary, but helps seed the bisect with a known-good lower bound
 	startY := 0
 	startX := 0
 	for y := 1; startY == 0; y++ {
@@ -91,9 +92,12 @@ func (d *Day19) Part2() string {
 
 	lastGoodX := 0
 	threshold := 1
+	// add 100 to start y since we know it has to be a 100x100 square.
+	// since we multiply x by 10,000 for the final result, that tells us y cannot be 10k+
 	y := u.Bisect(startY+100, 9999, threshold, func(y int) bool {
 		foundX := false
 		for x := startX; ; x++ {
+			// check top left
 			if !f(x, y) {
 				if !foundX {
 					continue
@@ -105,18 +109,38 @@ func (d *Day19) Part2() string {
 				foundX = true
 			}
 
+			// check top right
 			if !f(x+99, y) {
 				return true
 			}
+			// check bottom left
 			if !f(x, y+99) {
 				continue
 			}
 
+			// we believe the corners work, so run final validations on the full borders.
+			// this may not be necessary, but i've seen some rows end up shorter than a
+			// previous row because of the angle of the beam and our integer fidelity.
+			// plus it's really not that much more expensive to do to be certain we're correct.
+			for y2 := y; y2 < y+100; y2++ {
+				// right wall
+				if !f(x+99, y2) {
+					return true
+				}
+				// left wall
+				if !f(x, y2) {
+					return true
+				}
+			}
+
 			lastGoodX = x
 			return false
 		}
 	})
 
+	// since we invert our bisect success returns, we need to increment y to
+	// tip back over into the "success" range
+	y += threshold
 	result := (lastGoodX * 10000) + y
 	return fmt.Sprintf("Closest 100x100 square for the ship starts at %d,%d = %s%d%s", lastGoodX, y, u.TextBold, result, u.TextReset)
 }

days/20.go

@@ -0,0 +1,398 @@
+package days
+
+import (
+	"container/heap"
+	"fmt"
+	"math"
+	"strings"
+
+	u "parnic.com/aoc2019/utilities"
+)
+
+type day20Cell int8
+type day20Graph map[day20Portal][]u.Pair[day20Portal, int]
+
+const (
+	day20CellWall day20Cell = iota
+	day20CellPath
+	day20CellDonutHole
+)
+
+var (
+	day20AdjacentOffsets = []u.Vec2i{
+		{X: -1, Y: 0},
+		{X: 1, Y: 0},
+		{X: 0, Y: -1},
+		{X: 0, Y: 1},
+	}
+
+	entrancePortal = day20Portal{name: "AA"}
+	exitPortal     = day20Portal{name: "ZZ"}
+)
+
+type day20Portal struct {
+	name  string
+	inner bool
+	depth int
+}
+
+type Day20 struct {
+	grid        [][]day20Cell
+	entrance    u.Vec2i
+	exit        u.Vec2i
+	portals     map[day20Portal]u.Vec2i
+	portalNames []string
+}
+
+func (d *Day20) Parse() {
+	d.portals = make(map[day20Portal]u.Vec2i)
+	d.portalNames = make([]string, 0)
+
+	lines := u.GetStringLines("20p")
+	d.grid = make([][]day20Cell, len(lines)-4)
+	currPortal := strings.Builder{}
+
+	for row, line := range lines {
+		y := row - 2
+		isGridRow := row >= 2 && row < len(lines)-2
+
+		if isGridRow {
+			d.grid[y] = make([]day20Cell, len(line)-4)
+		}
+
+		for col, ch := range lines[row] {
+			x := col - 2
+			isGridCol := col >= 2 && col < len(line)-2
+
+			if isGridRow && isGridCol {
+				if ch == '#' {
+					d.grid[y][x] = day20CellWall
+				} else if ch == '.' {
+					d.grid[y][x] = day20CellPath
+				} else {
+					d.grid[y][x] = day20CellDonutHole
+				}
+			}
+
+			if ch >= 'A' && ch <= 'Z' {
+				portalX := 0
+				portalY := 0
+				if len(line) > col+1 && line[col+1] >= 'A' && line[col+1] <= 'Z' {
+					currPortal.WriteRune(ch)
+					currPortal.WriteRune(rune(line[col+1]))
+
+					if len(line) > col+2 && line[col+2] == '.' {
+						portalY = y
+						portalX = x + 2
+					} else if col-1 >= 0 && line[col-1] == '.' {
+						portalY = y
+						portalX = x - 1
+					} else {
+						panic("!")
+					}
+				} else if len(lines) > row+1 && lines[row+1][col] >= 'A' && lines[row+1][col] <= 'Z' {
+					currPortal.WriteRune(ch)
+					currPortal.WriteRune(rune(lines[row+1][col]))
+
+					if len(lines) > row+2 && lines[row+2][col] == '.' {
+						portalY = y + 2
+						portalX = x
+					} else if row-1 >= 0 && lines[row-1][col] == '.' {
+						portalY = y - 1
+						portalX = x
+					} else {
+						panic("!")
+					}
+				}
+
+				if currPortal.Len() == 2 {
+					portalName := currPortal.String()
+					portalVec := u.Vec2i{X: portalX, Y: portalY}
+
+					if portalName == entrancePortal.name {
+						d.entrance = portalVec
+					} else if portalName == exitPortal.name {
+						d.exit = portalVec
+					} else {
+						portal := day20Portal{
+							name:  portalName,
+							inner: !d.isOuterPortal(portalVec),
+						}
+						d.portals[portal] = portalVec
+
+						u.AddToArray(&d.portalNames, portalName)
+					}
+
+					currPortal.Reset()
+				}
+			}
+		}
+	}
+}
+
+func (d Day20) Num() int {
+	return 20
+}
+
+func (d Day20) isPortal(vec u.Vec2i) (bool, int) {
+	if d.grid[vec.Y][vec.X] != day20CellPath {
+		return false, 0
+	}
+
+	for i, name := range d.portalNames {
+		p, exists := d.portals[day20Portal{name: name, inner: !d.isOuterPortal(vec)}]
+		if exists && vec == p {
+			return true, i
+		}
+	}
+
+	return false, 0
+}
+
+func (d Day20) Draw() {
+	for y := range d.grid {
+		for x := range d.grid[y] {
+			switch d.grid[y][x] {
+			case day20CellWall:
+				fmt.Print("█")
+			case day20CellDonutHole:
+				fmt.Print(" ")
+			case day20CellPath:
+				posVec := u.Vec2i{X: x, Y: y}
+				if posVec == d.entrance {
+					fmt.Print("@")
+				} else if posVec == d.exit {
+					fmt.Print("!")
+				} else {
+					isPortal, portalIdx := d.isPortal(posVec)
+					if isPortal {
+						ch := 'a' + portalIdx
+						if ch > 'z' {
+							ch = 'A' + (portalIdx - 26)
+						}
+						fmt.Printf("%c", ch)
+					} else {
+						fmt.Print(" ")
+					}
+				}
+			}
+		}
+
+		fmt.Println()
+	}
+}
+
+func (d Day20) isOuterPortal(pos u.Vec2i) bool {
+	return pos.X == 0 || pos.Y == 0 || pos.X == len(d.grid[0])-1 || pos.Y == len(d.grid)-1
+}
+
+func (d Day20) findAdjacentCells(inPos u.Vec2i) []u.Pair[day20Portal, int] {
+	found := make([]u.Pair[day20Portal, int], 0)
+
+	getAdjacent := func(pos u.Vec2i) []u.Vec2i {
+		retAdjacent := make([]u.Vec2i, 0, len(day20AdjacentOffsets))
+		for _, off := range day20AdjacentOffsets {
+			offVec := u.Vec2i{X: pos.X + off.X, Y: pos.Y + off.Y}
+			if offVec.Y < 0 || offVec.Y >= len(d.grid) || offVec.X < 0 || offVec.X >= len(d.grid[0]) {
+				continue
+			}
+			if d.grid[offVec.Y][offVec.X] != day20CellPath {
+				continue
+			}
+			retAdjacent = append(retAdjacent, offVec)
+		}
+
+		return retAdjacent
+	}
+
+	queue := make([]u.Pair[int, u.Vec2i], 0)
+	visited := map[u.Vec2i]bool{
+		inPos: true,
+	}
+	for _, adjacent := range getAdjacent(inPos) {
+		queue = append(queue, u.Pair[int, u.Vec2i]{First: 1, Second: adjacent})
+	}
+
+	for len(queue) > 0 {
+		next := queue[0]
+		queue = queue[1:]
+
+		if _, exists := visited[next.Second]; !exists {
+			visited[next.Second] = true
+
+			adjacentIsPortal, portalIdx := d.isPortal(next.Second)
+			if adjacentIsPortal || next.Second == d.entrance || next.Second == d.exit {
+				var portalName string
+				if next.Second == d.entrance {
+					portalName = entrancePortal.name
+				} else if next.Second == d.exit {
+					portalName = exitPortal.name
+				} else {
+					portalName = d.portalNames[portalIdx]
+				}
+
+				alreadyFound := false
+				for _, p := range found {
+					if p.First.name == portalName {
+						alreadyFound = true
+						break
+					}
+				}
+				if !alreadyFound {
+					found = append(found, u.Pair[day20Portal, int]{First: day20Portal{
+						name:  portalName,
+						inner: !d.isOuterPortal(next.Second),
+					}, Second: next.First})
+					continue
+				}
+			}
+
+			for _, neighbor := range getAdjacent(next.Second) {
+				if _, exists := visited[neighbor]; !exists {
+					queue = append(queue, u.Pair[int, u.Vec2i]{First: next.First + 1, Second: neighbor})
+				}
+			}
+		}
+	}
+
+	return found
+}
+
+type day20PriorityQueue struct {
+	distance int
+	neighbor day20Portal
+}
+type day20PriorityQueueHeap []day20PriorityQueue
+
+func (h day20PriorityQueueHeap) Len() int           { return len(h) }
+func (h day20PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
+func (h day20PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
+
+func (h *day20PriorityQueueHeap) Push(x any) {
+	*h = append(*h, x.(day20PriorityQueue))
+}
+
+func (h *day20PriorityQueueHeap) Pop() any {
+	old := *h
+	n := len(old)
+	x := old[n-1]
+	*h = old[0 : n-1]
+	return x
+}
+
+func (d Day20) dijkstra(graph day20Graph, start, end day20Portal, neighborFunc func(inPortal day20Portal) []u.Pair[day20Portal, int]) int {
+	distance := make(map[day20Portal]int)
+
+	ih := day20PriorityQueueHeap{
+		day20PriorityQueue{
+			distance: 0,
+			neighbor: start,
+		},
+	}
+
+	heap.Init(&ih)
+	visited := make(map[day20Portal]bool)
+
+	for ih.Len() > 0 {
+		node := heap.Pop(&ih).(day20PriorityQueue)
+
+		if node.neighbor == end {
+			return node.distance
+		}
+
+		if _, exists := visited[node.neighbor]; exists {
+			continue
+		}
+
+		visited[node.neighbor] = true
+
+		for _, p := range neighborFunc(node.neighbor) {
+			if _, exists := visited[p.First]; exists {
+				continue
+			}
+
+			newDistance := node.distance + p.Second
+			if dist, exists := distance[p.First]; !exists || newDistance < dist {
+				distance[p.First] = newDistance
+				heap.Push(&ih, day20PriorityQueue{
+					distance: newDistance,
+					neighbor: p.First,
+				})
+			}
+		}
+	}
+
+	return math.MaxInt
+}
+
+func (d Day20) buildGraph() day20Graph {
+	graph := make(day20Graph, len(d.portals)+1)
+
+	adjacent := d.findAdjacentCells(d.entrance)
+	graph[entrancePortal] = adjacent
+
+	for portal, portalVec := range d.portals {
+		adjacent = d.findAdjacentCells(portalVec)
+		graph[portal] = adjacent
+	}
+
+	return graph
+}
+
+func (d Day20) getDepthNeighbors(graph day20Graph, portal day20Portal) []u.Pair[day20Portal, int] {
+	basePortal := portal
+	basePortal.depth = 0
+	baseNeighbors := graph[basePortal]
+
+	neighbors := make([]u.Pair[day20Portal, int], 0)
+
+	if portal.inner {
+		n := day20Portal{name: portal.name, inner: false, depth: portal.depth + 1}
+		neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: 1})
+	}
+
+	if portal.depth == 0 {
+		for _, i := range baseNeighbors {
+			if i.First.inner || i.First.name == entrancePortal.name || i.First.name == exitPortal.name {
+				neighbors = append(neighbors, u.Pair[day20Portal, int]{First: i.First, Second: i.Second})
+			}
+		}
+	} else {
+		if !portal.inner {
+			n := day20Portal{name: portal.name, inner: true, depth: portal.depth - 1}
+			neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: 1})
+		}
+
+		for _, i := range baseNeighbors {
+			if i.First.name != entrancePortal.name && i.First.name != exitPortal.name {
+				n := day20Portal{name: i.First.name, inner: i.First.inner, depth: portal.depth}
+				neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: i.Second})
+			}
+		}
+	}
+
+	return neighbors
+}
+
+func (d *Day20) Part1() string {
+	// d.Draw()
+
+	graph := d.buildGraph()
+
+	for portal, adjacent := range graph {
+		if portal.name == entrancePortal.name {
+			continue
+		}
+
+		graph[portal] = append(adjacent, u.Pair[day20Portal, int]{First: day20Portal{name: portal.name, inner: !portal.inner}, Second: 1})
+	}
+
+	distance := d.dijkstra(graph, entrancePortal, exitPortal, func(inPortal day20Portal) []u.Pair[day20Portal, int] { return graph[inPortal] })
+	return fmt.Sprintf("Steps to traverse maze: %s%d%s", u.TextBold, distance, u.TextReset)
+}
+
+func (d *Day20) Part2() string {
+	graph := d.buildGraph()
+	distance := d.dijkstra(graph, entrancePortal, exitPortal, func(inPortal day20Portal) []u.Pair[day20Portal, int] { return d.getDepthNeighbors(graph, inPortal) })
+	return fmt.Sprintf("Steps to traverse recursive maze: %s%d%s", u.TextBold, distance, u.TextReset)
+}

go.mod

@@ -1,5 +1,3 @@
 module parnic.com/aoc2019
 
 go 1.18
-
-require github.com/edwingeng/deque/v2 v2.0.1

go.sum

@@ -1,2 +0,0 @@
-github.com/edwingeng/deque/v2 v2.0.1 h1:yNEsA9tUImO0vyw2hmVGiK4nnkoxBQ8stMYpdVq2ZmQ=
-github.com/edwingeng/deque/v2 v2.0.1/go.mod h1:HukI8CQe9KDmZCcURPZRYVYjH79Zy2tIjTF9sN3Bgb0=

inputs/19p.txt

@@ -1 +1 @@
-109,424,203,1,21102,11,1,0,1105,1,282,21102,18,1,0,1105,1,259,1201,1,0,221,203,1,21101,31,0,0,1105,1,282,21101,38,0,0,1106,0,259,21002,23,1,2,22101,0,1,3,21102,1,1,1,21101,0,57,0,1105,1,303,1201,1,0,222,20102,1,221,3,21001,221,0,2,21101,259,0,1,21101,0,80,0,1105,1,225,21102,1,76,2,21101,91,0,0,1106,0,303,1201,1,0,223,21001,222,0,4,21102,1,259,3,21101,0,225,2,21102,1,225,1,21102,1,118,0,1106,0,225,20101,0,222,3,21101,100,0,2,21102,1,133,0,1105,1,303,21202,1,-1,1,22001,223,1,1,21101,148,0,0,1105,1,259,2102,1,1,223,20102,1,221,4,21001,222,0,3,21101,0,17,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,0,195,0,106,0,109,20207,1,223,2,21002,23,1,1,21102,1,-1,3,21101,214,0,0,1105,1,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,1201,-4,0,249,22101,0,-3,1,21201,-2,0,2,22102,1,-1,3,21101,0,250,0,1106,0,225,22101,0,1,-4,109,-5,2105,1,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2105,1,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,22101,0,-2,-2,109,-3,2105,1,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,22101,0,-2,3,21102,1,343,0,1105,1,303,1106,0,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,21201,-4,0,1,21102,1,384,0,1106,0,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21201,1,0,-4,109,-5,2106,0,0
+109,424,203,1,21102,11,1,0,1105,1,282,21101,0,18,0,1105,1,259,2101,0,1,221,203,1,21102,1,31,0,1105,1,282,21102,1,38,0,1105,1,259,20102,1,23,2,21201,1,0,3,21102,1,1,1,21102,57,1,0,1106,0,303,2102,1,1,222,21002,221,1,3,20101,0,221,2,21101,0,259,1,21101,0,80,0,1105,1,225,21101,44,0,2,21102,91,1,0,1105,1,303,1202,1,1,223,21002,222,1,4,21102,259,1,3,21102,1,225,2,21102,225,1,1,21101,118,0,0,1106,0,225,21002,222,1,3,21101,163,0,2,21101,0,133,0,1106,0,303,21202,1,-1,1,22001,223,1,1,21102,148,1,0,1106,0,259,1202,1,1,223,20101,0,221,4,21001,222,0,3,21102,1,24,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,195,0,0,105,1,108,20207,1,223,2,21002,23,1,1,21102,-1,1,3,21102,1,214,0,1106,0,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,2101,0,-4,249,22102,1,-3,1,22101,0,-2,2,22101,0,-1,3,21102,250,1,0,1106,0,225,21202,1,1,-4,109,-5,2105,1,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2106,0,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,22102,1,-2,-2,109,-3,2105,1,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,21202,-2,1,3,21101,0,343,0,1106,0,303,1106,0,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,21201,-4,0,1,21101,384,0,0,1105,1,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21202,1,1,-4,109,-5,2105,1,0

inputs/20p.txt

@@ -0,0 +1,125 @@
+                                         J       L   P           P   V T       X                                           
+                                         G       V   M           I   O R       C                                           
+  #######################################.#######.###.###########.###.#.#######.#########################################  
+  #...#.........#.#...#.#...#.........#.....#.#.....#.......#...#...#.....#.#...........#...........#.......#...#.......#  
+  ###.#########.#.#.###.#.#######.###.###.###.#####.#.###.###.#####.###.###.#####.#.#######.#####.###.#.#####.#####.#####  
+  #.#.....#...........#...#...#.#.#.....#.....#.#...#.#.....#.#.#.....#.....#.....#.#.#.#.......#.#...#.....#.#.#.....#.#  
+  #.#####.#####.###.#####.###.#.#######.#.#.###.#.#####.###.#.#.#.#########.#.#.#####.#.###.#######.#.#######.#.###.###.#  
+  #...#...#.....#...#.#...#.#.#...#.#.....#.#.......#...#.#.#...#.#.#.......#.#.#...............#.#.#.........#.#.#.....#  
+  ###.#.#.#########.#.###.#.#.#.###.#.#.#########.#####.#.#.#.#.#.#.###.#####.###.#.#.#.###.#.###.###.#######.#.#.#.#####  
+  #.....#...#.....#.........#...#.#...#.........#.....#.#...#.#.....#.....#.#.#...#.#.#.#...#...........#...#.........#.#  
+  #########.#####.#.#.#.#.#.###.#.#######.#####.###.#####.###.###.###.#####.#.#.###.#.#.###.#.#####.#.###.#########.###.#  
+  #.#.........#.....#.#.#.#.#.......#.......#.#.#.......#.#...#.#...#...#...#.....#.#.#...#.#.....#.#.............#.#...#  
+  #.###.###.#####.#########.###.#####.###.#.#.#####.#####.###.#.###.#.###.###.#.###.#######.###.#.#.#.#######.#####.###.#  
+  #...#...#.....#.#.#...#.........#...#...#.#.....#.#.#.....#...#...#.......#.#.#.........#...#.#.#.#.......#.#...#.#.#.#  
+  #.#########.###.#.#.#####.#.###.###.#######.###.#.#.#.###.###.###.#.#.#.###.#####.#.###.#.#.###.#.#.#.#######.#.###.#.#  
+  #...#.......#.#.#.....#.#.#.#...........#.....#.....#.#...#.....#.#.#.#.#.......#.#.#...#.#.#.#.#.#.#...#...#.#.#.#...#  
+  #.#########.#.###.###.#.###########.#########.###########.#.###.###.###.#########.#########.#.#####.#.###.###.###.###.#  
+  #...#.#.#.......#.#.....#.....#.....#.#.......#.#...#.#...#...#.#.#.#.#.#...#...........#.#.....#...#.....#...#.......#  
+  ###.#.#.#####.#####.###.#####.#####.#.#####.###.###.#.###.#.#####.#.#.###.#######.#######.#.#######.#.###.###.#####.###  
+  #.....#.#.#.#.....#.#.#.........#.#.....#.#...........#...#.....#.........#...#...#...#...#.#.#...#.#.#.#...#.#.#.....#  
+  #.#.#.#.#.#.#.#######.#########.#.###.###.###.#####.#####.#.#######.#########.###.###.###.###.#.#####.#.#####.#.#.#.###  
+  #.#.#.......#.....#.#.#.#.#.#.#.#.....#...#...#.#.#.#...#.#.#.#.#.....#...#...#...#...#.....#.....#.#.#.#...#...#.#.#.#  
+  #####.#####.#.#####.#.#.#.#.#.#.###.#####.#.###.#.###.###.#.#.#.#.#.###.###.#.#.#####.#.#.#######.#.###.#.#####.###.#.#  
+  #.#.#.#.....#.....#.......................#...#...#.......#.....#.#.#.......#.#.........#...#.#.#.#...#.....#.#.#.....#  
+  #.#.#######.#.#######.###.#.#####.#######.#.#####.#.#.###.###.#####.#######.#.###.#######.#.#.#.#.#.#####.###.#.###.###  
+  #...#...........#.#.#.#...#.#...#.#...#.#.#.....#...#...#.#...#...........#.#...#.....#.#.#...........#...#...#.#...#.#  
+  ###.#.#.###.#.###.#.#.#.#####.#####.###.#.#.#######.#.#.#.#.###########.###.###.#.#.#.#.#.#.#.#.###.#.###.###.#.#.#.#.#  
+  #.....#.#.#.#.#.....#.#...#...#.#.#.....#.#.....#...#.#.#.#...#.#.#...#.#...#.#.#.#.#.#.#.#.#.#.#.#.#...#.......#.#...#  
+  ###.#.#.#.#.#####.###########.#.#.#.###.#.#.#####.#.#######.###.#.#.#.#.#.#.#.#.#.#####.#.#######.#######.#.###.#.#####  
+  #.#.#.#.#...#.#.......#.......#.....#.#.#.#...#.#.#.......#.......#.#...#.#.#.#...#.#...#.#...#...#...#...#.#...#.....#  
+  #.#########.#.###.#.#####.#.#.#####.#.#.#.###.#.###.###.#########.#.#######.#.#####.###.###.###.#####.#########.###.###  
+  #.....#.#.#.#.....#...#...#.#.#.......#...#.....#.....#...#.......#.....#.................#...#...#.........#.#.#.#...#  
+  #.#####.#.#.#######.#######.#########.#########.#########.#.#########.#.#######.#########.#.###.#####.#######.#.#.#.###  
+  #.....#.#.#.#...#.#.#.#.#.#...#      F         O         O X         N U       W        #.#.....#.#.#...#.#.#.........#  
+  #.#####.#.#.#.###.#.#.#.#.#.###      Z         G         D L         B Y       W        ###.#####.#.###.#.#.###.###.###  
+  #...#.#.#.#.#.#...#.......#...#                                                         #.......#.....#...#...#.#.#...#  
+  #.###.#.#.#.#.###.#.#.###.#.#.#                                                         #.#.#######.###.#.###.#.#.#.###  
+PL....#.#.#...#...#...#...#...#.#                                                         #.#.#.#.#...#.#.#.....#.#.#.#.#  
+  #.###.#.###.#.###.#.#.#.###.#.#                                                         #.###.#.#.###.###.#######.#.#.#  
+  #.......#.#.......#.#.#.#...#..EL                                                     PM..#.........#.#.....#.#.......#  
+  #.#.#.###.###.#.#.###########.#                                                         #.###.###.###.#.#.#.#.###.###.#  
+  #.#.#.........#.#.#.....#...#.#                                                         #.#.#...#.......#.#.......#....BR
+  #############.#.#####.###.#####                                                         #.#.###.#########.#.#.###.###.#  
+YP..#.........#.#...#.#.#.#.....#                                                         #.#...#.....#.#.#.#.#...#...#.#  
+  #.#.###.#.#####.###.#.#.###.#.#                                                         #.#.#.###.###.#.###########.#.#  
+  #...#.#.#.#.#.#.#...#.....#.#.#                                                         #...#.....#.#.#.#...#.#...#.#.#  
+  #.###.###.#.#.###.#.#.#.###.###                                                         ###########.#.#.#.###.###.###.#  
+  #...#.#...........#...#........TH                                                       #.......#...............#...#.#  
+  ###.#.#####################.###                                                         #.#####.#.###.###.#####.#.#.###  
+EV..#.#...#.................#...#                                                       LV..#.#.....#...#...#.#.#...#.#..UN
+  #.###.#.#####.#.###.#.#.###.###                                                         #.#.#.###.###.#.#.#.#.#####.#.#  
+  #.#...#...#...#.#...#.#.#.#...#                                                         #.#...#.#.#.#.#.#.#.#.......#.#  
+  #.#.#####.#.#.#.###.###.#.#####                                                         #######.###.#######.#.#######.#  
+  #.#.#.....#.#.#...#.#.#.......#                                                         #.#.......#.....#.#.#.........#  
+  #.#.#.#######.#######.###.#.#.#                                                         #.#####.#.###.###.#.###########  
+  #...#...........#...#...#.#.#..XC                                                       #...#.#.#.........#...........#  
+  #######.#########.###.###.#####                                                         #.#.#.###.###.###.###.#.#.#.###  
+WV..#.#.#.#...............#.#.#.#                                                         #.#...#.#.#.#.#.......#.#.#....OD
+  #.#.#.#.#.#.#.###.#####.###.#.#                                                         #.###.#.#.#.#########.#########  
+  #.....#.#.#.#...#.#.....#.#.#..PI                                                       #.#.....#...#.....#.#.....#...#  
+  #####.###.#####.#.#####.#.#.#.#                                                         #.#.#.#.###.###.###.#########.#  
+AA........#.....#.#.#...#.......#                                                       UN..#.#.#.....#...#...#.#.#.#...#  
+  #.#######.###########.###.###.#                                                         ###.###########.###.#.#.#.###.#  
+  #...........#.#.#.#.....#.#.#.#                                                         #...#...#.......#..............OA
+  #.#.#.#.#.#.#.#.#.###.#####.###                                                         #####.#.#.#.###.#.#.###.###.#.#  
+  #.#.#.#.#.#.....#.............#                                                         #.#...#...#.#.....#.#...#...#.#  
+  #################.#########.###                                                         #.#.###.#.#########.###########  
+  #.....#.#.#.#.......#.....#...#                                                         #.#...#.#.#.......#.#.#.....#.#  
+  #.#.###.#.#.#######.#.###.###.#                                                         #.#.###.#.#.#########.#.#####.#  
+  #.#.#...#...#.#...#.....#.#.#.#                                                       SL....#.#.#.#.#.#.....#...#.#...#  
+  #.#.#.#.#.###.#.#.#######.#.#.#                                                         #####.#####.#.#.#.#####.#.#.###  
+EL..#...#.........#.........#.#..WV                                                       #...............#.#.#..........XP
+  #.###########.###.#########.###                                                         #.#########.###.###.###.#####.#  
+  #.#.......#...#...#...........#                                                         #.#.....#...#...#...#.......#.#  
+  ###.#####.###.#########.#.###.#                                                         #.#.###.#.#.#####.#.#####.#.#.#  
+UY..#...#.....#.#.........#.#....XP                                                     PL..#...#...#.#.#.#.#...#...#.#.#  
+  #.#.###.#.###########.#.#.#####                                                         #.###.#######.#.###.#.#.#####.#  
+  #.#.#...#.#.#.#.#.#...#.#.....#                                                         #...#...............#.....#.#.#  
+  #.#.#.#####.#.#.#.###.###.#####                                                         #.#.###############.#.#.###.#.#  
+  #...#...................#.....#                                                         #.#.#...........#...#.#.#...#.#  
+  ###############.###############                                                         #.#.###.#######.###########.###  
+  #...........#.#.#.............#                                                         #.#.#.....#...........#...#.#.#  
+  #####.#.#.###.###.#######.###.#                                                         #########.#.#.###########.#.#.#  
+  #.....#.#.#.#.#.........#.#...#                                                         #.#.#.....#.#.#...#...#...#....TH
+  #.#####.###.#.#######.#####.###                                                         #.#.###.#.#.#########.###.#.#.#  
+ZZ....#...#...#.#...........#.#.#                                                       JG........#.#.................#.#  
+  ###.#.###.#.#.###.#.#.#####.#.#                                                         #.###.#.###.#.#.#####.###.#.###  
+JH....#.....#.......#.#...#......EV                                                       #.#...#...#.#.#...#.....#.#...#  
+  #.#.#######.#.#####.#.#####.###                                                         #.###.#########.###.#.#####.#.#  
+  #.#.#.......#.#.#.#.#.....#.#.#                                                         #.#...#...........#.#.#.#...#.#  
+  #.#.###.#.#.###.#.#.#######.#.#    V     J           Y       T     C     B       O      #.#####.###.#.###.#.###.###.#.#  
+  #.#.#...#.#...#.....#.#.......#    O     H           P       R     K     R       A      #.#.....#...#...#.#.#.#.....#.#  
+  #.#.#.#.###.#.#.#.#.#.#.###.#.#####.#####.###########.#######.#####.#####.#######.###############.#.#.#.###.#.#.#.#.###  
+  #.#.#.#.#...#.#.#.#...#...#.#.#.......#.......#...#.....#.....#.......#...#...#.........#.#.#.....#.#.#.#.#.#...#.#.#.#  
+  ###.#####.#.#######.###.###.#######.#####.#####.###.#######.###.#######.###.#.#.#.#.###.#.#.###.#####.###.#########.#.#  
+  #.....#.#.#.....#...#...#.#.#...........#.........#.....#...#.#.....#.#.....#.#.#.#.#.....#...#.#.#.........#.........#  
+  #.#####.#.###.#####.#####.#.#.###.###.#.###.#.###.#####.#.#.#.#.#####.###.###.#.#####.#.###.#####.###.###.###.#.#.###.#  
+  #...#...#...#.#.........#...#.#...#.#.#.#.#.#...#.#.....#.#...#.......#.#.#...#.#...#.#.#.....#.#.....#.....#.#.#.#...#  
+  #######.#####.#####.#######.#####.#.#.###.#####.#####.###.###########.#.#####.#.#.#########.###.###.#.###.#######.###.#  
+  #.......#.#.....#...#.........#...#.#.#...#.........#...#.#.#.......#...#.#.#.#...#...#...#.#.....#.#.#.#.#.........#.#  
+  #.#.#.#.#.#.#####.#####.###.#####.#.#.#.#####.#.#.#.###.#.#.#####.#.#.###.#.#.#.###.###.###.###.###.###.###.#.###.#####  
+  #.#.#.#.......#...#...#.#...#.......#.#...#...#.#.#.#.#.#.....#...#.#.....#...#...#.#.#.........#.#...#...#.#.#.......#  
+  #######.###.###.#.#.###############.###.#####.###.###.#.#.#.#.#.#.#.#.###.###.###.#.#.#.###.#.###.###.#.#.#.#####.#.#.#  
+  #...#.#.#.....#.#.#.#.........#.#.........#.....#.#...#.#.#.#.#.#.#.....#.#...#...#...#...#.#.....#.#.#.#.......#.#.#.#  
+  #.###.###.#.#####.#.#########.#.#######.#.###.#####.###.#.#.#####.###.#######.#.###.###.#######.#.#.#####.#.#.#.###.###  
+  #.....#...#...#.#.....#...............#.#.#.....#.......#.#.#.....#.#...#.....#.....#.....#.....#.....#.#.#.#.#.#.....#  
+  #####.#.#.###.#.#.#########.#####.###.#.###.###.#######.#.#####.###.#.#.#####.#.###.#.#.#######.#.#.###.#.#######.#.#.#  
+  #.......#.#.#.#.....#.......#.#...#.#.....#.#...#.#.#...#...#.......#.#.#.....#.#.....#...#...#.#.#.#.......#.#.#.#.#.#  
+  #.###.#.#.#.###.#######.#####.#.#.#####.#.###.###.#.#.#.#.#####.#####.#####.###.#.###.###.#.###.#.###########.#.#.#.#.#  
+  #.#.#.#.#...#...#...#.#.#.#.#.#.#.....#.#...#...#.....#.#...#.#.....#.#.......#.#.#...#.#.....#.#.#.........#...#.#.#.#  
+  #.#.#.#.#.###.#####.#.###.#.#.###.#######.#####.#.###.###.#.#.#.#############.#######.#.#.###.#####.#.###.###.#####.###  
+  #.#.#.#.#...#...#.#.....................#.#.....#...#.#...#...#.#...#.#.......#...#.#...#.#.#.#.....#.#.........#.#...#  
+  #.#.#.#.#.#######.#####.#####.#####.#########.#.#.#########.#.#.###.#.#####.###.###.#.#.###.#####.#########.#####.#####  
+  #.#...#.#.#...#.........#.#.#.#.......#...#.#.#.#.........#.#.#.#.....#...........#...#.#.......#.#.#.#.#...........#.#  
+  #.#######.###.###.#######.#.#####.#####.###.#.#######.#####.###.###.#.###.###.#######.#######.###.#.#.#.###.###.###.#.#  
+  #.....#.#.#.#.#.#.#.#.....#.........#.........#.#...#...#.#...#.....#.#.#...#.#.#.#.#.....#...............#...#.#.....#  
+  #.#####.###.#.#.###.#####.#######.#####.#.###.#.#.#.#.###.#.#########.#.#.###.#.#.#.#.#########.#####.#.#.#######.#.#.#  
+  #.#.#.......................#.#.#.#...#.#.#.....#.#...#.#...#.#.#.......#.#.....#.#...#...#.........#.#.#.......#.#.#.#  
+  #.#.#.###.#####.#########.#.#.#.#.#.###########.#.###.#.#.###.#.###.###.###.#####.###.###.#.#.#.#.###.#####.#.###.#####  
+  #.#...#.#.#.#...#.........#.........#...#.#.....#...#.#.......#...#...#.#.....#...#.........#.#.#...#...#...#.#.#...#.#  
+  #######.###.###.#####.#####.#####.#.#.###.###.###.#######.#.#.#.#####.#######.#.#.#.#####.#####.#.#.#.#####.###.#####.#  
+  #...............#.....#.......#...#.....#.......#.....#...#.#.#.......#.......#.#.......#.....#.#.#.#.....#...........#  
+  #####################################.#####.#######.#######.###.#########.#####.#######################################  
+                                       O     C       N       X   F         S     W                                         
+                                       G     K       B       L   Z         L     W                                         

inputs/20s1.txt

@@ -0,0 +1,19 @@
+         A           
+         A           
+  #######.#########  
+  #######.........#  
+  #######.#######.#  
+  #######.#######.#  
+  #######.#######.#  
+  #####  B    ###.#  
+BC...##  C    ###.#  
+  ##.##       ###.#  
+  ##...DE  F  ###.#  
+  #####    G  ###.#  
+  #########.#####.#  
+DE..#######...###.#  
+  #.#########.###.#  
+FG..#########.....#  
+  ###########.#####  
+             Z       
+             Z       

inputs/20s2.txt

@@ -0,0 +1,37 @@
+                   A               
+                   A               
+  #################.#############  
+  #.#...#...................#.#.#  
+  #.#.#.###.###.###.#########.#.#  
+  #.#.#.......#...#.....#.#.#...#  
+  #.#########.###.#####.#.#.###.#  
+  #.............#.#.....#.......#  
+  ###.###########.###.#####.#.#.#  
+  #.....#        A   C    #.#.#.#  
+  #######        S   P    #####.#  
+  #.#...#                 #......VT
+  #.#.#.#                 #.#####  
+  #...#.#               YN....#.#  
+  #.###.#                 #####.#  
+DI....#.#                 #.....#  
+  #####.#                 #.###.#  
+ZZ......#               QG....#..AS
+  ###.###                 #######  
+JO..#.#.#                 #.....#  
+  #.#.#.#                 ###.#.#  
+  #...#..DI             BU....#..LF
+  #####.#                 #.#####  
+YN......#               VT..#....QG
+  #.###.#                 #.###.#  
+  #.#...#                 #.....#  
+  ###.###    J L     J    #.#.###  
+  #.....#    O F     P    #.#...#  
+  #.###.#####.#.#####.#####.###.#  
+  #...#.#.#...#.....#.....#.#...#  
+  #.#####.###.###.#.#.#########.#  
+  #...#.#.....#...#.#.#.#.....#.#  
+  #.###.#####.###.###.#.#.#######  
+  #.#.........#...#.............#  
+  #########.###.###.#############  
+           B   J   C               
+           U   P   P               

inputs/20s3.txt

@@ -0,0 +1,37 @@
+             Z L X W       C                 
+             Z P Q B       K                 
+  ###########.#.#.#.#######.###############  
+  #...#.......#.#.......#.#.......#.#.#...#  
+  ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###  
+  #.#...#.#.#...#.#.#...#...#...#.#.......#  
+  #.###.#######.###.###.#.###.###.#.#######  
+  #...#.......#.#...#...#.............#...#  
+  #.#########.#######.#.#######.#######.###  
+  #...#.#    F       R I       Z    #.#.#.#  
+  #.###.#    D       E C       H    #.#.#.#  
+  #.#...#                           #...#.#  
+  #.###.#                           #.###.#  
+  #.#....OA                       WB..#.#..ZH
+  #.###.#                           #.#.#.#  
+CJ......#                           #.....#  
+  #######                           #######  
+  #.#....CK                         #......IC
+  #.###.#                           #.###.#  
+  #.....#                           #...#.#  
+  ###.###                           #.#.#.#  
+XF....#.#                         RF..#.#.#  
+  #####.#                           #######  
+  #......CJ                       NM..#...#  
+  ###.#.#                           #.###.#  
+RE....#.#                           #......RF
+  ###.###        X   X       L      #.#.#.#  
+  #.....#        F   Q       P      #.#.#.#  
+  ###.###########.###.#######.#########.###  
+  #.....#...#.....#.......#...#.....#.#...#  
+  #####.#.###.#######.#######.###.###.#.#.#  
+  #.......#.......#.#.#.#.#...#...#...#.#.#  
+  #####.###.#####.#.#.#.#.###.###.#.###.###  
+  #.......#.....#.#...#...............#...#  
+  #############.#.#.###.###################  
+               A O F   N                     
+               A A D   M                     

main.go

@@ -53,6 +53,7 @@ var dayMap = []day{
 	&days.Day17{},
 	&days.Day18{},
 	&days.Day19{},
+	&days.Day20{},
 }
 
 func main() {

utilities/bisect.go

@@ -12,10 +12,8 @@ import (
 // and the failure is less than or equal to the acceptance threshold
 // (usually 1, for integers).
 func Bisect[T Number](low, high, threshold T, tryFunc func(val T) bool) T {
-	currVal := low
-
 	for T(math.Abs(float64(high-low))) > threshold {
-		currVal = low + ((high - low) / 2)
+		currVal := low + ((high - low) / 2)
 		success := tryFunc(currVal)
 		if success {
 			low = currVal
@@ -24,5 +22,5 @@ func Bisect[T Number](low, high, threshold T, tryFunc func(val T) bool) T {
 		}
 	}
 
-	return currVal
+	return low
 }