Day 17 problems fixed

There were two issues here:
1. Searches for a subset would overlap a found area. So if the search string was R,4,R,4 and the string was R,4,R,4,R,4, it would say there were 2 matches in there since it re-used the middle set.
2. It would happily find a subset that was too long. 20 characters is the maximum program length, per the instructions. Huge thanks to the intcode program for having this as a diagnostic message.

Now this can solve both input sets I have access to.

days/17.go

@@ -9,7 +9,6 @@ import (
 
 type camViewCellType int
 type botFacing int
-type day17Grid [][]camViewCellType
 
 const (
 	cellTypeScaffold camViewCellType = iota
@@ -28,9 +27,8 @@ const (
 )
 
 const (
-	dirLeft                 = 1
-	dirRight                = -1
-	maxInstructionSetLength = 20
+	dirLeft  dirType = 1
+	dirRight dirType = -1
 )
 
 var (
@@ -44,38 +42,32 @@ var (
 
 type Day17 struct {
 	program      u.IntcodeProgram
+	grid         [][]camViewCellType
+	botLocation  u.Vec2i
+	botFacingDir botFacing
+	endLocation  u.Vec2i
 }
 
 func (d *Day17) Parse() {
 	d.program = u.LoadIntcodeProgram("17p")
+	d.grid = [][]camViewCellType{{}}
 }
 
 func (d Day17) Num() int {
 	return 17
 }
 
-func (currentDir botFacing) getNewFacingDir(turnDir int) botFacing {
-	currentDir += botFacing(turnDir)
-	if currentDir < botFacingFirst {
-		currentDir = botFacingLast
-	} else if currentDir > botFacingLast {
-		currentDir = botFacingFirst
-	}
-
-	return currentDir
-}
-
-func (grid day17Grid) Draw(botLocation u.Vec2i, botFacingDir botFacing, endLocation u.Vec2i) {
-	for y := range grid {
-		for x := range grid[y] {
-			switch grid[y][x] {
+func (d Day17) Draw() {
+	for y := range d.grid {
+		for x := range d.grid[y] {
+			switch d.grid[y][x] {
 			case cellTypeOpen:
 				fmt.Print(" ")
 			case cellTypeScaffold:
 				char := "█"
 				color := u.ColorBlack
-				if botLocation.X == x && botLocation.Y == y {
-					switch botFacingDir {
+				if d.botLocation.X == x && d.botLocation.Y == y {
+					switch d.botFacingDir {
 					case botFacingUp:
 						char = "^"
 					case botFacingLeft:
@@ -85,7 +77,7 @@ func (grid day17Grid) Draw(botLocation u.Vec2i, botFacingDir botFacing, endLocat
 					case botFacingRight:
 						char = ">"
 					}
-				} else if endLocation.X == x && endLocation.Y == y {
+				} else if d.endLocation.X == x && d.endLocation.Y == y {
 					char = "@"
 				} else {
 					color = u.ColorWhite
@@ -97,17 +89,17 @@ func (grid day17Grid) Draw(botLocation u.Vec2i, botFacingDir botFacing, endLocat
 	}
 }
 
-func (grid day17Grid) getAdjacentScaffolds(y, x int) []u.Vec2i {
+func (d Day17) getAdjacentScaffolds(y, x int) []u.Vec2i {
 	retval := make([]u.Vec2i, 0)
 	for _, offset := range day17AdjacentOffsets {
 		offY := y + offset.Y
 		offX := x + offset.X
-		if offY < 0 || offY >= len(grid) ||
-			offX < 0 || offX >= len(grid[0]) {
+		if offY < 0 || offY >= len(d.grid) ||
+			offX < 0 || offX >= len(d.grid[0]) {
 			continue
 		}
 
-		if grid[offY][offX] == cellTypeScaffold {
+		if d.grid[offY][offX] == cellTypeScaffold {
 			retval = append(retval, u.Vec2i{X: offX, Y: offY})
 		}
 	}
@@ -115,40 +107,32 @@ func (grid day17Grid) getAdjacentScaffolds(y, x int) []u.Vec2i {
 	return retval
 }
 
-func (grid day17Grid) forEachCellOfType(t camViewCellType, f func(y, x int)) {
-	for y := range grid {
-		for x := range grid[y] {
-			if grid[y][x] == t {
+func (d Day17) getNumSurroundingScaffolds(y, x int) int {
+	return len(d.getAdjacentScaffolds(y, x))
+}
+
+func (d Day17) forEachCellOfType(t camViewCellType, f func(y, x int)) {
+	for y := range d.grid {
+		for x := range d.grid[y] {
+			if d.grid[y][x] == t {
 				f(y, x)
 			}
 		}
 	}
 }
 
-func (grid *day17Grid) processGridUpdate(y int, rVal rune, currBotLocation u.Vec2i, currBotFacing botFacing) (int, u.Vec2i, botFacing) {
-	grid.appendValue(rVal, y)
-
-	switch rVal {
-	case '\n':
-		y++
-	case '^', '<', 'v', '>':
-		currBotLocation = u.Vec2i{X: len((*grid)[y]) - 1, Y: y}
-		switch rVal {
-		case '^':
-			currBotFacing = botFacingUp
-		case '<':
-			currBotFacing = botFacingLeft
-		case 'v':
-			currBotFacing = botFacingDown
-		case '>':
-			currBotFacing = botFacingRight
-		}
+func (d Day17) getNewFacingDir(currentDir botFacing, turnDir dirType) botFacing {
+	currentDir += botFacing(turnDir)
+	if currentDir < botFacingFirst {
+		currentDir = botFacingLast
+	} else if currentDir > botFacingLast {
+		currentDir = botFacingFirst
 	}
 
-	return y, currBotLocation, currBotFacing
+	return currentDir
 }
 
-func (grid day17Grid) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCellType, int, int) {
+func (d Day17) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCellType, int, int) {
 	newX := x
 	newY := y
 	switch facingDir {
@@ -162,50 +146,78 @@ func (grid day17Grid) getCellTypeInDirection(y, x int, facingDir botFacing) (cam
 		newX++
 	}
 
-	if newY < 0 || newY >= len(grid) || newX < 0 || newX >= len(grid[0]) {
+	if newY < 0 || newY >= len(d.grid) || newX < 0 || newX >= len(d.grid[0]) {
 		return cellTypeInvalid, newY, newX
 	}
 
-	return grid[newY][newX], newY, newX
-}
-
-func (grid *day17Grid) appendValue(rVal rune, row int) {
-	ensureCapacity := func(y int) {
-		for len(*grid) <= y {
-			*grid = append(*grid, make([]camViewCellType, 0))
-		}
+	return d.grid[newY][newX], newY, newX
 }
 
+func (d *Day17) Part1() string {
+	y := 0
+	d.program.RunIn(func(inputStep int) int64 {
+		return 0
+	}, func(val int64, state u.IntcodeProgramState) {
+		rVal := rune(val)
 		switch rVal {
+		case '\n':
+			y++
+			d.grid = append(d.grid, make([]camViewCellType, 0))
 		case '#':
-		ensureCapacity(row)
-		(*grid)[row] = append((*grid)[row], cellTypeScaffold)
+			d.grid[y] = append(d.grid[y], cellTypeScaffold)
 		case '.':
-		ensureCapacity(row)
-		(*grid)[row] = append((*grid)[row], cellTypeOpen)
+			d.grid[y] = append(d.grid[y], cellTypeOpen)
 		case '^', '<', 'v', '>':
-		ensureCapacity(row)
-		(*grid)[row] = append((*grid)[row], cellTypeScaffold)
-	}
-}
-
-func (grid day17Grid) findEndLocation(botLocation u.Vec2i) u.Vec2i {
-	var endLocation u.Vec2i
-	grid.forEachCellOfType(cellTypeScaffold, func(y, x int) {
-		if numSurrounding := len(grid.getAdjacentScaffolds(y, x)); numSurrounding == 1 {
-			if botLocation.X != x || botLocation.Y != y {
-				endLocation = u.Vec2i{X: x, Y: y}
+			d.botLocation = u.Vec2i{X: len(d.grid[y]), Y: y}
+			d.grid[y] = append(d.grid[y], cellTypeScaffold)
+			switch rVal {
+			case '^':
+				d.botFacingDir = botFacingUp
+			case '<':
+				d.botFacingDir = botFacingLeft
+			case 'v':
+				d.botFacingDir = botFacingDown
+			case '>':
+				d.botFacingDir = botFacingRight
 			}
 		}
 	})
 
-	return endLocation
+	for y := len(d.grid) - 1; y >= 0; y-- {
+		if len(d.grid[y]) == 0 {
+			d.grid = d.grid[0 : len(d.grid)-1]
+		}
 	}
 
-func (grid day17Grid) getTurnDirectionFromCorner(pos u.Vec2i, botFacingDir botFacing) (int, string) {
-	adj := grid.getAdjacentScaffolds(pos.Y, pos.X)
-	turnDirection := 0
-	// this is so awful. i'm sure there's a better way, but i'm tired.
+	alignmentParameterTotal := 0
+	d.forEachCellOfType(cellTypeScaffold, func(y, x int) {
+		if numSurrounding := d.getNumSurroundingScaffolds(y, x); numSurrounding == 4 {
+			alignmentParameterTotal += y * x
+		} else if numSurrounding == 1 {
+			if d.botLocation.X != x || d.botLocation.Y != y {
+				d.endLocation = u.Vec2i{X: x, Y: y}
+			}
+		}
+	})
+
+	// d.Draw()
+
+	return fmt.Sprintf("Alignment parameter sum: %s%d%s", u.TextBold, alignmentParameterTotal, u.TextReset)
+}
+
+func (d *Day17) Part2() string {
+	instructions := make([]string, 0)
+
+	pos := d.botLocation
+	botFacingDir := d.botFacingDir
+	for {
+		if pos == d.endLocation {
+			fmt.Println()
+			break
+		}
+
+		adj := d.getAdjacentScaffolds(pos.Y, pos.X)
+		turnDirection := dirType(0)
 		if botFacingDir == botFacingUp || botFacingDir == botFacingDown {
 			if u.ArrayContains(adj, u.Vec2i{X: pos.X - 1, Y: pos.Y}) {
 				if botFacingDir == botFacingUp {
@@ -236,30 +248,42 @@ func (grid day17Grid) getTurnDirectionFromCorner(pos u.Vec2i, botFacingDir botFa
 			}
 		}
 
+		if turnDirection == 0 {
+			panic("at an invalid location somehow")
+		}
+
 		dirAscii := "L"
 		if turnDirection == dirRight {
 			dirAscii = "R"
 		}
+		instructions = append(instructions, dirAscii)
 
-	return turnDirection, dirAscii
+		botFacingDir = d.getNewFacingDir(botFacingDir, turnDirection)
+		numMoved := 0
+		for {
+			cell, newY, newX := d.getCellTypeInDirection(pos.Y, pos.X, botFacingDir)
+			if cell != cellTypeScaffold {
+				break
+			}
+			pos.X = newX
+			pos.Y = newY
+			numMoved++
+		}
+		instructions = append(instructions, fmt.Sprintf("%d", numMoved))
 	}
 
-func buildInstructionString(instructions []string) string {
 	workingInstructions := make([]string, len(instructions))
 	copy(workingInstructions, instructions)
 
-	minimumRecurrence := 3
-	initialInstructionSubsetLen := 4
-
 	instructionStr := strings.Join(workingInstructions, ",")
 	progs := make([][]string, 3)
-	for i := range progs {
-		numFound := minimumRecurrence
-		subLen := initialInstructionSubsetLen
-		for numFound >= minimumRecurrence {
+	for i := 0; i < 3; i++ {
+		numFound := 3
+		subLen := 4
+		for numFound >= 3 {
 			numFound = 1
 			instructionSubset := strings.Join(workingInstructions[0:subLen], ",")
-			if len(instructionSubset) > maxInstructionSetLength {
+			if len(instructionSubset) > 20 {
 				break
 			}
 			for x := len(instructionSubset); x <= len(instructionStr)-len(instructionSubset); x++ {
@@ -268,11 +292,11 @@ func buildInstructionString(instructions []string) string {
 					x += len(instructionSubset)
 				}
 			}
-			if numFound >= minimumRecurrence {
+			if numFound >= 3 {
 				subLen += 2
 			}
 		}
-		if numFound < minimumRecurrence {
+		if numFound < 3 {
 			subLen -= 2
 		}
 		progs[i] = make([]string, subLen)
@@ -289,134 +313,28 @@ func buildInstructionString(instructions []string) string {
 	}
 
 	if workingInstructions != nil {
-		panic("failed to use up all instructions")
+		panic("didn't empty instructions")
 	}
+	instructionStr = strings.Join(instructions, ",")
+	instructionStr = strings.ReplaceAll(instructionStr, strings.Join(progs[0], ","), "A")
+	instructionStr = strings.ReplaceAll(instructionStr, strings.Join(progs[1], ","), "B")
+	instructionStr = strings.ReplaceAll(instructionStr, strings.Join(progs[2], ","), "C")
 
-	programStr := strings.Join(instructions, ",")
-	for i := range progs {
-		programStr = strings.ReplaceAll(programStr, strings.Join(progs[i], ","), fmt.Sprintf("%c", 'A'+i))
-	}
-
-	sb := strings.Builder{}
-	sb.WriteString(programStr)
-	sb.WriteRune('\n')
-
-	for i := range progs {
-		sb.WriteString(strings.Join(progs[i], ","))
-		sb.WriteRune('\n')
-	}
-
-	runDebug := 'n'
-	sb.WriteRune(runDebug)
-	sb.WriteRune('\n')
-
-	return sb.String()
-}
-
-func (grid day17Grid) solvePath(botLocation u.Vec2i, botFacingDir botFacing) string {
-	instructions := make([]string, 0)
-
-	pos := botLocation
-	endLocation := grid.findEndLocation(botLocation)
-	for {
-		if pos == endLocation {
-			break
-		}
-
-		turnDirection, dirAscii := grid.getTurnDirectionFromCorner(pos, botFacingDir)
-		if turnDirection == 0 {
-			panic("at an invalid location somehow")
-		}
-
-		instructions = append(instructions, dirAscii)
-
-		botFacingDir = botFacingDir.getNewFacingDir(turnDirection)
-		numMoved := 0
-		for {
-			cell, newY, newX := grid.getCellTypeInDirection(pos.Y, pos.X, botFacingDir)
-			if cell != cellTypeScaffold {
-				break
-			}
-			pos.X = newX
-			pos.Y = newY
-			numMoved++
-		}
-		instructions = append(instructions, fmt.Sprintf("%d", numMoved))
-	}
-
-	return buildInstructionString(instructions)
-}
-
-func (d *Day17) Part1() string {
-	grid := day17Grid{}
-	y := 0
-	var botLocation u.Vec2i
-	var botFacingDir botFacing
-
-	d.program.RunIn(func(inputStep int) int64 {
-		return 0
-	}, func(val int64, state u.IntcodeProgramState) {
-		rVal := rune(val)
-		y, botLocation, botFacingDir = grid.processGridUpdate(y, rVal, botLocation, botFacingDir)
-	})
-
-	alignmentParameterTotal := 0
-	grid.forEachCellOfType(cellTypeScaffold, func(y, x int) {
-		if numSurrounding := len(grid.getAdjacentScaffolds(y, x)); numSurrounding == 4 {
-			alignmentParameterTotal += y * x
-		}
-	})
-
-	// endLocation := grid.findEndLocation(botLocation)
-	// grid.Draw(botLocation, botFacingDir, endLocation)
-
-	return fmt.Sprintf("Alignment parameter sum: %s%d%s", u.TextBold, alignmentParameterTotal, u.TextReset)
-}
-
-func (d *Day17) Part2() string {
-	beforeGrid := day17Grid{}
-	var beforeBotLocation u.Vec2i
-	var beforeBotFacing botFacing
-
-	afterGrid := day17Grid{}
-	var afterBotLocation u.Vec2i
-	var afterBotFacing botFacing
+	instructionStr = fmt.Sprintf("%s\n%s\n%s\n%s\nn\n",
+		instructionStr,
+		strings.Join(progs[0], ","),
+		strings.Join(progs[1], ","),
+		strings.Join(progs[2], ","),
+	)
 
 	d.program.Reset()
 	d.program.SetMemory(0, 2)
-
-	row := 0
-	var outputState int
-	var lastOutput int64
-	var instructionStr string
+	dustCollected := int64(0)
 	d.program.RunIn(func(inputStep int) int64 {
 		return int64(instructionStr[inputStep-1])
 	}, func(val int64, state u.IntcodeProgramState) {
-		rVal := rune(val)
-		if outputState == 0 {
-			row, beforeBotLocation, beforeBotFacing = beforeGrid.processGridUpdate(row, rVal, beforeBotLocation, beforeBotFacing)
-		} else if outputState == 2 {
-			row, afterBotLocation, afterBotFacing = afterGrid.processGridUpdate(row, rVal, afterBotLocation, afterBotFacing)
-		}
-
-		if rVal == '\n' && lastOutput == '\n' {
-			if outputState == 0 {
-				instructionStr = beforeGrid.solvePath(beforeBotLocation, beforeBotFacing)
-			}
-			outputState++
-			row = 0
-		}
-
-		lastOutput = val
+		dustCollected = val
 	})
 
-	// fmt.Println("initial grid:")
-	// beforeEndLocation := beforeGrid.findEndLocation(beforeBotLocation)
-	// beforeGrid.Draw(beforeBotLocation, beforeBotFacing, beforeEndLocation)
-
-	// fmt.Println("completed grid:")
-	// afterEndLocation := afterGrid.findEndLocation(afterBotLocation)
-	// afterGrid.Draw(afterBotLocation, afterBotFacing, afterEndLocation)
-
-	return fmt.Sprintf("Dust collected after traveling all paths: %s%d%s", u.TextBold, lastOutput, u.TextReset)
+	return fmt.Sprintf("Dust collected after traveling all paths: %s%d%s", u.TextBold, dustCollected, u.TextReset)
 }

days/18.go

@@ -1,345 +0,0 @@
-package days
-
-import (
-	"container/heap"
-	"fmt"
-	"math"
-	"strings"
-
-	"github.com/edwingeng/deque/v2"
-	u "parnic.com/aoc2019/utilities"
-)
-
-type day18Cell int
-type day18Vec u.Vec2[int]
-type day18Graph map[rune][]u.Pair[rune, int]
-
-const (
-	day18CellWall day18Cell = iota
-	day18CellOpen
-)
-
-var (
-	day18AdjacentOffsets = []day18Vec{
-		{X: -1, Y: 0},
-		{X: 1, Y: 0},
-		{X: 0, Y: -1},
-		{X: 0, Y: 1},
-	}
-)
-
-type Day18 struct {
-	entrance day18Vec
-	grid     [][]day18Cell
-	doors    map[day18Vec]int
-	keys     map[day18Vec]int
-}
-
-func (d *Day18) Parse() {
-	d.doors = make(map[day18Vec]int)
-	d.keys = make(map[day18Vec]int)
-
-	lines := u.GetStringLines("18p")
-	d.grid = make([][]day18Cell, len(lines))
-	for i, line := range lines {
-		d.grid[i] = make([]day18Cell, len(line))
-		for j, char := range line {
-			if char == '#' {
-				d.grid[i][j] = day18CellWall
-			} else if char == '.' {
-				d.grid[i][j] = day18CellOpen
-			} else if char == '@' {
-				d.grid[i][j] = day18CellOpen
-				d.entrance = day18Vec{X: j, Y: i}
-			} else if char >= 'A' && char <= 'Z' {
-				d.grid[i][j] = day18CellOpen
-				d.doors[day18Vec{X: j, Y: i}] = int(char - 'A')
-			} else if char >= 'a' && char <= 'z' {
-				d.grid[i][j] = day18CellOpen
-				d.keys[day18Vec{X: j, Y: i}] = int(char - 'a')
-			}
-		}
-	}
-}
-
-func (d Day18) Num() int {
-	return 18
-}
-
-func (d Day18) Draw(grid [][]day18Cell, keys, doors map[day18Vec]int, entrances ...day18Vec) {
-	for y := range grid {
-		for x := range grid[y] {
-			switch grid[y][x] {
-			case day18CellWall:
-				fmt.Print("█")
-			case day18CellOpen:
-				posVec := day18Vec{X: x, Y: y}
-				if _, exists := doors[posVec]; exists {
-					fmt.Printf("%c", rune(doors[posVec]+'A'))
-				} else if _, exists := keys[posVec]; exists {
-					fmt.Printf("%c", rune(keys[posVec]+'a'))
-				} else if u.ArrayContains(entrances, posVec) {
-					fmt.Print("@")
-				} else {
-					fmt.Print(".")
-				}
-			}
-		}
-		fmt.Println()
-	}
-}
-
-func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, grid [][]day18Cell) []u.Pair[rune, int] {
-	found := make([]u.Pair[rune, int], 0)
-
-	getAdjacent := func(pos day18Vec) []day18Vec {
-		retAdjacent := make([]day18Vec, 0, len(day18AdjacentOffsets))
-		for _, off := range day18AdjacentOffsets {
-			offVec := day18Vec{X: pos.X + off.X, Y: pos.Y + off.Y}
-			if grid[offVec.Y][offVec.X] == day18CellWall {
-				continue
-			}
-			retAdjacent = append(retAdjacent, offVec)
-		}
-
-		return retAdjacent
-	}
-
-	queue := deque.NewDeque[u.Pair[int, day18Vec]]()
-	visited := make(map[day18Vec]bool)
-	for _, adjacent := range getAdjacent(inPos) {
-		queue.PushBack(u.Pair[int, day18Vec]{First: 1, Second: adjacent})
-	}
-
-	for !queue.IsEmpty() {
-		next := queue.PopFront()
-
-		if _, exists := visited[next.Second]; !exists {
-			visited[next.Second] = true
-
-			key, adjacentIsKey := keys[next.Second]
-			door, adjacentIsDoor := doors[next.Second]
-			if adjacentIsKey || adjacentIsDoor {
-				var rVal rune
-				if adjacentIsKey {
-					rVal = rune('a' + key)
-				} else if adjacentIsDoor {
-					rVal = rune('A' + door)
-				}
-
-				alreadyFound := false
-				for _, p := range found {
-					if p.First == rVal {
-						alreadyFound = true
-						break
-					}
-				}
-				if !alreadyFound {
-					found = append(found, u.Pair[rune, int]{First: rVal, Second: next.First})
-					continue
-				}
-			}
-
-			for _, neighbor := range getAdjacent(next.Second) {
-				if _, exists := visited[neighbor]; !exists {
-					queue.PushBack(u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
-				}
-			}
-		}
-	}
-
-	return found
-}
-
-type day18PriorityQueue struct {
-	distance int
-	neighbor rune
-}
-type PriorityQueueHeap []day18PriorityQueue
-
-func (h PriorityQueueHeap) Len() int           { return len(h) }
-func (h PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
-func (h PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
-
-func (h *PriorityQueueHeap) Push(x any) {
-	*h = append(*h, x.(day18PriorityQueue))
-}
-
-func (h *PriorityQueueHeap) Pop() any {
-	old := *h
-	n := len(old)
-	x := old[n-1]
-	*h = old[0 : n-1]
-	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 := knownReachableKeys[memo]; exists {
-		return v
-	}
-
-	ret := make([]u.Pair[rune, int], 0)
-	distance := make(map[rune]int)
-
-	ih := make(PriorityQueueHeap, 0)
-
-	for _, p := range graph[inPos] {
-		ih = append(ih, day18PriorityQueue{
-			distance: p.Second,
-			neighbor: p.First,
-		})
-	}
-
-	heap.Init(&ih)
-
-	for ih.Len() > 0 {
-		node := heap.Pop(&ih).(day18PriorityQueue)
-
-		// it's a key and we haven't picked it up yet...
-		if node.neighbor >= 'a' && node.neighbor <= 'z' && (1<<int(node.neighbor-'a')&keysFound) == 0 {
-			ret = append(ret, u.Pair[rune, int]{First: node.neighbor, Second: node.distance})
-			continue
-		}
-
-		// it's a door but we don't have the key yet...
-		if node.neighbor >= 'A' && node.neighbor <= 'Z' && ((1<<int(node.neighbor-'A'))&keysFound) == 0 {
-			continue
-		}
-
-		for _, p := range graph[node.neighbor] {
-			newDistance := node.distance + p.Second
-			if dist, exists := distance[p.First]; !exists || newDistance < dist {
-				distance[p.First] = newDistance
-				heap.Push(&ih, day18PriorityQueue{
-					distance: newDistance,
-					neighbor: p.First,
-				})
-			}
-		}
-	}
-
-	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 := knownMinimumSteps[memo]; exists {
-		return v
-	}
-
-	if keysToFind == 0 {
-		return 0
-	}
-
-	best := math.Inf(1)
-	for _, item := range inPos {
-		for _, p := range d.reachableKeys(item, keysFound, graph) {
-			sb := strings.Builder{}
-			oldIdx := strings.IndexRune(inPos, item)
-			for i := range inPos {
-				if i == oldIdx {
-					sb.WriteRune(p.First)
-				} else {
-					sb.WriteByte(inPos[i])
-				}
-			}
-			newKeys := keysFound + (1 << (p.First - 'a'))
-			dist := p.Second
-
-			dist += d.minimumSteps(sb.String(), keysToFind-1, newKeys, graph)
-
-			if float64(dist) < best {
-				best = float64(dist)
-			}
-		}
-	}
-
-	knownMinimumSteps[memo] = int(best)
-	return int(best)
-}
-
-func (d Day18) buildGraph(pos []day18Vec, keys map[day18Vec]int, doors map[day18Vec]int, grid [][]day18Cell) day18Graph {
-	graph := make(day18Graph)
-	for i, p := range pos {
-		adjacent := d.findAdjacentCells(p, keys, doors, grid)
-		graph[rune('1'+i)] = adjacent
-	}
-	for keyPos, keyType := range keys {
-		graph[rune('a'+keyType)] = d.findAdjacentCells(keyPos, keys, doors, grid)
-	}
-	for doorPos, doorType := range doors {
-		graph[rune('A'+doorType)] = d.findAdjacentCells(doorPos, keys, doors, grid)
-	}
-
-	return graph
-}
-
-func (d Day18) part2PatchMap(grid [][]day18Cell, entrance day18Vec) []day18Vec {
-	grid[entrance.Y-1][entrance.X] = day18CellWall
-	grid[entrance.Y][entrance.X-1] = day18CellWall
-	grid[entrance.Y][entrance.X] = day18CellWall
-	grid[entrance.Y][entrance.X+1] = day18CellWall
-	grid[entrance.Y+1][entrance.X] = day18CellWall
-
-	return []day18Vec{
-		{X: entrance.X - 1, Y: entrance.Y - 1},
-		{X: entrance.X + 1, Y: entrance.Y - 1},
-		{X: entrance.X - 1, Y: entrance.Y + 1},
-		{X: entrance.X + 1, Y: entrance.Y + 1},
-	}
-}
-
-func (d *Day18) Part1() string {
-	// fmt.Println("initial state:")
-	// d.Draw(d.grid, d.keys, d.doors, d.entrance)
-
-	graph := d.buildGraph([]day18Vec{d.entrance}, d.keys, d.doors, d.grid)
-	minSteps := d.minimumSteps("1", len(d.keys), 0, graph)
-
-	return fmt.Sprintf("Total distance traveled: %s%d%s", u.TextBold, minSteps, u.TextReset)
-}
-
-func (d *Day18) Part2() string {
-	// fmt.Println("initial state:")
-	grid := make([][]day18Cell, len(d.grid))
-	for i := range d.grid {
-		grid[i] = make([]day18Cell, len(d.grid[i]))
-		copy(grid[i], d.grid[i])
-	}
-
-	entrances := d.part2PatchMap(grid, d.entrance)
-	// d.Draw(grid, d.keys, d.doors, entrances...)
-
-	// clear memoized maps that (might have) came from part1
-	knownMinimumSteps = make(map[minStepsMemo]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)
-
-	return fmt.Sprintf("Total distance traveled: %s%d%s", u.TextBold, minSteps, 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/18p.txt

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

inputs/18s1.txt

@@ -1,3 +0,0 @@
-#########
-#b.A.@.a#
-#########

inputs/18s2.txt

@@ -1,5 +0,0 @@
-########################
-#f.D.E.e.C.b.A.@.a.B.c.#
-######################.#
-#d.....................#
-########################

inputs/18s3.txt

@@ -1,5 +0,0 @@
-########################
-#...............b.C.D.f#
-#.######################
-#.....@.a.B.c.d.A.e.F.g#
-########################

inputs/18s4.txt

@@ -1,9 +0,0 @@
-#################
-#i.G..c...e..H.p#
-########.########
-#j.A..b...f..D.o#
-########@########
-#k.E..a...g..B.n#
-########.########
-#l.F..d...h..C.m#
-#################

inputs/18s5.txt

@@ -1,6 +0,0 @@
-########################
-#@..............ac.GI.b#
-###d#e#f################
-###A#B#C################
-###g#h#i################
-########################

inputs/18s6.txt

@@ -1,7 +0,0 @@
-#######
-#a.#Cd#
-##...##
-##.@.##
-##...##
-#cB#Ab#
-#######

inputs/18s7.txt

@@ -1,7 +0,0 @@
-###############
-#d.ABC.#.....a#
-######...######
-######.@.######
-######...######
-#b.....#.....c#
-###############

inputs/18s8.txt

@@ -1,7 +0,0 @@
-#############
-#DcBa.#.GhKl#
-#.###...#I###
-#e#d#.@.#j#k#
-###C#...###J#
-#fEbA.#.FgHi#
-#############

inputs/18s9.txt

@@ -1,9 +0,0 @@
-#############
-#g#f.D#..h#l#
-#F###e#E###.#
-#dCba...BcIJ#
-#####.@.#####
-#nK.L...G...#
-#M###N#H###.#
-#o#m..#i#jk.#
-#############

main.go

@@ -48,7 +48,6 @@ var dayMap = []day{
 	&days.Day15{},
 	&days.Day16{},
 	&days.Day17{},
-	&days.Day18{},
 }
 
 func main() {

utilities/map.go

@@ -15,13 +15,3 @@ func MapValues[T comparable, U any](m map[T]U) []U {
 	}
 	return r
 }
-
-// CopyMap returns a copy of the passed-in map. Note: currently only works if [U]
-// is not a map or slice.
-func CopyMap[T comparable, U any](m map[T]U) map[T]U {
-	r := make(map[T]U)
-	for k, v := range m {
-		r[k] = v
-	}
-	return r
-}

utilities/vector.go

@@ -44,16 +44,11 @@ func (v Vec2[T]) Equals(other Vec2[T]) bool {
 		v.Y == other.Y
 }
 
-func (v Vec2[T]) ManhattanDistance(other Vec2[T]) T {
-	return T(math.Abs(float64(v.X-other.X)) + math.Abs(float64(v.Y-other.Y)))
-}
-
 func VecBetween[T Number](a, b Vec2[T]) Vec2[T] {
-	return a.To(b)
+	return Vec2[T]{
+		X: a.X - b.X,
+		Y: a.Y - b.Y,
 	}
-
-func ManhattanDistance[T Number](a, b Vec2[T]) T {
-	return a.ManhattanDistance(b)
 }
 
 func (v Vec3[T]) Dot(other Vec3[T]) T {