advent-of-code/2019
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity

Compare commits

base: advent-of-code:dev/18
Branches Tags
advent-of-code:main advent-of-code:dev/24 advent-of-code:dev/21 advent-of-code:dev/20 advent-of-code:dev/19 advent-of-code:dev/18 advent-of-code:dev/17 advent-of-code:dev/15 advent-of-code:dev/14
..
compare: advent-of-code:dev/15
Branches Tags
advent-of-code:main advent-of-code:dev/24 advent-of-code:dev/21 advent-of-code:dev/20 advent-of-code:dev/19 advent-of-code:dev/18 advent-of-code:dev/17 advent-of-code:dev/15 advent-of-code:dev/14

15 Commits
dev/18 ... dev/15

Author SHA1 Message Date
Parnic
ce6e63b5b6 Day 15 Part 2 
Well...that turned out easier than I 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).
 2022-06-13 08:31:43 -05:00
Parnic
d41aa6cfa5 Day 15 part 1 
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 do it all at once.

Part 2 might be able to use the right-hand exploration rule since it has the full map, maybe...possibly a pathfinding/A* type solution, but the problem is finding the "goal" location (furthest point from the oxygen system) itself, so I'm not sure if those will work. My current plan is to either try right-hand wall walking or some sort of breadth-first tree system to plot all distances from the oxygen system, then take the furthest one as the answer.

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 came to a version of it myself.
 2022-06-13 00:01:50 -05:00
Parnic
b5202b28c5 Allow intcode programs to be halted externally 
This is simplest to do during an input or output callback, but could potentially also be done to a program running on a goroutine.
 2022-06-12 23:49:13 -05:00
Parnic
0a249b85fc Use varargs for GetPermutations 2022-06-12 23:48:14 -05:00
Parnic
f03184d4c4 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-12 13:37:38 -05:00
Parnic
c15d206b8b 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-12 13:37:38 -05:00
Parnic
43d9a77d62 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-12 13:37:38 -05:00
Parnic
b903417c06 Day 11 solution 2022-06-12 13:37:37 -05:00
Parnic
9dd39aa193 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-12 13:37:37 -05:00
Parnic
3b3c805997 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-12 13:37:37 -05:00
Parnic
3ca7312e2c 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-12 13:37:37 -05:00
Parnic
bb00808f99 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-12 13:37:37 -05:00
Parnic
11b73ba5bc 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-12 13:37:37 -05:00
Parnic
d7db069031 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-12 13:37:36 -05:00
Parnic
870abdf579 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-12 13:37:36 -05:00
30 changed files with 12 additions and 1056 deletions
Expand all files Collapse all files

4
days/05.go
View File

@ -169,7 +169,7 @@ func (d *Day05) Part1() string {
} }
}) })
return fmt.Sprintf("Diagnostic code: %s%d%s", utilities.TextBold, diagCode, utilities.TextReset) return fmt.Sprintf("Diagnostic code: %d", diagCode)
} }
func (d *Day05) Part2() string { func (d *Day05) Part2() string {
@ -184,5 +184,5 @@ func (d *Day05) Part2() string {
diagCode = val diagCode = val
}) })
return fmt.Sprintf("Diagnostic code: %s%d%s", utilities.TextBold, diagCode, utilities.TextReset) return fmt.Sprintf("Diagnostic code: %d", diagCode)
} }

4
days/08.go
View File

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

4
days/11.go
View File

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

4
days/14.go
View File

@ -98,7 +98,7 @@ func (d *Day14) getOreRequiredForFuel(qty int64) int64 {
func (d *Day14) Part1() string { func (d *Day14) Part1() string {
neededOre := d.getOreRequiredForFuel(1) neededOre := d.getOreRequiredForFuel(1)
return fmt.Sprintf("Minimum ore to produce 1 FUEL: %s%d%s", u.TextBold, neededOre, u.TextReset) return fmt.Sprintf("%s%d%s", u.TextBold, neededOre, u.TextReset)
} }
func (d *Day14) Part2() string { func (d *Day14) Part2() string {
@ -125,5 +125,5 @@ func (d *Day14) Part2() string {
fuelProduced += adjustment fuelProduced += adjustment
} }
return fmt.Sprintf("Maximum fuel we can make from 1 trillion ore: %s%d%s", u.TextBold, lastSuccess, u.TextReset) return fmt.Sprintf("%s%d%s", u.TextBold, lastSuccess, u.TextReset)
} }

2
days/15.go
View File

@ -328,5 +328,5 @@ func (d *Day15) Part2() string {
cellDistances := u.MapValues(distanceMap) cellDistances := u.MapValues(distanceMap)
sort.Slice(cellDistances, func(i, j int) bool { return cellDistances[i] > cellDistances[j] }) sort.Slice(cellDistances, func(i, j int) bool { return cellDistances[i] > cellDistances[j] })
return fmt.Sprintf("Time to fill the area with oxygen: %s%d%s minutes", u.TextBold, cellDistances[0], u.TextReset) return fmt.Sprintf("%s%d%s", u.TextBold, cellDistances[0], u.TextReset)
} }

104
days/16.go
View File

@ -1,104 +0,0 @@
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)
}

422
days/17.go
View File

@ -1,422 +0,0 @@
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)
}

345
days/18.go
View File

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

2
go.mod
View File

@ -1,5 +1,3 @@
module parnic.com/aoc2019 module parnic.com/aoc2019
go 1.18 go 1.18
require github.com/edwingeng/deque/v2 v2.0.1

2
go.sum
View File

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

2
inputs/15p.txt
View File

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

1
inputs/16p.txt
View File

@ -1 +0,0 @@
59791875142707344554745984624833270124746225787022156176259864082972613206097260696475359886661459314067969858521185244807128606896674972341093111690401527976891268108040443281821862422244152800144859031661510297789792278726877676645835805097902853584093615895099152578276185267316851163313487136731134073054989870018294373731775466754420075119913101001966739563592696702233028356328979384389178001923889641041703308599918672055860556825287836987992883550004999016194930620165247185883506733712391462975446192414198344745434022955974228926237100271949068464343172968939069550036969073411905889066207300644632441054836725463178144030305115977951503567

1
inputs/16s1.txt
View File

@ -1 +0,0 @@
12345678

1
inputs/16s2.txt
View File

@ -1 +0,0 @@
80871224585914546619083218645595

1
inputs/16s3.txt
View File

@ -1 +0,0 @@
19617804207202209144916044189917

1
inputs/16s4.txt
View File

@ -1 +0,0 @@
69317163492948606335995924319873

1
inputs/17p.txt
View File

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

81
inputs/18p.txt
View File

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

3
inputs/18s1.txt
View File

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

5
inputs/18s2.txt
View File

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

5
inputs/18s3.txt
View File

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

9
inputs/18s4.txt
View File

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

6
inputs/18s5.txt
View File

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

7
inputs/18s6.txt
View File

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

7
inputs/18s7.txt
View File

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

7
inputs/18s8.txt
View File

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

9
inputs/18s9.txt
View File

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

3
main.go
View File

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

10
utilities/map.go
View File

@ -15,13 +15,3 @@ func MapValues[T comparable, U any](m map[T]U) []U {
} }
return r 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
}

15
utilities/vector.go
View File

@ -13,8 +13,6 @@ type Vec3[T Number] struct {
Z T Z T
} }
type Vec2i Vec2[int]
func (v Vec2[T]) Dot(other Vec2[T]) T { func (v Vec2[T]) Dot(other Vec2[T]) T {
return (v.X * other.X) + (v.Y * other.Y) return (v.X * other.X) + (v.Y * other.Y)
} }
@ -44,16 +42,11 @@ func (v Vec2[T]) Equals(other Vec2[T]) bool {
v.Y == other.Y 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] { func VecBetween[T Number](a, b Vec2[T]) Vec2[T] {
return a.To(b) return Vec2[T]{
} X: a.X - b.X,
Y: a.Y - b.Y,
func ManhattanDistance[T Number](a, b Vec2[T]) T { }
return a.ManhattanDistance(b)
} }
func (v Vec3[T]) Dot(other Vec3[T]) T { func (v Vec3[T]) Dot(other Vec3[T]) T {