Merge branch 'develop' into dev/19

Revert "Merge branch 'develop' into dev/19"
This reverts commit 5247ae9d72, reversing changes made to 9947a9b559.
2022-06-21 01:18:12 -05:00 · 2022-06-21 01:18:05 -05:00 · 2022-06-21 01:17:33 -05:00 · 2022-06-21 01:17:31 -05:00 · 2022-06-21 01:16:42 -05:00 · 2022-06-21 00:22:40 -05:00
36 changed files with 1261 additions and 43 deletions
--- a/.gitignore
+++ b/.gitignore
@ -2,3 +2,4 @@
 __debug_bin
 aoc2019
 debug.test
+*.*prof
--- a/days/05.go
+++ b/days/05.go
@ -169,7 +169,7 @@ func (d *Day05) Part1() string {
 		}
 	})

-	return fmt.Sprintf("Diagnostic code: %d", diagCode)
+	return fmt.Sprintf("Diagnostic code: %s%d%s", utilities.TextBold, diagCode, utilities.TextReset)
 }

 func (d *Day05) Part2() string {
@ -184,5 +184,5 @@ func (d *Day05) Part2() string {
 		diagCode = val
 	})

-	return fmt.Sprintf("Diagnostic code: %d", diagCode)
+	return fmt.Sprintf("Diagnostic code: %s%d%s", utilities.TextBold, diagCode, utilities.TextReset)
 }
--- a/days/08.go
+++ b/days/08.go
@ -84,7 +84,8 @@ func (d *Day08) Part2() string {
 	}

 	outStr := strings.Builder{}
-	outStr.WriteRune('\n')
+	outStr.WriteString("Message received:\n")
+	outStr.WriteString(utilities.TextBold)
 	for y := 0; y < imgHeight; y++ {
 		for x := 0; x < imgWidth; x++ {
 			if finalImg[(y*imgWidth)+x] == 0 {
@ -95,6 +96,7 @@ func (d *Day08) Part2() string {
 		}
 		outStr.WriteRune('\n')
 	}
+	outStr.WriteString(utilities.TextReset)

 	return outStr.String()
 }
--- a/days/11.go
+++ b/days/11.go
@ -99,7 +99,8 @@ func (d *Day11) Part2() string {
 	_, min, max := d.paintHull()

 	outStr := strings.Builder{}
-	outStr.WriteRune('\n')
+	outStr.WriteString("Registration identifier:\n")
+	outStr.WriteString(u.TextBold)
 	for x := min.First; x <= max.First; x++ {
 		for y := min.Second; y <= max.Second; y++ {
 			val, exists := d.painted[u.Pair[int, int]{First: x, Second: y}]
@ -111,6 +112,7 @@ func (d *Day11) Part2() string {
 		}
 		outStr.WriteRune('\n')
 	}
+	outStr.WriteString(u.TextReset)

 	return outStr.String()
 }
--- a/days/14.go
+++ b/days/14.go
@ -98,32 +98,16 @@ func (d *Day14) getOreRequiredForFuel(qty int64) int64 {

 func (d *Day14) Part1() string {
 	neededOre := d.getOreRequiredForFuel(1)
-	return fmt.Sprintf("%s%d%s", u.TextBold, neededOre, u.TextReset)
+	return fmt.Sprintf("Minimum ore to produce 1 FUEL: %s%d%s", u.TextBold, neededOre, u.TextReset)
 }

 func (d *Day14) Part2() string {
 	oreAvailable := int64(1000000000000)
 	estimate := oreAvailable / d.getOreRequiredForFuel(1)
+	lastSuccess := u.Bisect(estimate, estimate*2, 1, func(val int64) bool {
+		oreConsumed := d.getOreRequiredForFuel(val)
+		return oreConsumed < oreAvailable
+	})

-	high := estimate * 2
-	low := estimate
-
-	lastSuccess := low
-	lastFailure := high
-	fuelProduced := low
-
-	for math.Abs(float64(lastFailure-lastSuccess)) > 1 {
-		oreConsumed := d.getOreRequiredForFuel(fuelProduced)
-		adjustment := (lastFailure - lastSuccess) / 2
-		if oreConsumed < oreAvailable {
-			lastSuccess = fuelProduced
-		} else {
-			lastFailure = fuelProduced
-			adjustment = -adjustment
-		}
-
-		fuelProduced += adjustment
-	}
-
-	return fmt.Sprintf("%s%d%s", u.TextBold, lastSuccess, u.TextReset)
+	return fmt.Sprintf("Maximum fuel we can make from 1 trillion ore: %s%d%s", u.TextBold, lastSuccess, u.TextReset)
 }
--- a/days/15.go
+++ b/days/15.go
@ -328,5 +328,5 @@ func (d *Day15) Part2() string {
 	cellDistances := u.MapValues(distanceMap)
 	sort.Slice(cellDistances, func(i, j int) bool { return cellDistances[i] > cellDistances[j] })

-	return fmt.Sprintf("%s%d%s", u.TextBold, cellDistances[0], u.TextReset)
+	return fmt.Sprintf("Time to fill the area with oxygen: %s%d%s minutes", u.TextBold, cellDistances[0], u.TextReset)
 }
--- a/days/16.go
+++ b/days/16.go
@ -0,0 +1,104 @@
+package days
+
+import (
+	"fmt"
+	"math"
+
+	u "parnic.com/aoc2019/utilities"
+)
+
+type Day16 struct {
+	numberSet []int8
+}
+
+func (d *Day16) Parse() {
+	numberSequence := u.GetStringContents("16p")
+	d.numberSet = make([]int8, len(numberSequence))
+	for i, numRune := range numberSequence {
+		d.numberSet[i] = int8(numRune - '0')
+	}
+}
+
+func (d Day16) Num() int {
+	return 16
+}
+
+func (d *Day16) Part1() string {
+	transformed := make([]int8, len(d.numberSet))
+	copy(transformed, d.numberSet)
+
+	transformPattern := []int8{0, 1, 0, -1}
+
+	phases := 100
+	workingSet := make([]int8, len(transformed))
+	for i := 0; i < phases; i++ {
+		copy(workingSet, transformed)
+
+		// fmt.Printf("Phase %d. Input signal: %v\n", (i + 1), transformed)
+		for destIdx := range transformed {
+			repeated := 0
+			patternIdx := 0
+			workingVal := int64(0)
+			for idx := range transformed {
+				if repeated >= destIdx {
+					repeated = 0
+					patternIdx++
+					if patternIdx == len(transformPattern) {
+						patternIdx = 0
+					}
+				} else {
+					repeated++
+				}
+
+				// fmt.Printf("%d*%d", transformed[idx], transformPattern[patternIdx])
+				// if idx < len(transformed)-1 {
+				// 	fmt.Print(" + ")
+				// }
+				workingVal += int64(transformed[idx] * transformPattern[patternIdx])
+			}
+
+			workingSet[destIdx] = int8(int64(math.Abs(float64(workingVal))) % 10)
+			// fmt.Printf(" = %d\n", workingSet[destIdx])
+		}
+
+		copy(transformed, workingSet)
+	}
+
+	finalVal := 0
+	for i := range transformed[0:8] {
+		finalVal += int(transformed[i]) * int(math.Pow10(8-1-i))
+	}
+	return fmt.Sprintf("First 8 digits of the final output list: %s%d%s", u.TextBold, finalVal, u.TextReset)
+}
+
+func (d *Day16) Part2() string {
+	transformed := make([]int8, len(d.numberSet)*10000)
+	for i := 0; i < 10000; i++ {
+		copy(transformed[i*len(d.numberSet):(i*len(d.numberSet))+len(d.numberSet)], d.numberSet)
+	}
+
+	finalMsgOffset := 0
+	for i := 0; i < 7; i++ {
+		finalMsgOffset += int(d.numberSet[i]) * int(math.Pow10(7-1-i))
+	}
+
+	if finalMsgOffset < len(transformed)/2 {
+		panic("offset must be in the back half of the message for this solution to work")
+	}
+
+	phases := 100
+	for p := 0; p < phases; p++ {
+		rollingTotal := int8(0)
+		for i := len(transformed) - 1; i >= finalMsgOffset; i-- {
+			rollingTotal += transformed[i]
+			rollingTotal = rollingTotal % 10
+			transformed[i] = rollingTotal
+		}
+	}
+
+	finalVal := 0
+	for i := range transformed[finalMsgOffset : finalMsgOffset+8] {
+		finalVal += int(transformed[finalMsgOffset+i]) * int(math.Pow10(8-1-i))
+	}
+	return fmt.Sprintf("Embedded message in the final output list: %s%d%s", u.TextBold, finalVal, u.TextReset)
+}
--- a/days/17.go
+++ b/days/17.go
@ -0,0 +1,422 @@
+package days
+
+import (
+	"fmt"
+	"strings"
+
+	u "parnic.com/aoc2019/utilities"
+)
+
+type camViewCellType int
+type botFacing int
+type day17Grid [][]camViewCellType
+
+const (
+	cellTypeScaffold camViewCellType = iota
+	cellTypeOpen
+	cellTypeInvalid
+)
+
+const (
+	botFacingUp botFacing = iota
+	botFacingLeft
+	botFacingDown
+	botFacingRight
+
+	botFacingFirst = botFacingUp
+	botFacingLast  = botFacingRight
+)
+
+const (
+	dirLeft                 = 1
+	dirRight                = -1
+	maxInstructionSetLength = 20
+)
+
+var (
+	day17AdjacentOffsets = []u.Vec2i{
+		{X: -1, Y: 0},
+		{X: 1, Y: 0},
+		{X: 0, Y: -1},
+		{X: 0, Y: 1},
+	}
+)
+
+type Day17 struct {
+	program u.IntcodeProgram
+}
+
+func (d *Day17) Parse() {
+	d.program = u.LoadIntcodeProgram("17p")
+}
+
+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] {
+			case cellTypeOpen:
+				fmt.Print(" ")
+			case cellTypeScaffold:
+				char := "█"
+				color := u.ColorBlack
+				if botLocation.X == x && botLocation.Y == y {
+					switch botFacingDir {
+					case botFacingUp:
+						char = "^"
+					case botFacingLeft:
+						char = "<"
+					case botFacingDown:
+						char = "v"
+					case botFacingRight:
+						char = ">"
+					}
+				} else if endLocation.X == x && endLocation.Y == y {
+					char = "@"
+				} else {
+					color = u.ColorWhite
+				}
+				fmt.Printf("%s%s%s%s", u.BackgroundWhite, color, char, u.TextReset)
+			}
+		}
+		fmt.Println()
+	}
+}
+
+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(grid) ||
+			offX < 0 || offX >= len(grid[0]) {
+			continue
+		}
+
+		if grid[offY][offX] == cellTypeScaffold {
+			retval = append(retval, u.Vec2i{X: offX, Y: offY})
+		}
+	}
+
+	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 {
+				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
+		}
+	}
+
+	return y, currBotLocation, currBotFacing
+}
+
+func (grid day17Grid) getCellTypeInDirection(y, x int, facingDir botFacing) (camViewCellType, int, int) {
+	newX := x
+	newY := y
+	switch facingDir {
+	case botFacingUp:
+		newY--
+	case botFacingLeft:
+		newX--
+	case botFacingDown:
+		newY++
+	case botFacingRight:
+		newX++
+	}
+
+	if newY < 0 || newY >= len(grid) || newX < 0 || newX >= len(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))
+		}
+	}
+
+	switch rVal {
+	case '#':
+		ensureCapacity(row)
+		(*grid)[row] = append((*grid)[row], cellTypeScaffold)
+	case '.':
+		ensureCapacity(row)
+		(*grid)[row] = append((*grid)[row], 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}
+			}
+		}
+	})
+
+	return endLocation
+}
+
+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.
+	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 {
+		if u.ArrayContains(adj, u.Vec2i{X: pos.X, Y: pos.Y - 1}) {
+			if botFacingDir == botFacingLeft {
+				turnDirection = dirRight
+			} else if botFacingDir == botFacingRight {
+				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
+			}
+		}
+	}
+
+	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 := range progs {
+		numFound := minimumRecurrence
+		subLen := initialInstructionSubsetLen
+		for numFound >= minimumRecurrence {
+			numFound = 1
+			instructionSubset := strings.Join(workingInstructions[0:subLen], ",")
+			if len(instructionSubset) > maxInstructionSetLength {
+				break
+			}
+			for x := len(instructionSubset); x <= len(instructionStr)-len(instructionSubset); x++ {
+				if instructionStr[x:x+len(instructionSubset)] == instructionSubset {
+					numFound++
+					x += len(instructionSubset)
+				}
+			}
+			if numFound >= minimumRecurrence {
+				subLen += 2
+			}
+		}
+		if numFound < minimumRecurrence {
+			subLen -= 2
+		}
+		progs[i] = make([]string, subLen)
+		copy(progs[i], workingInstructions[0:subLen])
+
+		instructionStr = strings.ReplaceAll(instructionStr, strings.Join(progs[i], ","), "")
+		instructionStr = strings.TrimPrefix(strings.ReplaceAll(instructionStr, ",,", ","), ",")
+
+		if len(instructionStr) == 0 {
+			workingInstructions = nil
+		} else {
+			workingInstructions = strings.Split(instructionStr, ",")
+		}
+	}
+
+	if workingInstructions != nil {
+		panic("failed to use up all instructions")
+	}
+
+	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
+
+	d.program.Reset()
+	d.program.SetMemory(0, 2)
+
+	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) {
+		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
+	})
+
+	// 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)
+}
--- a/days/18.go
+++ b/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)
+}
--- a/days/19.go
+++ b/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)
+}
--- a/go.mod
+++ b/go.mod
@ -1,3 +1,5 @@
 module parnic.com/aoc2019

 go 1.18
+
+require github.com/edwingeng/deque/v2 v2.0.1
--- a/go.sum
+++ b/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=
--- a/inputs/15p.txt
+++ b/inputs/15p.txt
@ -1 +1 @@
-3,1033,1008,1033,1,1032,1005,1032,31,1008,1033,2,1032,1005,1032,58,1008,1033,3,1032,1005,1032,81,1008,1033,4,1032,1005,1032,104,99,1002,1034,1,1039,1001,1036,0,1041,1001,1035,-1,1040,1008,1038,0,1043,102,-1,1043,1032,1,1037,1032,1042,1105,1,124,102,1,1034,1039,1001,1036,0,1041,1001,1035,1,1040,1008,1038,0,1043,1,1037,1038,1042,1106,0,124,1001,1034,-1,1039,1008,1036,0,1041,1002,1035,1,1040,1002,1038,1,1043,101,0,1037,1042,1106,0,124,1001,1034,1,1039,1008,1036,0,1041,101,0,1035,1040,1002,1038,1,1043,101,0,1037,1042,1006,1039,217,1006,1040,217,1008,1039,40,1032,1005,1032,217,1008,1040,40,1032,1005,1032,217,1008,1039,37,1032,1006,1032,165,1008,1040,9,1032,1006,1032,165,1101,2,0,1044,1105,1,224,2,1041,1043,1032,1006,1032,179,1101,1,0,1044,1106,0,224,1,1041,1043,1032,1006,1032,217,1,1042,1043,1032,1001,1032,-1,1032,1002,1032,39,1032,1,1032,1039,1032,101,-1,1032,1032,101,252,1032,211,1007,0,50,1044,1106,0,224,1102,0,1,1044,1105,1,224,1006,1044,247,1001,1039,0,1034,102,1,1040,1035,102,1,1041,1036,101,0,1043,1038,102,1,1042,1037,4,1044,1106,0,0,37,22,74,27,37,99,30,8,72,31,49,29,51,32,85,21,39,72,2,2,43,94,31,11,76,43,95,21,38,8,90,13,39,97,54,47,14,6,20,49,5,30,97,9,99,64,71,24,36,87,52,94,36,18,52,42,83,38,98,53,26,87,69,32,18,94,2,93,97,15,65,65,21,40,99,19,91,13,4,89,38,70,65,41,73,49,62,54,37,46,14,49,88,86,13,89,23,89,10,3,48,57,92,43,65,4,35,97,48,10,19,64,3,79,38,87,6,13,71,49,74,43,92,8,4,71,6,35,85,98,94,6,38,59,80,65,46,62,63,62,49,61,68,6,7,64,66,40,56,82,59,30,85,45,57,36,86,70,25,83,31,96,65,19,16,67,55,36,49,54,29,75,69,3,3,37,75,49,23,65,22,6,52,75,31,7,87,85,19,48,97,65,51,78,10,35,40,59,54,14,85,6,30,94,68,42,87,46,75,26,82,36,21,65,90,16,59,14,76,55,37,41,99,80,9,79,12,59,17,75,2,40,52,45,76,45,16,82,13,55,61,14,11,49,97,81,99,38,35,20,98,51,64,13,24,85,94,38,25,87,1,42,89,18,32,54,55,17,15,84,98,25,31,21,55,44,57,59,11,78,49,72,87,20,7,33,91,80,75,18,33,37,52,7,26,87,65,36,52,92,6,8,95,89,37,38,57,25,23,71,75,47,20,87,90,37,54,38,77,32,39,67,16,69,62,15,96,47,91,95,18,96,24,45,21,64,9,72,2,54,65,39,36,54,23,71,74,18,26,97,35,44,29,87,54,48,31,55,33,85,74,13,99,82,39,35,97,43,20,62,58,86,98,41,47,92,79,74,10,85,28,66,86,18,35,5,84,67,13,91,47,44,1,84,56,32,96,7,77,21,88,92,38,31,65,82,87,45,55,4,60,58,64,49,53,3,63,32,52,43,10,66,75,96,53,11,95,44,36,16,65,91,47,32,9,3,73,29,25,93,29,18,88,45,41,46,12,94,13,89,5,36,94,88,33,10,10,2,52,90,19,63,26,84,12,76,16,42,75,63,39,32,72,72,84,70,2,63,33,74,43,68,38,84,72,44,89,18,24,78,69,4,80,41,54,75,72,4,16,91,5,48,30,64,38,4,52,38,30,95,99,32,38,52,35,58,71,38,89,86,25,84,88,41,39,32,56,79,12,52,19,80,46,66,38,32,69,67,6,87,88,36,59,51,5,33,46,45,82,15,57,80,91,12,86,29,34,15,61,19,73,46,82,60,73,13,52,36,67,3,49,87,39,12,98,58,87,32,82,47,65,6,87,71,13,17,65,69,14,34,42,82,42,1,77,63,10,63,28,90,24,13,99,19,38,68,62,44,2,65,81,95,7,54,24,58,16,58,48,95,9,80,9,51,73,23,96,49,64,58,1,6,72,69,39,2,10,63,36,9,85,59,90,41,2,72,77,23,23,80,75,33,6,20,18,59,39,36,89,35,89,42,42,22,37,24,30,51,53,43,78,48,27,76,84,22,81,72,25,95,28,15,51,58,48,7,1,90,72,19,37,52,60,39,81,20,70,6,39,82,26,77,14,96,52,30,84,33,66,80,5,52,15,72,46,55,2,21,8,97,79,43,8,91,27,67,5,18,74,71,34,51,6,83,25,52,92,5,15,85,11,72,33,85,30,59,6,84,29,51,77,99,43,95,44,83,95,89,27,54,16,85,90,82,34,98,59,87,12,73,25,74,29,95,82,51,5,81,46,51,0,0,21,21,1,10,1,0,0,0,0,0,0
+3,1033,1008,1033,1,1032,1005,1032,31,1008,1033,2,1032,1005,1032,58,1008,1033,3,1032,1005,1032,81,1008,1033,4,1032,1005,1032,104,99,102,1,1034,1039,101,0,1036,1041,1001,1035,-1,1040,1008,1038,0,1043,102,-1,1043,1032,1,1037,1032,1042,1105,1,124,102,1,1034,1039,1001,1036,0,1041,1001,1035,1,1040,1008,1038,0,1043,1,1037,1038,1042,1105,1,124,1001,1034,-1,1039,1008,1036,0,1041,1001,1035,0,1040,1001,1038,0,1043,1002,1037,1,1042,1105,1,124,1001,1034,1,1039,1008,1036,0,1041,102,1,1035,1040,101,0,1038,1043,1001,1037,0,1042,1006,1039,217,1006,1040,217,1008,1039,40,1032,1005,1032,217,1008,1040,40,1032,1005,1032,217,1008,1039,3,1032,1006,1032,165,1008,1040,33,1032,1006,1032,165,1101,0,2,1044,1105,1,224,2,1041,1043,1032,1006,1032,179,1101,1,0,1044,1106,0,224,1,1041,1043,1032,1006,1032,217,1,1042,1043,1032,1001,1032,-1,1032,1002,1032,39,1032,1,1032,1039,1032,101,-1,1032,1032,101,252,1032,211,1007,0,37,1044,1106,0,224,1102,1,0,1044,1105,1,224,1006,1044,247,101,0,1039,1034,101,0,1040,1035,1001,1041,0,1036,1002,1043,1,1038,101,0,1042,1037,4,1044,1106,0,0,42,4,15,10,25,91,86,34,69,14,50,9,24,24,54,10,18,63,17,2,88,36,31,60,20,13,20,76,94,25,41,36,78,3,39,17,94,10,25,22,16,67,72,31,47,15,25,66,8,17,54,8,89,67,29,28,92,11,54,14,4,64,78,28,80,66,6,70,36,56,13,63,17,19,83,17,27,29,34,54,4,93,24,71,6,66,22,21,92,93,39,4,31,76,72,25,74,89,18,62,18,27,57,35,83,39,14,23,95,2,79,25,97,86,13,79,1,34,90,81,29,45,31,38,67,17,92,32,31,50,1,42,81,1,2,87,7,52,74,20,85,22,32,47,16,77,96,28,14,74,22,55,15,75,44,29,19,8,73,2,54,18,26,64,95,21,98,48,25,36,11,78,77,5,16,70,18,10,76,51,51,10,25,43,56,12,13,48,8,17,68,10,64,25,93,42,3,52,24,72,99,23,54,13,44,17,15,8,68,59,15,95,61,9,50,8,51,23,8,39,13,95,64,12,28,56,90,1,62,27,12,60,6,5,18,24,13,99,12,18,92,97,7,56,22,48,91,34,87,32,98,20,89,74,16,51,84,21,46,14,23,52,17,57,12,50,17,97,23,99,11,21,68,21,61,89,13,45,64,89,18,36,40,35,90,9,1,3,81,33,32,83,99,97,34,4,46,31,21,90,62,14,93,11,22,99,51,70,88,51,2,4,29,36,35,48,17,25,30,69,34,3,39,89,31,89,33,30,88,77,18,30,67,17,40,61,19,40,85,26,23,49,22,41,30,13,79,6,34,40,33,43,49,84,19,78,43,10,74,18,61,15,22,51,86,2,78,11,33,92,24,88,27,24,44,2,97,4,4,49,72,93,24,65,79,21,60,33,46,36,22,15,87,33,78,2,49,70,7,78,78,11,14,64,41,61,41,6,1,49,35,78,47,65,14,66,10,86,76,2,32,88,3,24,14,87,9,95,32,19,4,10,67,60,15,19,53,47,24,29,65,5,95,35,1,70,16,43,53,11,64,17,34,84,74,65,30,18,58,2,35,48,38,33,46,16,87,27,12,79,11,88,35,7,5,35,67,83,38,6,17,56,82,13,45,32,30,67,25,62,7,43,63,9,36,14,58,53,25,98,12,38,78,13,63,93,33,11,54,9,66,32,79,62,47,28,6,67,31,53,71,2,30,59,12,90,59,67,2,58,52,1,30,51,49,22,89,88,27,19,41,27,13,19,76,5,82,58,12,49,51,17,15,73,35,25,74,90,29,14,96,83,69,11,18,14,10,40,93,35,31,35,36,58,36,16,48,7,66,98,31,47,34,47,33,5,28,82,88,1,30,80,95,32,87,2,19,91,74,74,19,8,25,63,65,51,30,14,41,98,99,21,90,15,91,3,31,74,27,31,77,28,74,4,27,88,82,11,54,35,52,13,88,71,93,20,82,18,36,68,33,83,1,18,5,42,46,29,62,10,78,67,9,84,48,22,33,74,36,53,58,31,5,8,55,10,24,49,34,81,1,4,86,5,25,2,75,36,49,2,24,88,72,8,64,36,38,10,23,36,93,28,51,90,4,99,57,31,10,14,94,21,27,61,34,70,41,32,14,91,20,83,30,54,26,44,30,85,96,87,35,16,61,99,16,32,53,68,87,1,89,43,9,17,4,39,50,61,8,49,27,48,13,51,34,47,30,89,68,50,18,63,99,50,32,41,33,71,1,43,57,64,24,95,9,89,8,64,18,75,23,97,74,67,24,55,1,87,97,44,0,0,21,21,1,10,1,0,0,0,0,0,0
--- a/inputs/16p.txt
+++ b/inputs/16p.txt
@ -0,0 +1 @@
+59791875142707344554745984624833270124746225787022156176259864082972613206097260696475359886661459314067969858521185244807128606896674972341093111690401527976891268108040443281821862422244152800144859031661510297789792278726877676645835805097902853584093615895099152578276185267316851163313487136731134073054989870018294373731775466754420075119913101001966739563592696702233028356328979384389178001923889641041703308599918672055860556825287836987992883550004999016194930620165247185883506733712391462975446192414198344745434022955974228926237100271949068464343172968939069550036969073411905889066207300644632441054836725463178144030305115977951503567
--- a/inputs/16s1.txt
+++ b/inputs/16s1.txt
@ -0,0 +1 @@
+12345678
--- a/inputs/16s2.txt
+++ b/inputs/16s2.txt
@ -0,0 +1 @@
+80871224585914546619083218645595
--- a/inputs/16s3.txt
+++ b/inputs/16s3.txt
@ -0,0 +1 @@
+19617804207202209144916044189917
--- a/inputs/16s4.txt
+++ b/inputs/16s4.txt
@ -0,0 +1 @@
+69317163492948606335995924319873
--- a/inputs/17p.txt
+++ b/inputs/17p.txt
@ -0,0 +1 @@
+1,330,331,332,109,2734,1102,1182,1,15,1102,1,1429,24,1002,0,1,570,1006,570,36,1001,571,0,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,15,1,15,1008,15,1429,570,1006,570,14,21102,58,1,0,1105,1,786,1006,332,62,99,21101,0,333,1,21102,73,1,0,1105,1,579,1101,0,0,572,1101,0,0,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,1001,574,0,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1105,1,81,21102,1,340,1,1105,1,177,21101,0,477,1,1106,0,177,21101,0,514,1,21101,0,176,0,1106,0,579,99,21102,1,184,0,1106,0,579,4,574,104,10,99,1007,573,22,570,1006,570,165,1001,572,0,1182,21102,1,375,1,21101,211,0,0,1106,0,579,21101,1182,11,1,21102,1,222,0,1105,1,979,21102,1,388,1,21102,233,1,0,1105,1,579,21101,1182,22,1,21101,0,244,0,1106,0,979,21101,401,0,1,21101,0,255,0,1105,1,579,21101,1182,33,1,21102,266,1,0,1106,0,979,21102,1,414,1,21102,1,277,0,1106,0,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21102,1182,1,1,21101,313,0,0,1106,0,622,1005,575,327,1102,1,1,575,21102,327,1,0,1105,1,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,6,0,0,109,4,1202,-3,1,587,20101,0,0,-1,22101,1,-3,-3,21101,0,0,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1105,1,597,109,-4,2106,0,0,109,5,2102,1,-4,630,20102,1,0,-2,22101,1,-4,-4,21102,0,1,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,652,21002,0,1,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21101,0,702,0,1105,1,786,21201,-1,-1,-1,1106,0,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21101,0,731,0,1106,0,786,1105,1,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,0,756,0,1106,0,786,1106,0,774,21202,-1,-11,1,22101,1182,1,1,21102,774,1,0,1105,1,622,21201,-3,1,-3,1105,1,640,109,-5,2106,0,0,109,7,1005,575,802,21002,576,1,-6,20101,0,577,-5,1105,1,814,21102,1,0,-1,21102,1,0,-5,21102,0,1,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,29,-3,22201,-6,-3,-3,22101,1429,-3,-3,1202,-3,1,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21102,1,1,-1,1105,1,924,1205,-2,873,21102,1,35,-4,1105,1,924,1202,-3,1,878,1008,0,1,570,1006,570,916,1001,374,1,374,2101,0,-3,895,1101,2,0,0,2102,1,-3,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,922,20101,0,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,29,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,45,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1101,1,0,575,21101,973,0,0,1105,1,786,99,109,-7,2105,1,0,109,6,21101,0,0,-4,21102,1,0,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1105,1,1041,21102,-4,1,-2,1106,0,1041,21101,-5,0,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,1201,-2,0,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,2101,0,-2,0,1106,0,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1105,1,989,21101,439,0,1,1105,1,1150,21102,1,477,1,1105,1,1150,21102,1,514,1,21102,1,1149,0,1105,1,579,99,21101,1157,0,0,1106,0,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,2101,0,-5,1176,1202,-4,1,0,109,-6,2105,1,0,6,5,28,1,28,1,28,1,28,1,28,1,20,11,1,7,10,1,7,1,1,1,1,1,5,1,10,1,5,11,1,1,10,1,5,1,1,1,1,1,1,1,3,1,1,1,10,9,1,1,1,1,1,5,16,1,3,1,1,1,1,1,1,1,18,5,1,1,1,1,1,1,24,1,1,1,1,1,24,1,1,1,1,1,24,1,1,1,1,1,24,5,7,1,18,1,9,1,18,1,9,1,18,1,9,1,18,1,9,1,18,1,9,1,12,7,9,1,12,1,15,1,12,1,15,1,12,1,15,1,12,1,15,1,12,1,15,1,2,5,5,1,9,7,2,1,3,1,5,1,9,1,8,1,3,1,5,1,9,1,8,1,3,1,5,1,9,1,8,1,3,13,3,1,8,1,9,1,5,1,3,1,8,11,5,1,1,5,22,1,1,1,1,1,1,1,22,1,1,1,1,1,1,1,22,1,1,1,1,1,1,1,22,13,18,1,1,1,1,1,5,1,16,5,1,1,5,1,16,1,1,1,3,1,5,1,16,1,1,11,16,1,5,1,22,7,6
--- a/inputs/18p.txt
+++ b/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......#.....#.....#.........#
+#################################################################################
--- a/inputs/18s1.txt
+++ b/inputs/18s1.txt
@ -0,0 +1,3 @@
+#########
+#b.A.@.a#
+#########
--- a/inputs/18s2.txt
+++ b/inputs/18s2.txt
@ -0,0 +1,5 @@
+########################
+#f.D.E.e.C.b.A.@.a.B.c.#
+######################.#
+#d.....................#
+########################
--- a/inputs/18s3.txt
+++ b/inputs/18s3.txt
@ -0,0 +1,5 @@
+########################
+#...............b.C.D.f#
+#.######################
+#.....@.a.B.c.d.A.e.F.g#
+########################
--- a/inputs/18s4.txt
+++ b/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#
+#################
--- a/inputs/18s5.txt
+++ b/inputs/18s5.txt
@ -0,0 +1,6 @@
+########################
+#@..............ac.GI.b#
+###d#e#f################
+###A#B#C################
+###g#h#i################
+########################
--- a/inputs/18s6.txt
+++ b/inputs/18s6.txt
@ -0,0 +1,7 @@
+#######
+#a.#Cd#
+##...##
+##.@.##
+##...##
+#cB#Ab#
+#######
--- a/inputs/18s7.txt
+++ b/inputs/18s7.txt
@ -0,0 +1,7 @@
+###############
+#d.ABC.#.....a#
+######...######
+######.@.######
+######...######
+#b.....#.....c#
+###############
--- a/inputs/18s8.txt
+++ b/inputs/18s8.txt
@ -0,0 +1,7 @@
+#############
+#DcBa.#.GhKl#
+#.###...#I###
+#e#d#.@.#j#k#
+###C#...###J#
+#fEbA.#.FgHi#
+#############
--- a/inputs/18s9.txt
+++ b/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.#
+#############
--- a/inputs/19p.txt
+++ b/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
--- a/main.go
+++ b/main.go
@ -5,6 +5,7 @@ import (
 	"fmt"
 	"log"
 	"os"
+	"runtime/pprof"
 	"strconv"
 	"strings"
 	"time"
@ -28,6 +29,8 @@ const (
 var (
 	flagPart1      = flag.Bool("part1", false, "whether to run part1 or not; if no flags are present, all parts are run")
 	flagPart2      = flag.Bool("part2", false, "whether to run part2 or not; if no flags are present, all parts are run")
+	flagCpuProfile = flag.String("cpuprofile", "", "write cpu profile to file")
+	flagMemProfile = flag.String("memprofile", "", "write memory profile to file")
 )

 var dayMap = []day{
@ -46,11 +49,26 @@ var dayMap = []day{
 	&days.Day13{},
 	&days.Day14{},
 	&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 {
@ -75,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) {
@ -95,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
@ -102,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 {
--- a/utilities/array.go
+++ b/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
+}
--- a/utilities/bisect.go
+++ b/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
+}
--- a/utilities/intcode.go
+++ b/utilities/intcode.go
@ -128,9 +128,15 @@ func (p *IntcodeProgram) ensureMemoryCapacity(address int) {
 }

 func (p *IntcodeProgram) Reset() {
+	wiped := false
+	if len(p.memory) != len(p.program) {
+		wiped = true
 		p.memory = nil
+	}
 	p.init()
+	if !wiped {
 		copy(p.memory, p.program)
+	}
 	p.relativeBase = 0
 }

--- a/utilities/map.go
+++ b/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
+}
--- a/utilities/vector.go
+++ b/utilities/vector.go
@ -13,6 +13,8 @@ type Vec3[T Number] struct {
 	Z T
 }

+type Vec2i Vec2[int]
+
 func (v Vec2[T]) Dot(other Vec2[T]) T {
 	return (v.X * other.X) + (v.Y * other.Y)
 }
@ -42,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]{
-		X: a.X - b.X,
-		Y: a.Y - b.Y,
-	}
+	return a.To(b)
+}
+
+func ManhattanDistance[T Number](a, b Vec2[T]) T {
+	return a.ManhattanDistance(b)
 }

 func (v Vec3[T]) Dot(other Vec3[T]) T {
Author	SHA1	Message	Date
Parnic	788d22f33c	Merge branch 'develop' into dev/19	2022-06-21 01:18:12 -05:00
Parnic	34ece5dd77	Revert "Merge branch 'develop' into dev/19" This reverts commit `5247ae9d72`, reversing changes made to `9947a9b559`.	2022-06-21 01:18:05 -05:00
Parnic	e153d022a7	Intcode Reset optimization Initially I noticed that I was copying twice unnecessarily (once in init() after nulling out memory, and again after returning from init()). After cleaning that up, I realized that we don't need to create a new buffer at all if the program never malloc-ed, so sometimes we can skip the re-init and we can always avoid the double-copy. I don't know if this is actually measurable anywhere, but I spot-checked some results and I still seem to be getting the same answers, so I'm gonna roll with it.	2022-06-21 01:17:33 -05:00
Parnic	b97ec2eb17	Add bisect utility This is too common of an optimization to not have this readily accessible. And I kinda like how this worked out, too. Go is fun.	2022-06-21 01:17:31 -05:00
Parnic	de07c7c987	First optimizations This gets runtime down to about a quarter of what it was. I need to see if I can apply bisect to the X value, but I'm not sure I understand how/if that can work.	2022-06-21 01:16:42 -05:00
Parnic	5247ae9d72	Merge branch 'develop' into dev/19	2022-06-21 00:22:40 -05:00
Parnic	dfc2eb6e4f	Intcode Reset optimization Initially I noticed that I was copying twice unnecessarily (once in init() after nulling out memory, and again after returning from init()). After cleaning that up, I realized that we don't need to create a new buffer at all if the program never malloc-ed, so sometimes we can skip the re-init and we can always avoid the double-copy. I don't know if this is actually measurable anywhere, but I spot-checked some results and I still seem to be getting the same answers, so I'm gonna roll with it.	2022-06-21 00:21:58 -05:00
Parnic	94471df109	Add bisect utility This is too common of an optimization to not have this readily accessible. And I kinda like how this worked out, too. Go is fun.	2022-06-21 00:12:06 -05:00
Parnic	9947a9b559	Day 19 functional We're at about 1s runtime on my macbook, but we do get the right answer now.	2022-06-21 00:11:22 -05:00
Parnic	cbaab27054	Day 19 almost Part 1 works, part 2 is giving me trouble. I need to find a better way to validate whether 100x100 can fit, and then something faster to figure out the minimum position. In other words, the entire problem.	2022-06-20 08:58:58 -05:00
Parnic	23bf2e9d84	Day 18 solution This one was a doozy and took far more time than I'd like to admit. I hope it's the hardest problem of the year. My original solution gave correct answers, but took on the order of 3+ minutes to run, even with memoization (it wasn't finishing any time soon without it). I then tried dropping in some A* and Dijkstra libraries, but wasn't really happy with how things were progressing with them. Some research pointed me toward double-ended queues and priority queues as better solutions, which I should have come up with my own since they've been used along with memoization in other AoC's, and dropping those in took the runtimes down to 4-15 seconds on my m1 macbook air. Once I swapped out the memoized data structures from arrays to maps, the runtime finally dropped to a much more palatable 50-180 millisecond range. I'm always suspicious when my solution is hundreds of lines of code, though, since you tend to see much more terse solutions from others in the AoC subreddit, but I attribute at least some of the bloat to "Go things" like how maps and arrays usually need to be "make"d first, how there's no easy "list comprehension" or "linq" style data structure queries, etc. Finally: note that I've seen _dramatically_ different runtimes based on the input. One set of input I checked against ran in 30ms/10ms while another ran in 180ms/54ms. I guess it's never been promised that all inputs are created equally...	2022-06-18 23:13:19 -05:00
Parnic	a0867490c9	Add utility for array AddUnique	2022-06-18 23:07:38 -05:00
Parnic	3d3ea6e266	Add support for cpu and memory profiling My day 18 was slow and I wasn't completely certain where it was all coming from, so I dove into Go's profiling stuff. It was super helpful in identifying the problem and giving me easy wins that took runtime from 4.6s/14.4s (part 1/part 2) to 180ms/50ms just from swapping some arrays for maps, which the profile pointed out very clearly.	2022-06-18 23:07:38 -05:00
Parnic	4b5bd0d4e0	Display part1 output as soon as it's ready When we start having problems that take a while to run, it sucks to have to wait for everything to finish before we see any output.	2022-06-18 22:49:28 -05:00
Parnic	5bc089c83d	Day 17 solution My initial idea for a solution ended up working out great, but I had a hard time getting it all down on "paper," so to speak, so this is probably 200 lines of code too many, but it definitely does exactly what I envisioned (and quickly) even if it's not the most succinct.	2022-06-14 14:37:06 -05:00
Parnic	c788813cd2	Day 16 solution Following the formula for part 1 was straightforward enough, but finding the pattern for part 2 and deducing the shortcut formula took me a while. That first 0 1 propagate enough that by the time we get halfway through applying the formula, it's all 0s and 1s, so sort of like an addition with a mask on what numbers we're adding.	2022-06-13 15:30:17 -05:00
Parnic	788239e531	Day 15 solution I wanted to use something like a right-hand wall solver, but the fact that you don't know the maze ahead of time and you can't see what something is without trying to move into it made that difficult. This semi-brute-force approach works well enough. I originally stopped as soon as I found the oxygen system and figured out the shortest path, but once I submitted that answer and saw that part 2 wanted the full map explored, I figured I might as well just fill the map all at once. I think I would have been stuck on part 1 longer if my input set didn't happen to find the goal system fairly easily (or maybe my debug drawing helped me work through it with that input set specifically, I'm not sure) since a different input set required some tweaking to the max-visited threshold in order to find things that my first input set found with a lower setting. Regardless, I'm pretty excited that I came to Trémaux's algorithm, more or less, on my own. I went to Wikipedia to see if I was on the right track and lo and behold, I had come to a version of it myself. Part 2 turned out easier than I originally thought. I suspected this solution would work, but wasn't completely confident. It can only work for the type of maze used by this problem (where there are no loops of open areas). I'm just glad I didn't need A* or anything. Oh, and this `stringer` command that allows debug printing of enums can be installed with `go install golang.org/x/tools/cmd/stringer@latest`	2022-06-13 15:30:17 -05:00
Parnic	37928d7138	Day 14 solution This one's part 1 destroyed me. I had a very difficult time, trying 3 separate approaches, each one of which worked for most cases but eventually fell apart on the 5th sample or my actual puzzle input. I ended up reading a bunch of hints from the subreddit which eventually led me to a blog post describing this solution, which wasn't far off from what I had, but I was overcomplicating things. Part 2 surprised me in that I expected a simple "ore available divided by ore needed for 1 fuel" would solve it, but of course the excess chemicals produced in any given reaction meant that it wasn't that simple. So this approach uses that estimate as a lower bound, since it always underestimates, and then bisects its way to the solution (starting at the lower bound and adding 1 each time took too long). I'm sure a smarter upper bound choice could lower the runtime of this by a bit, but runtime isn't bad enough right now for me to try any additional optimizations.	2022-06-13 15:30:17 -05:00
Parnic	da5823aa17	Day 13 solution This was incredibly cool and I had a really fun time with it. Uncomment everything to see the game play itself! Note that I'm not seeking around in the terminal window to make the drawing smooth, I'm just outputting each new frame as it happens, so there's some jitter, but it still looks great! I messed around a bit with control codes to move the cursor around instead of the "draw the buffer over and over again" approach, and they work, mostly, but I'm sticking with this for now.	2022-06-13 15:30:17 -05:00
Parnic	8282e09a42	Day 12 solution Okay, I had to seek help on this one. The orbital period + least-common-multiple solution was not coming to me.	2022-06-13 15:30:17 -05:00
Parnic	343007481a	Day 11 solution	2022-06-13 15:30:17 -05:00
Parnic	44eeb5a8a6	Day 10 solution This one was an absolute beating for me. I am so bad at these sorts of problems. Ultimately I settled on a probably-not-ideal solution that crawls the graph with offsets of each variant of (+/-x,+/-y), marking nodes visited as we come across them so that we end up with a list of asteroids that we can see. Given that this is day 10, and knowing how bad I am at math, I'm assuming this is very far from the intended solution, but it works reasonably quickly and I managed to come up with it myself, so I'm not going to stress too much about it. For asteroid destruction, the best method I could come up with for finding the correct order was to implement an entire Vector class and sort by angle, which worked, but again, I can't decide if it was the intended solution or not. I should start reusing past years' codebases so I don't have to keep building a utility library from scratch.	2022-06-13 15:30:17 -05:00
Parnic	f8d2758c90	Move Pair to a more reusable location I originally used this in my day 10 solution, but ended up removing it. Either way, it's a general utility so it belongs here.	2022-06-13 15:30:17 -05:00
Parnic	d9e0d9b649	Day 9 solution This day showed me that when the input instruction was introduced and said "write addresses will never be in immediate mode", that didn't mean "so don't bother handling modes for input addresses", it meant "handle the mode, but assert if it's immediate mode". It was super helpful that this program contained a bootstrap sequence to validate each instruction. Memory expansion came with a few caveats: obviously reads and writes needed to handle expanding the memory space, but a Reset also can no longer get away with simply copying the program into memory again because we need to ensure that any additional memory is cut off (or at least zeroed), so the quickest way to handle that in Go is to simply allocate a new buffer; I'd rather manipulate the existing buffer, but I'm having a hard time finding the best way to do that. And finally, make sure you reset your relativeBase when resetting the program...that one was ugly to track down.	2022-06-13 15:30:17 -05:00
Parnic	94d83695bf	Day 8 solution I had fun with this one. I liked how straightforward it was, and it's always satisfying to see the code print a message visually when you're done.	2022-06-13 15:30:17 -05:00
Parnic	365edf82b1	Day 7 solution I will probably end up regretting this since I assume the "wait to be given an input from some other process before continuing execution" paradigm is going to come up again, but this part 2 goroutine+channel solution felt good (taking advantage of Go features) and made me happy, so I rolled with it.	2022-06-13 15:30:16 -05:00
Parnic	a099a86511	Day 6 solution I'm reasonably happy with this. I started with a bi-directional linked list, but realized that a flat list of all nodes came in handy for one use case while the linked list came in handy for another, so I settled on that.	2022-06-13 15:30:10 -05:00
Parnic	acef5fdc12	Day 5 solution This required an overhaul of the intcode machine to actually be its own type that could operate on its own memory and stuff. So I had to touch day 2 to make it adhere to the new API. Feeling good about this foundation now. Until I get gobsmacked at some point later, which I expect to happen.	2022-06-13 15:29:18 -05:00
				`@ -0,0 +1 @@`
				59791875142707344554745984624833270124746225787022156176259864082972613206097260696475359886661459314067969858521185244807128606896674972341093111690401527976891268108040443281821862422244152800144859031661510297789792278726877676645835805097902853584093615895099152578276185267316851163313487136731134073054989870018294373731775466754420075119913101001966739563592696702233028356328979384389178001923889641041703308599918672055860556825287836987992883550004999016194930620165247185883506733712391462975446192414198344745434022955974228926237100271949068464343172968939069550036969073411905889066207300644632441054836725463178144030305115977951503567
				`@ -0,0 +1 @@`
				1,330,331,332,109,2734,1102,1182,1,15,1102,1,1429,24,1002,0,1,570,1006,570,36,1001,571,0,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,15,1,15,1008,15,1429,570,1006,570,14,21102,58,1,0,1105,1,786,1006,332,62,99,21101,0,333,1,21102,73,1,0,1105,1,579,1101,0,0,572,1101,0,0,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,1001,574,0,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1105,1,81,21102,1,340,1,1105,1,177,21101,0,477,1,1106,0,177,21101,0,514,1,21101,0,176,0,1106,0,579,99,21102,1,184,0,1106,0,579,4,574,104,10,99,1007,573,22,570,1006,570,165,1001,572,0,1182,21102,1,375,1,21101,211,0,0,1106,0,579,21101,1182,11,1,21102,1,222,0,1105,1,979,21102,1,388,1,21102,233,1,0,1105,1,579,21101,1182,22,1,21101,0,244,0,1106,0,979,21101,401,0,1,21101,0,255,0,1105,1,579,21101,1182,33,1,21102,266,1,0,1106,0,979,21102,1,414,1,21102,1,277,0,1106,0,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21102,1182,1,1,21101,313,0,0,1106,0,622,1005,575,327,1102,1,1,575,21102,327,1,0,1105,1,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,6,0,0,109,4,1202,-3,1,587,20101,0,0,-1,22101,1,-3,-3,21101,0,0,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1105,1,597,109,-4,2106,0,0,109,5,2102,1,-4,630,20102,1,0,-2,22101,1,-4,-4,21102,0,1,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,652,21002,0,1,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21101,0,702,0,1105,1,786,21201,-1,-1,-1,1106,0,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21101,0,731,0,1106,0,786,1105,1,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,0,756,0,1106,0,786,1106,0,774,21202,-1,-11,1,22101,1182,1,1,21102,774,1,0,1105,1,622,21201,-3,1,-3,1105,1,640,109,-5,2106,0,0,109,7,1005,575,802,21002,576,1,-6,20101,0,577,-5,1105,1,814,21102,1,0,-1,21102,1,0,-5,21102,0,1,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,29,-3,22201,-6,-3,-3,22101,1429,-3,-3,1202,-3,1,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21102,1,1,-1,1105,1,924,1205,-2,873,21102,1,35,-4,1105,1,924,1202,-3,1,878,1008,0,1,570,1006,570,916,1001,374,1,374,2101,0,-3,895,1101,2,0,0,2102,1,-3,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,922,20101,0,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,29,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,45,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1101,1,0,575,21101,973,0,0,1105,1,786,99,109,-7,2105,1,0,109,6,21101,0,0,-4,21102,1,0,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1105,1,1041,21102,-4,1,-2,1106,0,1041,21101,-5,0,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,1201,-2,0,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,2101,0,-2,0,1106,0,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1105,1,989,21101,439,0,1,1105,1,1150,21102,1,477,1,1105,1,1150,21102,1,514,1,21102,1,1149,0,1105,1,579,99,21101,1157,0,0,1106,0,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,2101,0,-5,1176,1202,-4,1,0,109,-6,2105,1,0,6,5,28,1,28,1,28,1,28,1,28,1,20,11,1,7,10,1,7,1,1,1,1,1,5,1,10,1,5,11,1,1,10,1,5,1,1,1,1,1,1,1,3,1,1,1,10,9,1,1,1,1,1,5,16,1,3,1,1,1,1,1,1,1,18,5,1,1,1,1,1,1,24,1,1,1,1,1,24,1,1,1,1,1,24,1,1,1,1,1,24,5,7,1,18,1,9,1,18,1,9,1,18,1,9,1,18,1,9,1,18,1,9,1,12,7,9,1,12,1,15,1,12,1,15,1,12,1,15,1,12,1,15,1,12,1,15,1,2,5,5,1,9,7,2,1,3,1,5,1,9,1,8,1,3,1,5,1,9,1,8,1,3,1,5,1,9,1,8,1,3,13,3,1,8,1,9,1,5,1,3,1,8,11,5,1,1,5,22,1,1,1,1,1,1,1,22,1,1,1,1,1,1,1,22,1,1,1,1,1,1,1,22,13,18,1,1,1,1,1,5,1,16,5,1,1,5,1,16,1,1,1,3,1,5,1,16,1,1,11,16,1,5,1,22,7,6
				`@ -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