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/18.go

@@ -28,16 +28,31 @@ var (
 	}
 )
 
+type reachableKeysMemo struct {
+	pos       rune
+	keysFound int
+}
+
+type minStepsMemo struct {
+	pos        string
+	keysToFind int
+	keysFound  int
+}
+
 type Day18 struct {
-	entrance day18Vec
+	entrance           day18Vec
-	grid     [][]day18Cell
+	grid               [][]day18Cell
-	doors    map[day18Vec]int
+	doors              map[day18Vec]int
-	keys     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))
@@ -155,17 +170,17 @@ type day18PriorityQueue struct {
 	distance int
 	neighbor rune
 }
-type PriorityQueueHeap []day18PriorityQueue
+type day18PriorityQueueHeap []day18PriorityQueue
 
-func (h PriorityQueueHeap) Len() int           { return len(h) }
+func (h day18PriorityQueueHeap) Len() int           { return len(h) }
-func (h PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
+func (h day18PriorityQueueHeap) 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 day18PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
-func (h *PriorityQueueHeap) Push(x any) {
+func (h *day18PriorityQueueHeap) Push(x any) {
 	*h = append(*h, x.(day18PriorityQueue))
 }
 
-func (h *PriorityQueueHeap) Pop() any {
+func (h *day18PriorityQueueHeap) Pop() any {
 	old := *h
 	n := len(old)
 	x := old[n-1]
@@ -173,26 +188,19 @@ func (h *PriorityQueueHeap) 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 := knownReachableKeys[memo]; exists {
+	if v, exists := d.knownReachableKeys[memo]; exists {
 		return v
 	}
 
 	ret := make([]u.Pair[rune, int], 0)
 	distance := make(map[rune]int)
 
-	ih := make(PriorityQueueHeap, 0)
+	ih := make(day18PriorityQueueHeap, 0)
 
 	for _, p := range graph[inPos] {
 		ih = append(ih, day18PriorityQueue{
@@ -229,25 +237,17 @@ func (d Day18) reachableKeys(inPos rune, keysFound int, graph day18Graph) []u.Pa
 		}
 	}
 
-	knownReachableKeys[memo] = ret
+	d.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 {
+	if v, exists := d.knownMinimumSteps[memo]; exists {
 		return v
 	}
 
@@ -278,7 +278,7 @@ func (d Day18) minimumSteps(inPos string, keysToFind int, keysFound int, graph d
 		}
 	}
 
-	knownMinimumSteps[memo] = int(best)
+	d.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
-	knownMinimumSteps = make(map[minStepsMemo]int)
+	d.knownMinimumSteps = make(map[minStepsMemo]int)
-	knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, 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)

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)
+}

inputs/18p.txt

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

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{
@@ -49,11 +52,23 @@ var dayMap = []day{
 	&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 {
@@ -78,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) {
@@ -98,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
@@ -105,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
 }