Optimizations and minor cleanups

Thanks to Go's profiling tools, I discovered that the memoization, while it was cutting down runtime significantly, was itself slow because it was using arrays. Swapping those arrays out for maps made a _massive_ difference (4s/14s part1/part2 to 1ms/2ms with no other changes). Lesson learned. Again.

The IntHeap rename was long overdue since I took the code originally from Go's sample docs for priority queues.

.gitignore

@@ -2,4 +2,3 @@
 __debug_bin
 aoc2019
 debug.test
-*.*prof

days/14.go

@@ -104,10 +104,26 @@ func (d *Day14) Part1() string {
 func (d *Day14) Part2() string {
 	oreAvailable := int64(1000000000000)
 	estimate := oreAvailable / d.getOreRequiredForFuel(1)
-	lastSuccess := u.Bisect(estimate, estimate*2, 1, func(val int64) bool {
+
-		oreConsumed := d.getOreRequiredForFuel(val)
+	high := estimate * 2
-		return oreConsumed < oreAvailable
+	low := estimate
-	})
+
+	lastSuccess := low
+	lastFailure := high
+	fuelProduced := low
+
+	for math.Abs(float64(lastFailure-lastSuccess)) > 1 {
+		oreConsumed := d.getOreRequiredForFuel(fuelProduced)
+		adjustment := (lastFailure - lastSuccess) / 2
+		if oreConsumed < oreAvailable {
+			lastSuccess = fuelProduced
+		} else {
+			lastFailure = fuelProduced
+			adjustment = -adjustment
+		}
+
+		fuelProduced += adjustment
+	}
 
 	return fmt.Sprintf("Maximum fuel we can make from 1 trillion ore: %s%d%s", u.TextBold, lastSuccess, u.TextReset)
 }

days/18.go

@@ -6,6 +6,7 @@ import (
 	"math"
 	"strings"
 
+	"github.com/edwingeng/deque/v2"
 	u "parnic.com/aoc2019/utilities"
 )
 
@@ -27,31 +28,16 @@ var (
 	}
 )
 
-type reachableKeysMemo struct {
-	pos       rune
-	keysFound int
-}
-
-type minStepsMemo struct {
-	pos        string
-	keysToFind int
-	keysFound  int
-}
-
 type Day18 struct {
 	entrance day18Vec
 	grid     [][]day18Cell
 	doors    map[day18Vec]int
 	keys     map[day18Vec]int
-	knownReachableKeys map[reachableKeysMemo][]u.Pair[rune, int]
-	knownMinimumSteps  map[minStepsMemo]int
 }
 
 func (d *Day18) Parse() {
 	d.doors = make(map[day18Vec]int)
 	d.keys = make(map[day18Vec]int)
-	d.knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
-	d.knownMinimumSteps = make(map[minStepsMemo]int, 0)
 
 	lines := u.GetStringLines("18p")
 	d.grid = make([][]day18Cell, len(lines))
@@ -119,15 +105,14 @@ func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, g
 		return retAdjacent
 	}
 
-	queue := make([]u.Pair[int, day18Vec], 0)
+	queue := deque.NewDeque[u.Pair[int, day18Vec]]()
 	visited := make(map[day18Vec]bool)
 	for _, adjacent := range getAdjacent(inPos) {
-		queue = append(queue, u.Pair[int, day18Vec]{First: 1, Second: adjacent})
+		queue.PushBack(u.Pair[int, day18Vec]{First: 1, Second: adjacent})
 	}
 
-	for len(queue) > 0 {
+	for !queue.IsEmpty() {
-		next := queue[0]
+		next := queue.PopFront()
-		queue = queue[1:]
 
 		if _, exists := visited[next.Second]; !exists {
 			visited[next.Second] = true
@@ -157,7 +142,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 = append(queue, u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
+					queue.PushBack(u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
 				}
 			}
 		}
@@ -170,17 +155,17 @@ type day18PriorityQueue struct {
 	distance int
 	neighbor rune
 }
-type day18PriorityQueueHeap []day18PriorityQueue
+type PriorityQueueHeap []day18PriorityQueue
 
-func (h day18PriorityQueueHeap) Len() int           { return len(h) }
+func (h PriorityQueueHeap) Len() int           { return len(h) }
-func (h day18PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
+func (h PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
-func (h day18PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
+func (h PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
-func (h *day18PriorityQueueHeap) Push(x any) {
+func (h *PriorityQueueHeap) Push(x any) {
 	*h = append(*h, x.(day18PriorityQueue))
 }
 
-func (h *day18PriorityQueueHeap) Pop() any {
+func (h *PriorityQueueHeap) Pop() any {
 	old := *h
 	n := len(old)
 	x := old[n-1]
@@ -188,19 +173,26 @@ func (h *day18PriorityQueueHeap) Pop() any {
 	return x
 }
 
+type reachableKeysMemo struct {
+	pos       rune
+	keysFound int
+}
+
+var knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
+
 func (d Day18) reachableKeys(inPos rune, keysFound int, graph day18Graph) []u.Pair[rune, int] {
 	memo := reachableKeysMemo{
 		pos:       inPos,
 		keysFound: keysFound,
 	}
-	if v, exists := d.knownReachableKeys[memo]; exists {
+	if v, exists := knownReachableKeys[memo]; exists {
 		return v
 	}
 
 	ret := make([]u.Pair[rune, int], 0)
 	distance := make(map[rune]int)
 
-	ih := make(day18PriorityQueueHeap, 0)
+	ih := make(PriorityQueueHeap, 0)
 
 	for _, p := range graph[inPos] {
 		ih = append(ih, day18PriorityQueue{
@@ -237,17 +229,25 @@ func (d Day18) reachableKeys(inPos rune, keysFound int, graph day18Graph) []u.Pa
 		}
 	}
 
-	d.knownReachableKeys[memo] = ret
+	knownReachableKeys[memo] = ret
 	return ret
 }
 
+type minStepsMemo struct {
+	pos        string
+	keysToFind int
+	keysFound  int
+}
+
+var knownMinimumSteps = make(map[minStepsMemo]int, 0)
+
 func (d Day18) minimumSteps(inPos string, keysToFind int, keysFound int, graph day18Graph) int {
 	memo := minStepsMemo{
 		pos:        inPos,
 		keysToFind: keysToFind,
 		keysFound:  keysFound,
 	}
-	if v, exists := d.knownMinimumSteps[memo]; exists {
+	if v, exists := knownMinimumSteps[memo]; exists {
 		return v
 	}
 
@@ -278,7 +278,7 @@ func (d Day18) minimumSteps(inPos string, keysToFind int, keysFound int, graph d
 		}
 	}
 
-	d.knownMinimumSteps[memo] = int(best)
+	knownMinimumSteps[memo] = int(best)
 	return int(best)
 }
 
@@ -335,8 +335,8 @@ func (d *Day18) Part2() string {
 	// d.Draw(grid, d.keys, d.doors, entrances...)
 
 	// clear memoized maps that (might have) came from part1
-	d.knownMinimumSteps = make(map[minStepsMemo]int)
+	knownMinimumSteps = make(map[minStepsMemo]int)
-	d.knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
+	knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
 
 	graph := d.buildGraph(entrances, d.keys, d.doors, grid)
 	minSteps := d.minimumSteps("1234", len(d.keys), 0, graph)

days/19.go

@@ -1,146 +0,0 @@
-package days
-
-import (
-	"fmt"
-
-	u "parnic.com/aoc2019/utilities"
-)
-
-type Day19 struct {
-	program u.IntcodeProgram
-}
-
-func (d *Day19) Parse() {
-	d.program = u.LoadIntcodeProgram("19p")
-}
-
-func (d Day19) Num() int {
-	return 19
-}
-
-func (d *Day19) Part1() string {
-	grid := make([][]bool, 50)
-	for y := 0; y < len(grid); y++ {
-		grid[y] = make([]bool, 50)
-	}
-
-	count := int64(0)
-
-	for y := 0; y < 50; y++ {
-		for x := 0; x < 50; x++ {
-			d.program.Reset()
-			d.program.RunIn(func(inputStep int) int64 {
-				if inputStep == 1 {
-					return int64(x)
-				}
-
-				return int64(y)
-			}, func(val int64, state u.IntcodeProgramState) {
-				res := val == 1
-				grid[y][x] = res
-				if res {
-					count++
-				}
-			})
-		}
-	}
-
-	// fmt.Println("50x50 tractor view:")
-	// for y := 0; y < len(grid); y++ {
-	// 	for x := 0; x < len(grid[y]); x++ {
-	// 		if grid[y][x] {
-	// 			fmt.Print("█")
-	// 		} else {
-	// 			fmt.Print(" ")
-	// 		}
-	// 	}
-	// 	fmt.Println()
-	// }
-
-	return fmt.Sprintf("Points affected in 50x50 area: %s%d%s", u.TextBold, count, u.TextReset)
-}
-
-func (d *Day19) Part2() string {
-	f := func(x, y int) bool {
-		ret := false
-		d.program.Reset()
-		d.program.RunIn(func(inputStep int) int64 {
-			if inputStep == 1 {
-				return int64(x)
-			}
-			return int64(y)
-		}, func(val int64, state u.IntcodeProgramState) {
-			ret = val == 1
-		})
-
-		return ret
-	}
-
-	// 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++ {
-		for x := 0; x < 10*y; x++ {
-			if f(x, y) {
-				startY = y
-				startX = x
-				break
-			}
-		}
-	}
-
-	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
-				} else {
-					return true
-				}
-			}
-			if !foundX {
-				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

@@ -1,398 +0,0 @@
-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,3 +1,5 @@
 module parnic.com/aoc2019
 
 go 1.18
+
+require github.com/edwingeng/deque/v2 v2.0.1

go.sum

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

inputs/18p.txt

@@ -1,81 +1,81 @@
 #################################################################################
-#...............#.......#...............#.........#.......#.......#.....#.......#
+#...#.........P...................#.....#.........#.......#.........#...........#
-#.#########.#.###.#####.#.#.#######.#####.#######.#.#######.#.###.###.#.#.#####.#
+#.###.#############.#.###########.#.#.###.#########.###.###.#######.#.###########
-#.#.#.....#.#.#...#...#..f#...#.....#...#...#.....#.........#...#.....#...#m....#
+#.#...#.#...V.....#.#..t..#.......#.#..a#...........#.#..c..#...#.#.#...........#
-#.#.#.###.###.#.#####.#######.#######.#.#.#.#.#######.#########.###########.#####
+#.#.###.#.#######.#####.#.#####.#######.#.###########.#######.#.#.#.###########.#
-#...#...#.#...#.......#.....#.#.......#.#.#.#...#...#...#.......#..h......#.....#
+#...#...#...#.#...#.J.#.#.....#.........#.......#.......#.....#.#.#.......#...#.#
-###.###.#.#.#########.#.###.#T#.#######.###.###.#B#.#.###.#######.#######.#####.#
+#Z###.#####.#.#.###.#.###.###.#################.#.###.#.#.#####.#.#######.#.#.#.#
-#...#...#...#.....#...#...#.#...#.....#.#...#.#...#.#.#...#.........#...#.......#
+#.....#...#.#.......#...#...#.#...#.....#...#.#.#.#...#.#...#.....#.......#.#.#.#
-#####.#######.###.#.###.#.#######.###.#.#.###.#####.###.#.###########.#.#######.#
+###.###.#.#.###########.###.#.#.#.#.###.#.#.#.#.#.#.###.###.#######.#######.#.#.#
-#...#...#.....#.#...#.#.#.....#...#.....#.#.....#...#...#.#...........#.#.....#.#
+#.#.#...#..y#.........#...#.#...#...#...#.#...#.#.#.#.......#.......#.......#...#
-#.#.###.#.#####.#####.#.#####.#.###.#####.#.###.#.###.#####.###########.#.###.#.#
+#.#.#.#######.#######.###.#######.###.###.###.#.###.#######.#.#######.#########.#
-#.#.....#.#.....#.........#...#...#.#...#.#...#..x#...W.....#.....#.....#.#...#.#
+#.#.#..q........#.....#.#...#.E.#...#...#.#...#...#.....#.#.#.#...........#...#.#
-#.#######.###.#.#########.#.#####.###.#.#.###.#######.#######.###.#.#####.#.#####
+#.#.#############.#####.###.#.#.#######.#.###.###.#.###.#.#.#.#####.#####.#.#.#.#
-#.........#...#.......#.#.#.#...#.....#.#.#.#.#.....#...#.....#...#.#.....#.....#
+#.#...F.......#...#...#.......#.........#...#.#...#.#...#.#.#.....#.#.....#.#...#
-#.#########O#########.#.#.#.#.#.#.#####.#.#.#.###.#.#.###.#####.###.#.#########.#
+#.#########.###.###.#S###################.#I###.#####.###.#.#####.#.#.#########.#
-#.#.........#.........#...#.#.#.#...#.#.#.#.......#.#.#...#...#.#.......#.....#.#
+#...#...#...#...#...#....u......#.#.....#.#...#.#...#.#...#.....#.#.#.#.......#.#
-#.#####.#########.#########.#.#.###.#.#.#.#########.###.###.###.#####.###.###.#.#
+#.###.#.#.###.###.#############.#.#.###.#####.#.#.#.#.#.#######.#.#.#.#.#####.#.#
-#.....#...#.....#.#.........#.#.#.....#.#.....#.....#...#...........#.#...#e..#.#
+#.#...#.#.#.#.#s..#...#hG.#...#.#.#...#.#.....#...#...#.#.......#.#.#...#...#.#.#
-#####.###.#K###.#.#####.#####.#.#######.#####.#####.#.#.###########.###.###.###.#
+#.#.###.#.#.#O#.###.#.#.#.#.#.#.#.#.###.#.###.#########.#.#######.###.###.###.#.#
-#...#.....#.#...#.......#.....#.#.......#.....#...#...#.#.........#.....#.#.#...#
+#m..#.#...#.#.#.#...#...#...#g#.#.#.#...#.#.#.#.........#.#.#...#...#.....#...#.#
-#.#####.###.#.#########.#.#####.#.#####.#.#####.#.#######.#####.#.#######.#.#.#.#
+#.###.#####.#.#.#H###########.#.#.#.#.###.#.#.###.#.#####.#.#.#.#.#.#.#####.###.#
-#.#j..#.#...#a..#.....#.#.#.......#.....#.......#...........#.#.#.......#.#...#.#
+#.#.........#...#.....#...#...#.#...#...#.#...#...#.#...#.#.#.#.#.#.#.#..w#.#.#.#
-#.#.#.#.#.#####.#.#####.#.#############.#.###################.#########.#.#####.#
+#.#.#####.#.#############.#.###U###.###.#.#.###.###.#.#.#.#.###.###.#.#.#.#.#.#.#
-#...#.#.#.#...#...#.....#.#..z..#.....#.#.....#.......#.....#...#...#...#...#...#
+#.#.....#.#.#.....#.......#.#.....#.#...#.#.....#...#.#.#.#...#...#.#.#.#...#...#
-#.###.#.#.###.#####.#####.#.###.#.###.#######.#.#.#####.###.###.#.#.#.###.###.###
+#.#######.#.###.#.#####.###.#####.###.#.#.#######.###.#.#.#.#####.#.###.#####.###
-#.#...#.#.....#.#...#...#.#...#.#.#.#...#.....#.#.....#...#.....#.#...#.#...#...#
+#.#.......#.....#.....#...#.#...#b#...#.#.#.#.....#...#.....#.....#...#.#.....#.#
-###.###.#####.#.#.###.#.#.###.#.#.#.###.#.###########.###.#######.#####.#.#.###.#
+#.#.#################.#.#.#.#.#.#.#.###.#.#.#.#####.#########.#######.#.#.#####.#
-#...#...#...#.#.......#.#.....#.#.....#.#.#.............#...#...#...#.....#.#...#
+#.#.#.......#.......#.#.#.#.B.#...#.#.#.#.#.....#...#.....#...#.......#.#...#...#
-#.#.#.#####.#.#############.###.###.###.#.#.#########.#####.###.#.#.#####.#.#.###
+#.#.#.#######.###.###.#.#.#########.#.#.#.#######.###.#.###.#####.#.###N###.#.###
-#.#.#.#.....#.............#...#.....#...#.#.....#...#.#.....#...#.#.#...#.#.#.#.#
+#.#.#...#.....#...#...#.#...........#.#.#.......#.#...#.#...#...#.#.#...#...#...#
-#.###.#.#.###############.###.#####.#.#.#.#####.#.#.#.#.#####.###.#.#.#.#.#.#.#.#
+#.#.#.#.#.#####.###.###.###########.#.#.#.#####.#.#.###.#.###.#.###.#.###.###.#.#
-#.#...#.#.......#.........#...#...#.#.#.#.#.....#.#...#.#.........#.#.#.#.#...#.#
+#...#.#.#.#...#.....#.#.#...#.......#...#.#..r#...#.#...#.....#.....#.#.#...#.#.#
-#.#.#######.###.#.#########.###.#.###.#.#.#.###########.#.#########.#.#.#####.#.#
+#######.#.###.#######.#.###.#.#######.###.###.#######.#.#############.#.###.#.#.#
-#.#.......#...#.#.#.......#...#.#.#...#.#.#...#.......#.#.#.......#...#.#...#c..#
+#.......#...#.......#.#...#.#.#.....#.#.#.....#.......#.......#.......#...#.#.#.#
-#.#######.#.#.###.###.###.#####.#.#.###.#.###.#.#####.#.###.#####.#.###.#.#.###.#
+###.###.###.#.#####.#.###.#.#.###.#.#.#.#####.#.#.###########.###.#####.#.#.###.#
-#.L..q..#.#.#...#...#.#.#.....#.#...#...#...#.....#...#.....#.....#...#...#.#...#
+#...#...#...#...#.#.#.......#...#.#.#.#.#.#...#.#...#...#...#...#.#.....#.#...#.#
-#.#######.#####.###.#.#.#####.#.#####.#####.#######S#########.#############.#.###
+#D###.###.###.#.#.#.###########.#.###.#.#.#.###.###.#.#.#.#.###.#.#.###.#####.#.#
-#...#...#.#.......#...#.#.....#.#...#...#...#.....#.....#...#.#.....#.....#k#...#
+#...#...#.#...#.#.#...........#.#.#...#.#...#...#...#.#...#...#...#.#.#.......#.#
-#.#.#.#.#.#.#####.#####.#.#####.#.#.###.#.###.###.###.#.###.#.#.###.#.###.#.###.#
+#.#.#####.#####.#.###########.#.#.#.###.#.#######.###.#######.#####.#.#########.#
-#.#...#.....#...........#.......#.#...........#.......#.....#...#.....#.....#...#
+#.#.............#...............#.................#.........#.................M.#
 #######################################.@.#######################################
-#.#...#...........#u....#...#.......#...............#.....#...................#.#
+#.#...#.......#...............................#.........#.........#..d#...#.....#
-#.#.#.#.#####.###.#.#.#.#.#.#.#.#####.#.#####.#####.#.###.#.###.#############.#.#
+#.#.#.#.#####.#.#######################.###.#.#.#######.#.###.###.###.#.#.#.#.#K#
-#.#.#...#...#...#.#.#.#.#.#...#.#s....#.#.....#...#.#.#.#..p#.#.#.....#.....#...#
+#...#...#...#.#.#...#.................#.#...#.#.#.#.....#...#.#.#.....#.#...#.#.#
-#.#.#######.###.###.#.###.#####.#.#####.#.#######.#.#.#.#####.#.#.###.#.###.###.#
+#.#########.#.#.#.#.#.###############.#.#.###.#.#.#.#########.#.#####.#.#####.###
-#...#.........#.#...#.#...#...#...#...#.#...#.....#...#.......#.#.#.#.....#.#.#.#
+#.....#...#.#.#.#.#.#.#...#.........#...#.#...#.#.#.......#...#.#.....#.....#...#
-#.###.#.#####.#.#.###.#.###.#######.#.#.#.#.#.###.#####.#######.#.#.#######.#.#.#
+#####.#.#.#.#.#.#.#.#.#.#.#.#####.#####.#.#.###.#.#######.#.###.#.#########.###.#
-#...#.#.#.....#...#...#.#...#.....#.#...#.#.#.#...#.....#.......#.#...#.V...#...#
+#...#.#.#...#.....#.#.#.#.#...#...#...#.#.#.#...#...........#.....#.......#.#...#
-###.###.#.#########.###.#.#.#.###.#.###.###.#.#####.#.###.#######.###.#.#####.###
+#.#.#.#.###.#########.#.#.###.#####.#.#.#.#.###.###.###########.###.###.###.#.#.#
-#.#.....#.#.....#...#.....#.#...#...#...#...#.#.....#.......#...#.#...#.#.....#.#
+#.#.#...#.W...#.......#.#...#.......#.#.#.#...#...#.#...#.#...#.#...#l#.#...#.#.#
-#.#######.#N#.#.#.#.#.#########.#.#######.###.#.#############.#.#.#.#.#.#.#####.#
+#.###.#########.#######.###.#.#######.#.#.###.###.#.#.#.#.#.#.###.###.#.#.###.#.#
-#.......#.#.#.#.#.#.#.#...#.....#.#.....#.#.........#.........#.#...#.#.#.....U.#
+#.....#.........#...#...#...#.......#...#.#...#...#...#...#.#.#.......#.#...#.#.#
-#.#######.###.#.#.###.#.#P#.#######.###.#.###.#######.#########.#####.#.#######.#
+#.#####.#######.#.#.#.###.###.#####.#####.###.#.#####.#####.#.#.#######.###.#.###
-#.#.....#...#.#.#.....#.#...#.......#...#...#...#.....#.......#.......#.#...#...#
+#.#...#.#.....#.#.#...#...#...#...#.....#...#.R.#...#.#.....#.....#...#...#x#...#
-#.#.###.###.#.#########.###.#.#######.#####.###.#.#####.###.###########.#.#.#.###
+#.#.#.#.###.###.#.#####.#######.#.#######.#.#####.#.###.###########.#.#.###.###.#
-#...#...#.#.#.#.....#...#...#.#.....#...#...#...#.......#...#.........#.#.#.#.#.#
+#...#.#...#...#.#.#...#...#...#.#.#.....#.#.#.....#.#...#.#.........#.#.......#.#
-#.###.#.#.#.#.#.#.###.#######.#.###.###.#.#####.#####.#####.#.#######.#.#.#Q#.#.#
+#####.###.###.#.#.###.###.#.#.#.#.#.###.#.#.#.#####.#.###.#.#########.#.#######.#
-#.#...#...#.#...#...#.....#...#.#...#...#.....#.....#.#.Yi#.#.#...#...#.#.#.#...#
+#...#...#...#...#...#.......#...#.#...#.#.#...#.#...#.....#.#.......#.#.#.......#
-#.#.#######.###.###.#####.#.###.#.#.#.###.###.#######.#.#.#.#.###.#.###.#.#.###.#
+###.###.###.###.###.#############.###.#.#.#####.#.#######.#.#.#.#####Y###.#####.#
-#.#.......#...#.#.....#...#.#...#.#.#...#.#...#.......#.#.#.#...#.....#.#.#.#...#
+#...#.....#...#...#.......#.#...#.....#.#.#..i..#.......#.#.#.#.......#...#.#...#
-#.#######.###.###.#.###.###.#####.#####.#.#.#.#.#######.#.#.###.#####.#.#.#.#####
+#.###.#######.###.#######.#.#.#.#######.#.#.###.#####.###.#Q###.#######.###.#.###
-#.#.....#.....#...#.#.#.........#.....#.#.#.#.#.#...#...#.#.#.#.#...#...#.#.....#
+#...#.#.......#..n#.#.....#...#...#.....#.#.#...#...#.#...#.#.#.#...#...#.#...#.#
-#.#.###.#######.#####.#########.#.#.###.#.#.#.#.#.###.###.#.#.#.#.#.#####.#####.#
+#.#.#.#.###.#####.#.#######.#####.#.#####.#.#.###.###.#.###.#.#.#.#.#.###.#.###.#
-#.#.#.....#.........#.#.....#.#.#.#b#...#.#.#.#.#.#..y#.#.#.#.#.#.#...#...#.....#
+#.#...#.#...#...#.....#...#.#...#...#...#...#...#.#...#...#..o#...#.#.#.......#.#
-#.###.#####.#######.#.#.###.#.#.#.#.#.#####.###.#.#.###.#.###.#.#.###.#.###.###.#
+#.#####.#####.#.#######.#.#.#.#.#####.#.#######.#.#.###.###########.#.#######.#.#
-#.E.#....d..#.......#...#.#.#.#.#.#.#...#...#...#.#...#.#...I.#...#..l#.#...#...#
+#.....#...#...#.#.......#.#.#.#.....#.#.#.....#.#.#.....#.........#.#.#...#.....#
-###.#.#######.###########F#.#.#.###.###.#.#.#.###.###.#.#########.#.###.#.###J###
+#####L###.#.###.#.#######.#.###.###.###.###.#.#.#.#######.#.#####.#.#.#.#.#######
-#...#...#...#...........#...#.......#...#.#.#.#.....#.G.#.......#.#.....#.#.#.#.#
+#...#.#...#.#...#...#...#.#...#.#.......#...#.#...#.....#.#.....#.#.#.#.#.......#
-#.#####.#.#########.#.#.#.#########.#.#.#.###.#####.###.#.###.#.#####.###.#.#.#.#
+#.#.#.#.###.#.#.###.#.#.#.###.#.#######.#.#######.#.#.###.#####.###.#.#.#######.#
-#..v..#...#.......#.#.#.#.#...#.....#.#.#...#.......#.#.#...#.#.....#.#...#.#...#
+#.#.#.#.....#.#.#...#.#.....#.#.......#.#.......#...#.#...#..j..#..v#.........#.#
-#####.#####.#####.###.###.#.#.#.#####.#.#Z#.#######X#.#.#####.#####.#.#.###.###.#
+#.#.#.#######.#.#.###.#.#####.###.###.###.#####.###.###.###.###.#.###.#########.#
-#...#.....#...#.....#...#...#.#.#...#.#.#.#.......#...#.....#.....#.#.#.#...#...#
+#.#.#.#...#...#.#...#.#.#...#...#...#...#...#.#.#...#...#.#.#...#.#.#.#.........#
-#.#######.#.#.#####.###.#####.#.#.###.#.###.#.#####.#######.#.###.#.###.#.###.###
+###.#.#.#.#.#######.#.###.#.###.#####.#.###.#.#.#.###.###.#.#####.#.#.#.#######.#
-#.........#.#.#...#...#...#...#...#...#.#...#.#...#.#.R....g#.#...#.....#.#...#.#
+#...#...#.#.........#.....#...#.....#f#.#.....#.....#e..#.#.......#.#.#.#.#...#.#
-#.###########.#.#.###.###.#.###.###.###.#.#####.#.#.#.#########.#########.#.###.#
+#.#######.#################.#.#####.###.#.#############A#.#########.#.#.#.#.#.#.#
-#...#.#.....#...#.#.#.#...#..t#.#...#...#.#.....#...#...#.....#.#..n....#.M.#...#
+#...#.....#.....#...#.....#.#.....#.....#...#...#.....#...#...#.......#.#.#.#..z#
-###.#.#.#.#.#####.#.#.#.#####.###.#####.#.#.###########.#.###.#.#.#######.###.#.#
+#.#.#.#####.###.###.#.###C#.###########.###.#.#T#.#.#####.#.###.#######.#.#.#####
-#...#...#.#.#..w#.#.#.#.....#...#.....#.#.#.......#.....#.#...#.#.#.D...#.....#.#
+#.#.#.X.#k..#.#...#...#...#.....#.....#.#...#.#...#.......#.....#....p..#...#...#
-#C#######.#.#.#.#.#.#.###.#.###.#####.#.#.#######.#.#####.#.###.#.#.###.#######H#
+#.#.###.###.#.###.#####.#.#####.#.#.###.#.###.###################.#######.###.#.#
-#......o..#...#...#.......#...#.A.....#.#.........#r......#.....#.....#.........#
+#.#.........#...........#.....#...#.....#...#.....................#...........#.#
 #################################################################################

inputs/19p.txt

@@ -1 +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

@@ -1,125 +0,0 @@
-                                         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

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

inputs/20s2.txt

@@ -1,37 +0,0 @@
-                   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

@@ -1,37 +0,0 @@
-             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

@@ -5,7 +5,6 @@ import (
 	"fmt"
 	"log"
 	"os"
-	"runtime/pprof"
 	"strconv"
 	"strings"
 	"time"
@@ -29,8 +28,6 @@ const (
 var (
 	flagPart1 = flag.Bool("part1", false, "whether to run part1 or not; if no flags are present, all parts are run")
 	flagPart2 = flag.Bool("part2", false, "whether to run part2 or not; if no flags are present, all parts are run")
-	flagCpuProfile = flag.String("cpuprofile", "", "write cpu profile to file")
-	flagMemProfile = flag.String("memprofile", "", "write memory profile to file")
 )
 
 var dayMap = []day{
@@ -52,24 +49,11 @@ var dayMap = []day{
 	&days.Day16{},
 	&days.Day17{},
 	&days.Day18{},
-	&days.Day19{},
-	&days.Day20{},
 }
 
 func main() {
 	flag.Parse()
 
-	if *flagCpuProfile != "" {
-		f, err := os.Create(*flagCpuProfile)
-		if err != nil {
-			log.Fatal(err)
-		}
-		defer f.Close()
-
-		pprof.StartCPUProfile(f)
-		defer pprof.StopCPUProfile()
-	}
-
 	arg := strconv.Itoa(len(dayMap))
 	flagArgs := flag.Args()
 	if len(flagArgs) > 0 && len(flagArgs[0]) > 0 {
@@ -94,14 +78,7 @@ func main() {
 		solve(dayMap[iArg-1])
 	}
 
-	if *flagMemProfile != "" {
+	os.Exit(0)
-		f, err := os.Create(*flagMemProfile)
-		if err != nil {
-			log.Fatal(err)
-		}
-		pprof.WriteHeapProfile(f)
-		f.Close()
-	}
 }
 
 func solve(d day) {
@@ -121,11 +98,6 @@ func solve(d day) {
 		part1Text = d.Part1()
 	}
 	part1Time := time.Since(part1Start)
-	if runPart1 {
-		fmt.Println(part1Header)
-		fmt.Println(">", part1Text)
-		fmt.Println()
-	}
 
 	part2Start := time.Now()
 	var part2Text string
@@ -133,12 +105,17 @@ func solve(d day) {
 		part2Text = d.Part2()
 	}
 	part2Time := time.Since(part2Start)
+
+	if runPart1 {
+		fmt.Println(part1Header)
+		fmt.Println(">", part1Text)
+		fmt.Println()
+	}
 	if runPart2 {
 		fmt.Println(part2Header)
 		fmt.Println(">", part2Text)
 		fmt.Println()
 	}
-
 	fmt.Print(utilities.ColorBrightBlack)
 	fmt.Println("Parsed in", parseTime)
 	if runPart1 {

utilities/array.go

@@ -10,13 +10,3 @@ func ArrayContains[T comparable](array []T, val T) bool {
 
 	return false
 }
-
-func AddToArray[V comparable, T ~[]V](arr *T, val V) bool {
-	for _, v := range *arr {
-		if v == val {
-			return false
-		}
-	}
-	*arr = append(*arr, val)
-	return true
-}

utilities/bisect.go

@@ -1,26 +0,0 @@
-package utilities
-
-import (
-	"math"
-)
-
-// Bisect takes a known-good low and known-bad high value as the bounds
-// to bisect, and a function to test each value for success or failure.
-// If the function succeeds, the value is adjusted toward the maximum,
-// and if the function fails, the value is adjusted toward the minimum.
-// The final value is returned when the difference between the success
-// 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 {
-	for T(math.Abs(float64(high-low))) > threshold {
-		currVal := low + ((high - low) / 2)
-		success := tryFunc(currVal)
-		if success {
-			low = currVal
-		} else {
-			high = currVal
-		}
-	}
-
-	return low
-}

utilities/intcode.go

@@ -128,15 +128,9 @@ func (p *IntcodeProgram) ensureMemoryCapacity(address int) {
 }
 
 func (p *IntcodeProgram) Reset() {
-	wiped := false
-	if len(p.memory) != len(p.program) {
-		wiped = true
 	p.memory = nil
-	}
 	p.init()
-	if !wiped {
 	copy(p.memory, p.program)
-	}
 	p.relativeBase = 0
 }