Merge branch 'develop' into dev/19

This reverts commit 5247ae9d72, reversing
changes made to 9947a9b559.

.gitignore

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

days/14.go

@@ -104,26 +104,10 @@ 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 {
-	high := estimate * 2
+		oreConsumed := d.getOreRequiredForFuel(val)
-	low := estimate
+		return oreConsumed < oreAvailable
-
+	})
-	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/17.go

@@ -9,6 +9,7 @@ import (
 
 type camViewCellType int
 type botFacing int
+type day17Grid [][]camViewCellType
 
 const (
 	cellTypeScaffold camViewCellType = iota
@@ -27,8 +28,9 @@ const (
 )
 
 const (
-	dirLeft  dirType = 1
+	dirLeft                 = 1
-	dirRight dirType = -1
+	dirRight                = -1
+	maxInstructionSetLength = 20
 )
 
 var (
@@ -41,33 +43,39 @@ var (
 )
 
 type Day17 struct {
-	program      u.IntcodeProgram
+	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 (d Day17) Draw() {
+func (currentDir botFacing) getNewFacingDir(turnDir int) botFacing {
-	for y := range d.grid {
+	currentDir += botFacing(turnDir)
-		for x := range d.grid[y] {
+	if currentDir < botFacingFirst {
-			switch d.grid[y][x] {
+		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] {
 			case cellTypeOpen:
 				fmt.Print(" ")
 			case cellTypeScaffold:
 				char := "█"
 				color := u.ColorBlack
-				if d.botLocation.X == x && d.botLocation.Y == y {
+				if botLocation.X == x && botLocation.Y == y {
-					switch d.botFacingDir {
+					switch botFacingDir {
 					case botFacingUp:
 						char = "^"
 					case botFacingLeft:
@@ -77,7 +85,7 @@ func (d Day17) Draw() {
 					case botFacingRight:
 						char = ">"
 					}
-				} else if d.endLocation.X == x && d.endLocation.Y == y {
+				} else if endLocation.X == x && endLocation.Y == y {
 					char = "@"
 				} else {
 					color = u.ColorWhite
@@ -89,17 +97,17 @@ func (d Day17) Draw() {
 	}
 }
 
-func (d Day17) getAdjacentScaffolds(y, x int) []u.Vec2i {
+func (grid day17Grid) 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(d.grid) ||
+		if offY < 0 || offY >= len(grid) ||
-			offX < 0 || offX >= len(d.grid[0]) {
+			offX < 0 || offX >= len(grid[0]) {
 			continue
 		}
 
-		if d.grid[offY][offX] == cellTypeScaffold {
+		if grid[offY][offX] == cellTypeScaffold {
 			retval = append(retval, u.Vec2i{X: offX, Y: offY})
 		}
 	}
@@ -107,32 +115,40 @@ func (d Day17) getAdjacentScaffolds(y, x int) []u.Vec2i {
 	return retval
 }
 
-func (d Day17) getNumSurroundingScaffolds(y, x int) int {
+func (grid day17Grid) forEachCellOfType(t camViewCellType, f func(y, x int)) {
-	return len(d.getAdjacentScaffolds(y, x))
+	for y := range grid {
-}
+		for x := range grid[y] {
-
+			if grid[y][x] == t {
-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 (d Day17) getNewFacingDir(currentDir botFacing, turnDir dirType) botFacing {
+func (grid *day17Grid) processGridUpdate(y int, rVal rune, currBotLocation u.Vec2i, currBotFacing botFacing) (int, u.Vec2i, botFacing) {
-	currentDir += botFacing(turnDir)
+	grid.appendValue(rVal, y)
-	if currentDir < botFacingFirst {
+
-		currentDir = botFacingLast
+	switch rVal {
-	} else if currentDir > botFacingLast {
+	case '\n':
-		currentDir = botFacingFirst
+		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
+		}
 	}
 
-	return currentDir
+	return y, currBotLocation, currBotFacing
 }
 
-func (d Day17) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCellType, int, int) {
+func (grid day17Grid) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCellType, int, int) {
 	newX := x
 	newY := y
 	switch facingDir {
@@ -146,144 +162,104 @@ func (d Day17) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCel
 		newX++
 	}
 
-	if newY < 0 || newY >= len(d.grid) || newX < 0 || newX >= len(d.grid[0]) {
+	if newY < 0 || newY >= len(grid) || newX < 0 || newX >= len(grid[0]) {
 		return cellTypeInvalid, newY, newX
 	}
 
-	return d.grid[newY][newX], newY, newX
+	return grid[newY][newX], newY, newX
 }
 
-func (d *Day17) Part1() string {
+func (grid *day17Grid) appendValue(rVal rune, row int) {
-	y := 0
+	ensureCapacity := func(y int) {
-	d.program.RunIn(func(inputStep int) int64 {
+		for len(*grid) <= y {
-		return 0
+			*grid = append(*grid, make([]camViewCellType, 0))
-	}, func(val int64, state u.IntcodeProgramState) {
+		}
-		rVal := rune(val)
+	}
-		switch rVal {
+
-		case '\n':
+	switch rVal {
-			y++
+	case '#':
-			d.grid = append(d.grid, make([]camViewCellType, 0))
+		ensureCapacity(row)
-		case '#':
+		(*grid)[row] = append((*grid)[row], cellTypeScaffold)
-			d.grid[y] = append(d.grid[y], cellTypeScaffold)
+	case '.':
-		case '.':
+		ensureCapacity(row)
-			d.grid[y] = append(d.grid[y], cellTypeOpen)
+		(*grid)[row] = append((*grid)[row], cellTypeOpen)
-		case '^', '<', 'v', '>':
+	case '^', '<', 'v', '>':
-			d.botLocation = u.Vec2i{X: len(d.grid[y]), Y: y}
+		ensureCapacity(row)
-			d.grid[y] = append(d.grid[y], cellTypeScaffold)
+		(*grid)[row] = append((*grid)[row], cellTypeScaffold)
-			switch rVal {
+	}
-			case '^':
+}
-				d.botFacingDir = botFacingUp
+
-			case '<':
+func (grid day17Grid) findEndLocation(botLocation u.Vec2i) u.Vec2i {
-				d.botFacingDir = botFacingLeft
+	var endLocation u.Vec2i
-			case 'v':
+	grid.forEachCellOfType(cellTypeScaffold, func(y, x int) {
-				d.botFacingDir = botFacingDown
+		if numSurrounding := len(grid.getAdjacentScaffolds(y, x)); numSurrounding == 1 {
-			case '>':
+			if botLocation.X != x || botLocation.Y != y {
-				d.botFacingDir = botFacingRight
+				endLocation = u.Vec2i{X: x, Y: y}
 			}
 		}
 	})
 
-	for y := len(d.grid) - 1; y >= 0; y-- {
+	return endLocation
-		if len(d.grid[y]) == 0 {
-			d.grid = d.grid[0 : len(d.grid)-1]
-		}
-	}
-
-	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 {
+func (grid day17Grid) getTurnDirectionFromCorner(pos u.Vec2i, botFacingDir botFacing) (int, string) {
-	instructions := make([]string, 0)
+	adj := grid.getAdjacentScaffolds(pos.Y, pos.X)
-
+	turnDirection := 0
-	pos := d.botLocation
+	// this is so awful. i'm sure there's a better way, but i'm tired.
-	botFacingDir := d.botFacingDir
+	if botFacingDir == botFacingUp || botFacingDir == botFacingDown {
-	for {
+		if u.ArrayContains(adj, u.Vec2i{X: pos.X - 1, Y: pos.Y}) {
-		if pos == d.endLocation {
+			if botFacingDir == botFacingUp {
-			fmt.Println()
+				turnDirection = dirLeft
-			break
+			} else if botFacingDir == botFacingDown {
-		}
+				turnDirection = dirRight
-
-		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 {
-					turnDirection = dirLeft
-				} else if botFacingDir == botFacingDown {
-					turnDirection = dirRight
-				}
-			} else if u.ArrayContains(adj, u.Vec2i{X: pos.X + 1, Y: pos.Y}) {
-				if botFacingDir == botFacingUp {
-					turnDirection = dirRight
-				} else if botFacingDir == botFacingDown {
-					turnDirection = dirLeft
-				}
 			}
-		} else {
+		} else if u.ArrayContains(adj, u.Vec2i{X: pos.X + 1, Y: pos.Y}) {
-			if u.ArrayContains(adj, u.Vec2i{X: pos.X, Y: pos.Y - 1}) {
+			if botFacingDir == botFacingUp {
-				if botFacingDir == botFacingLeft {
+				turnDirection = dirRight
-					turnDirection = dirRight
+			} else if botFacingDir == botFacingDown {
-				} else if botFacingDir == botFacingRight {
+				turnDirection = dirLeft
-					turnDirection = dirLeft
-				}
-			} else if u.ArrayContains(adj, u.Vec2i{X: pos.X, Y: pos.Y + 1}) {
-				if botFacingDir == botFacingLeft {
-					turnDirection = dirLeft
-				} else if botFacingDir == botFacingRight {
-					turnDirection = dirRight
-				}
 			}
 		}
-
+	} else {
-		if turnDirection == 0 {
+		if u.ArrayContains(adj, u.Vec2i{X: pos.X, Y: pos.Y - 1}) {
-			panic("at an invalid location somehow")
+			if botFacingDir == botFacingLeft {
-		}
+				turnDirection = dirRight
-
+			} else if botFacingDir == botFacingRight {
-		dirAscii := "L"
+				turnDirection = dirLeft
-		if turnDirection == dirRight {
+			}
-			dirAscii = "R"
+		} else if u.ArrayContains(adj, u.Vec2i{X: pos.X, Y: pos.Y + 1}) {
-		}
+			if botFacingDir == botFacingLeft {
-		instructions = append(instructions, dirAscii)
+				turnDirection = dirLeft
-
+			} else if botFacingDir == botFacingRight {
-		botFacingDir = d.getNewFacingDir(botFacingDir, turnDirection)
+				turnDirection = dirRight
-		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))
 	}
 
+	dirAscii := "L"
+	if turnDirection == dirRight {
+		dirAscii = "R"
+	}
+
+	return turnDirection, dirAscii
+}
+
+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 := 0; i < 3; i++ {
+	for i := range progs {
-		numFound := 3
+		numFound := minimumRecurrence
-		subLen := 4
+		subLen := initialInstructionSubsetLen
-		for numFound >= 3 {
+		for numFound >= minimumRecurrence {
 			numFound = 1
 			instructionSubset := strings.Join(workingInstructions[0:subLen], ",")
-			if len(instructionSubset) > 20 {
+			if len(instructionSubset) > maxInstructionSetLength {
 				break
 			}
 			for x := len(instructionSubset); x <= len(instructionStr)-len(instructionSubset); x++ {
@@ -292,11 +268,11 @@ func (d *Day17) Part2() string {
 					x += len(instructionSubset)
 				}
 			}
-			if numFound >= 3 {
+			if numFound >= minimumRecurrence {
 				subLen += 2
 			}
 		}
-		if numFound < 3 {
+		if numFound < minimumRecurrence {
 			subLen -= 2
 		}
 		progs[i] = make([]string, subLen)
@@ -313,28 +289,134 @@ func (d *Day17) Part2() string {
 	}
 
 	if workingInstructions != nil {
-		panic("didn't empty instructions")
+		panic("failed to use up all 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")
 
-	instructionStr = fmt.Sprintf("%s\n%s\n%s\n%s\nn\n",
+	programStr := strings.Join(instructions, ",")
-		instructionStr,
+	for i := range progs {
-		strings.Join(progs[0], ","),
+		programStr = strings.ReplaceAll(programStr, strings.Join(progs[i], ","), fmt.Sprintf("%c", 'A'+i))
-		strings.Join(progs[1], ","),
+	}
-		strings.Join(progs[2], ","),
+
-	)
+	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
 
 	d.program.Reset()
 	d.program.SetMemory(0, 2)
-	dustCollected := int64(0)
+
+	row := 0
+	var outputState int
+	var lastOutput int64
+	var instructionStr string
 	d.program.RunIn(func(inputStep int) int64 {
 		return int64(instructionStr[inputStep-1])
 	}, func(val int64, state u.IntcodeProgramState) {
-		dustCollected = val
+		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
 	})
 
-	return fmt.Sprintf("Dust collected after traveling all paths: %s%d%s", u.TextBold, dustCollected, u.TextReset)
+	// 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)
 }

days/18.go

@@ -0,0 +1,345 @@
+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 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))
+	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 day18PriorityQueueHeap []day18PriorityQueue
+
+func (h day18PriorityQueueHeap) Len() int           { return len(h) }
+func (h day18PriorityQueueHeap) 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 *day18PriorityQueueHeap) Push(x any) {
+	*h = append(*h, x.(day18PriorityQueue))
+}
+
+func (h *day18PriorityQueueHeap) Pop() any {
+	old := *h
+	n := len(old)
+	x := old[n-1]
+	*h = old[0 : n-1]
+	return x
+}
+
+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 {
+		return v
+	}
+
+	ret := make([]u.Pair[rune, int], 0)
+	distance := make(map[rune]int)
+
+	ih := make(day18PriorityQueueHeap, 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,
+				})
+			}
+		}
+	}
+
+	d.knownReachableKeys[memo] = ret
+	return ret
+}
+
+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 {
+		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)
+			}
+		}
+	}
+
+	d.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
+	d.knownMinimumSteps = make(map[minStepsMemo]int)
+	d.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)
+}

days/19.go

@@ -0,0 +1,122 @@
+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
+	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
+	y := u.Bisect(startY+100, 9999, threshold, func(y int) bool {
+		foundX := false
+		for x := startX; ; x++ {
+			if !f(x, y) {
+				if !foundX {
+					continue
+				} else {
+					return true
+				}
+			}
+			if !foundX {
+				foundX = true
+			}
+
+			if !f(x+99, y) {
+				return true
+			}
+			if !f(x, y+99) {
+				continue
+			}
+
+			lastGoodX = x
+			return false
+		}
+	})
+
+	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)
+}

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

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

inputs/18s1.txt

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

inputs/18s2.txt

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

inputs/18s3.txt

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

inputs/18s4.txt

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

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

inputs/18s6.txt

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

inputs/18s7.txt

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

inputs/18s8.txt

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

inputs/18s9.txt

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

inputs/19p.txt

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

main.go

@@ -5,6 +5,7 @@ import (
 	"fmt"
 	"log"
 	"os"
+	"runtime/pprof"
 	"strconv"
 	"strings"
 	"time"
@@ -26,8 +27,10 @@ const (
 )
 
 var (
-	flagPart1 = flag.Bool("part1", false, "whether to run part1 or not; if no flags are present, all parts are run")
+	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")
+	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{
@@ -48,11 +51,24 @@ var dayMap = []day{
 	&days.Day15{},
 	&days.Day16{},
 	&days.Day17{},
+	&days.Day18{},
+	&days.Day19{},
 }
 
 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 {
@@ -77,7 +93,14 @@ func main() {
 		solve(dayMap[iArg-1])
 	}
 
-	os.Exit(0)
+	if *flagMemProfile != "" {
+		f, err := os.Create(*flagMemProfile)
+		if err != nil {
+			log.Fatal(err)
+		}
+		pprof.WriteHeapProfile(f)
+		f.Close()
+	}
 }
 
 func solve(d day) {
@@ -97,6 +120,11 @@ 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
@@ -104,17 +132,12 @@ 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,3 +10,13 @@ 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

@@ -0,0 +1,28 @@
+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 {
+	currVal := low
+
+	for T(math.Abs(float64(high-low))) > threshold {
+		currVal = low + ((high - low) / 2)
+		success := tryFunc(currVal)
+		if success {
+			low = currVal
+		} else {
+			high = currVal
+		}
+	}
+
+	return currVal
+}

utilities/intcode.go

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

utilities/map.go

@@ -15,3 +15,13 @@ 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,11 +44,16 @@ 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 Vec2[T]{
+	return a.To(b)
-		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 {