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

Compare commits

base: advent-of-code:dev/24
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/19
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

11 Commits
dev/24 ... dev/19

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
28 changed files with 23 additions and 1514 deletions
Expand all files Collapse all files

6
days/17.go
View File

@ -48,7 +48,6 @@ type Day17 struct {
func (d *Day17) Parse() { func (d *Day17) Parse() {
d.program = u.LoadIntcodeProgram("17p") d.program = u.LoadIntcodeProgram("17p")
// d.program.SetDebugASCIIPrint(true)
} }
func (d Day17) Num() int { func (d Day17) Num() int {
@ -389,8 +388,9 @@ func (d *Day17) Part2() string {
row := 0 row := 0
var outputState int var outputState int
var lastOutput int64 var lastOutput int64
var instructionStr string
d.program.RunIn(func(inputStep int) int64 { d.program.RunIn(func(inputStep int) int64 {
panic("unexpected read") return int64(instructionStr[inputStep-1])
}, func(val int64, state u.IntcodeProgramState) { }, func(val int64, state u.IntcodeProgramState) {
rVal := rune(val) rVal := rune(val)
if outputState == 0 { if outputState == 0 {
@ -401,7 +401,7 @@ func (d *Day17) Part2() string {
if rVal == '\n' && lastOutput == '\n' { if rVal == '\n' && lastOutput == '\n' {
if outputState == 0 { if outputState == 0 {
d.program.FeedInputString(beforeGrid.solvePath(beforeBotLocation, beforeBotFacing)) instructionStr = beforeGrid.solvePath(beforeBotLocation, beforeBotFacing)
} }
outputState++ outputState++
row = 0 row = 0

12
days/18.go
View File

@ -6,6 +6,7 @@ import (
"math" "math"
"strings" "strings"
"github.com/edwingeng/deque/v2"
u "parnic.com/aoc2019/utilities" u "parnic.com/aoc2019/utilities"
) )
@ -119,15 +120,14 @@ func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, g
return retAdjacent return retAdjacent
} }
queue := make([]u.Pair[int, day18Vec], 0) queue := deque.NewDeque[u.Pair[int, day18Vec]]()
visited := make(map[day18Vec]bool) visited := make(map[day18Vec]bool)
for _, adjacent := range getAdjacent(inPos) { for _, adjacent := range getAdjacent(inPos) {
queue = append(queue, u.Pair[int, day18Vec]{First: 1, Second: adjacent}) queue.PushBack(u.Pair[int, day18Vec]{First: 1, Second: adjacent})
} }
for len(queue) > 0 { for !queue.IsEmpty() {
next := queue[0] next := queue.PopFront()
queue = queue[1:]
if _, exists := visited[next.Second]; !exists { if _, exists := visited[next.Second]; !exists {
visited[next.Second] = true visited[next.Second] = true
@ -157,7 +157,7 @@ func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, g
for _, neighbor := range getAdjacent(next.Second) { for _, neighbor := range getAdjacent(next.Second) {
if _, exists := visited[neighbor]; !exists { if _, exists := visited[neighbor]; !exists {
queue = append(queue, u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor}) queue.PushBack(u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
} }
} }
} }

24
days/19.go
View File

@ -77,7 +77,6 @@ func (d *Day19) Part2() string {
} }
// find lower bound // find lower bound
// this may not be necessary, but helps seed the bisect with a known-good lower bound
startY := 0 startY := 0
startX := 0 startX := 0
for y := 1; startY == 0; y++ { for y := 1; startY == 0; y++ {
@ -92,12 +91,9 @@ func (d *Day19) Part2() string {
lastGoodX := 0 lastGoodX := 0
threshold := 1 threshold := 1
// add 100 to start y since we know it has to be a 100x100 square.
// since we multiply x by 10,000 for the final result, that tells us y cannot be 10k+
y := u.Bisect(startY+100, 9999, threshold, func(y int) bool { y := u.Bisect(startY+100, 9999, threshold, func(y int) bool {
foundX := false foundX := false
for x := startX; ; x++ { for x := startX; ; x++ {
// check top left
if !f(x, y) { if !f(x, y) {
if !foundX { if !foundX {
continue continue
@ -109,38 +105,18 @@ func (d *Day19) Part2() string {
foundX = true foundX = true
} }
// check top right
if !f(x+99, y) { if !f(x+99, y) {
return true return true
} }
// check bottom left
if !f(x, y+99) { if !f(x, y+99) {
continue continue
} }
// we believe the corners work, so run final validations on the full borders.
// this may not be necessary, but i've seen some rows end up shorter than a
// previous row because of the angle of the beam and our integer fidelity.
// plus it's really not that much more expensive to do to be certain we're correct.
for y2 := y; y2 < y+100; y2++ {
// right wall
if !f(x+99, y2) {
return true
}
// left wall
if !f(x, y2) {
return true
}
}
lastGoodX = x lastGoodX = x
return false return false
} }
}) })
// since we invert our bisect success returns, we need to increment y to
// tip back over into the "success" range
y += threshold
result := (lastGoodX * 10000) + y 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) return fmt.Sprintf("Closest 100x100 square for the ship starts at %d,%d = %s%d%s", lastGoodX, y, u.TextBold, result, u.TextReset)
} }

398
days/20.go
View File

@ -1,398 +0,0 @@
package days
import (
"container/heap"
"fmt"
"math"
"strings"
u "parnic.com/aoc2019/utilities"
)
type day20Cell int8
type day20Graph map[day20Portal][]u.Pair[day20Portal, int]
const (
day20CellWall day20Cell = iota
day20CellPath
day20CellDonutHole
)
var (
day20AdjacentOffsets = []u.Vec2i{
{X: -1, Y: 0},
{X: 1, Y: 0},
{X: 0, Y: -1},
{X: 0, Y: 1},
}
entrancePortal = day20Portal{name: "AA"}
exitPortal = day20Portal{name: "ZZ"}
)
type day20Portal struct {
name string
inner bool
depth int
}
type Day20 struct {
grid [][]day20Cell
entrance u.Vec2i
exit u.Vec2i
portals map[day20Portal]u.Vec2i
portalNames []string
}
func (d *Day20) Parse() {
d.portals = make(map[day20Portal]u.Vec2i)
d.portalNames = make([]string, 0)
lines := u.GetStringLines("20p")
d.grid = make([][]day20Cell, len(lines)-4)
currPortal := strings.Builder{}
for row, line := range lines {
y := row - 2
isGridRow := row >= 2 && row < len(lines)-2
if isGridRow {
d.grid[y] = make([]day20Cell, len(line)-4)
}
for col, ch := range lines[row] {
x := col - 2
isGridCol := col >= 2 && col < len(line)-2
if isGridRow && isGridCol {
if ch == '#' {
d.grid[y][x] = day20CellWall
} else if ch == '.' {
d.grid[y][x] = day20CellPath
} else {
d.grid[y][x] = day20CellDonutHole
}
}
if ch >= 'A' && ch <= 'Z' {
portalX := 0
portalY := 0
if len(line) > col+1 && line[col+1] >= 'A' && line[col+1] <= 'Z' {
currPortal.WriteRune(ch)
currPortal.WriteRune(rune(line[col+1]))
if len(line) > col+2 && line[col+2] == '.' {
portalY = y
portalX = x + 2
} else if col-1 >= 0 && line[col-1] == '.' {
portalY = y
portalX = x - 1
} else {
panic("!")
}
} else if len(lines) > row+1 && lines[row+1][col] >= 'A' && lines[row+1][col] <= 'Z' {
currPortal.WriteRune(ch)
currPortal.WriteRune(rune(lines[row+1][col]))
if len(lines) > row+2 && lines[row+2][col] == '.' {
portalY = y + 2
portalX = x
} else if row-1 >= 0 && lines[row-1][col] == '.' {
portalY = y - 1
portalX = x
} else {
panic("!")
}
}
if currPortal.Len() == 2 {
portalName := currPortal.String()
portalVec := u.Vec2i{X: portalX, Y: portalY}
if portalName == entrancePortal.name {
d.entrance = portalVec
} else if portalName == exitPortal.name {
d.exit = portalVec
} else {
portal := day20Portal{
name: portalName,
inner: !d.isOuterPortal(portalVec),
}
d.portals[portal] = portalVec
u.AddToArray(&d.portalNames, portalName)
}
currPortal.Reset()
}
}
}
}
}
func (d Day20) Num() int {
return 20
}
func (d Day20) isPortal(vec u.Vec2i) (bool, int) {
if d.grid[vec.Y][vec.X] != day20CellPath {
return false, 0
}
for i, name := range d.portalNames {
p, exists := d.portals[day20Portal{name: name, inner: !d.isOuterPortal(vec)}]
if exists && vec == p {
return true, i
}
}
return false, 0
}
func (d Day20) Draw() {
for y := range d.grid {
for x := range d.grid[y] {
switch d.grid[y][x] {
case day20CellWall:
fmt.Print("█")
case day20CellDonutHole:
fmt.Print(" ")
case day20CellPath:
posVec := u.Vec2i{X: x, Y: y}
if posVec == d.entrance {
fmt.Print("@")
} else if posVec == d.exit {
fmt.Print("!")
} else {
isPortal, portalIdx := d.isPortal(posVec)
if isPortal {
ch := 'a' + portalIdx
if ch > 'z' {
ch = 'A' + (portalIdx - 26)
}
fmt.Printf("%c", ch)
} else {
fmt.Print(" ")
}
}
}
}
fmt.Println()
}
}
func (d Day20) isOuterPortal(pos u.Vec2i) bool {
return pos.X == 0 || pos.Y == 0 || pos.X == len(d.grid[0])-1 || pos.Y == len(d.grid)-1
}
func (d Day20) findAdjacentCells(inPos u.Vec2i) []u.Pair[day20Portal, int] {
found := make([]u.Pair[day20Portal, int], 0)
getAdjacent := func(pos u.Vec2i) []u.Vec2i {
retAdjacent := make([]u.Vec2i, 0, len(day20AdjacentOffsets))
for _, off := range day20AdjacentOffsets {
offVec := u.Vec2i{X: pos.X + off.X, Y: pos.Y + off.Y}
if offVec.Y < 0 || offVec.Y >= len(d.grid) || offVec.X < 0 || offVec.X >= len(d.grid[0]) {
continue
}
if d.grid[offVec.Y][offVec.X] != day20CellPath {
continue
}
retAdjacent = append(retAdjacent, offVec)
}
return retAdjacent
}
queue := make([]u.Pair[int, u.Vec2i], 0)
visited := map[u.Vec2i]bool{
inPos: true,
}
for _, adjacent := range getAdjacent(inPos) {
queue = append(queue, u.Pair[int, u.Vec2i]{First: 1, Second: adjacent})
}
for len(queue) > 0 {
next := queue[0]
queue = queue[1:]
if _, exists := visited[next.Second]; !exists {
visited[next.Second] = true
adjacentIsPortal, portalIdx := d.isPortal(next.Second)
if adjacentIsPortal || next.Second == d.entrance || next.Second == d.exit {
var portalName string
if next.Second == d.entrance {
portalName = entrancePortal.name
} else if next.Second == d.exit {
portalName = exitPortal.name
} else {
portalName = d.portalNames[portalIdx]
}
alreadyFound := false
for _, p := range found {
if p.First.name == portalName {
alreadyFound = true
break
}
}
if !alreadyFound {
found = append(found, u.Pair[day20Portal, int]{First: day20Portal{
name: portalName,
inner: !d.isOuterPortal(next.Second),
}, Second: next.First})
continue
}
}
for _, neighbor := range getAdjacent(next.Second) {
if _, exists := visited[neighbor]; !exists {
queue = append(queue, u.Pair[int, u.Vec2i]{First: next.First + 1, Second: neighbor})
}
}
}
}
return found
}
type day20PriorityQueue struct {
distance int
neighbor day20Portal
}
type day20PriorityQueueHeap []day20PriorityQueue
func (h day20PriorityQueueHeap) Len() int { return len(h) }
func (h day20PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
func (h day20PriorityQueueHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *day20PriorityQueueHeap) Push(x any) {
*h = append(*h, x.(day20PriorityQueue))
}
func (h *day20PriorityQueueHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func (d Day20) dijkstra(graph day20Graph, start, end day20Portal, neighborFunc func(inPortal day20Portal) []u.Pair[day20Portal, int]) int {
distance := make(map[day20Portal]int)
ih := day20PriorityQueueHeap{
day20PriorityQueue{
distance: 0,
neighbor: start,
},
}
heap.Init(&ih)
visited := make(map[day20Portal]bool)
for ih.Len() > 0 {
node := heap.Pop(&ih).(day20PriorityQueue)
if node.neighbor == end {
return node.distance
}
if _, exists := visited[node.neighbor]; exists {
continue
}
visited[node.neighbor] = true
for _, p := range neighborFunc(node.neighbor) {
if _, exists := visited[p.First]; exists {
continue
}
newDistance := node.distance + p.Second
if dist, exists := distance[p.First]; !exists || newDistance < dist {
distance[p.First] = newDistance
heap.Push(&ih, day20PriorityQueue{
distance: newDistance,
neighbor: p.First,
})
}
}
}
return math.MaxInt
}
func (d Day20) buildGraph() day20Graph {
graph := make(day20Graph, len(d.portals)+1)
adjacent := d.findAdjacentCells(d.entrance)
graph[entrancePortal] = adjacent
for portal, portalVec := range d.portals {
adjacent = d.findAdjacentCells(portalVec)
graph[portal] = adjacent
}
return graph
}
func (d Day20) getDepthNeighbors(graph day20Graph, portal day20Portal) []u.Pair[day20Portal, int] {
basePortal := portal
basePortal.depth = 0
baseNeighbors := graph[basePortal]
neighbors := make([]u.Pair[day20Portal, int], 0)
if portal.inner {
n := day20Portal{name: portal.name, inner: false, depth: portal.depth + 1}
neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: 1})
}
if portal.depth == 0 {
for _, i := range baseNeighbors {
if i.First.inner || i.First.name == entrancePortal.name || i.First.name == exitPortal.name {
neighbors = append(neighbors, u.Pair[day20Portal, int]{First: i.First, Second: i.Second})
}
}
} else {
if !portal.inner {
n := day20Portal{name: portal.name, inner: true, depth: portal.depth - 1}
neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: 1})
}
for _, i := range baseNeighbors {
if i.First.name != entrancePortal.name && i.First.name != exitPortal.name {
n := day20Portal{name: i.First.name, inner: i.First.inner, depth: portal.depth}
neighbors = append(neighbors, u.Pair[day20Portal, int]{First: n, Second: i.Second})
}
}
}
return neighbors
}
func (d *Day20) Part1() string {
// d.Draw()
graph := d.buildGraph()
for portal, adjacent := range graph {
if portal.name == entrancePortal.name {
continue
}
graph[portal] = append(adjacent, u.Pair[day20Portal, int]{First: day20Portal{name: portal.name, inner: !portal.inner}, Second: 1})
}
distance := d.dijkstra(graph, entrancePortal, exitPortal, func(inPortal day20Portal) []u.Pair[day20Portal, int] { return graph[inPortal] })
return fmt.Sprintf("Steps to traverse maze: %s%d%s", u.TextBold, distance, u.TextReset)
}
func (d *Day20) Part2() string {
graph := d.buildGraph()
distance := d.dijkstra(graph, entrancePortal, exitPortal, func(inPortal day20Portal) []u.Pair[day20Portal, int] { return d.getDepthNeighbors(graph, inPortal) })
return fmt.Sprintf("Steps to traverse recursive maze: %s%d%s", u.TextBold, distance, u.TextReset)
}

85
days/21.go
View File

@ -1,85 +0,0 @@
package days
import (
"fmt"
"strings"
u "parnic.com/aoc2019/utilities"
)
type Day21 struct {
program u.IntcodeProgram
}
func (d *Day21) Parse() {
d.program = u.LoadIntcodeProgram("21p")
// d.program.SetDebugASCIIPrint(true)
}
func (d Day21) Num() int {
return 21
}
func (d *Day21) Part1() string {
// if there's any hole up to 3 ahead of us but there's ground where we'd land if we jumped
// (a jump takes 4 spaces), go ahead and jump
cmds := []string{
// check if a hole at 1 or 2 ahead
"NOT A T",
"NOT B J",
// store that result in J
"OR T J",
// check if a hole at 3 ahead
"NOT C T",
// store hole in 1, 2, or 3 in T
"OR J T",
// set J true if hole in 1, 2, or 3
"OR T J",
// set J true if also no hole at 4 ahead
"AND D J",
"WALK",
}
instructionStr := strings.Join(cmds, "\n") + "\n"
d.program.FeedInputString(instructionStr)
res := d.program.Run()
return fmt.Sprintf("Hull damage value when walking: %s%d%s", u.TextBold, res, u.TextReset)
}
func (d *Day21) Part2() string {
// @
// #####.#.##.##.###
// ABCDEFGHI
// using the first program, this kills us. if we jump, we land at D and H becomes our new D, so it won't jump again.
// but if we waited to jump until we got one more ahead, we'd be ok.
// so now we want to know essentially the same thing as part 1, but also if our multiple (immediate second jump) would be successful.
// in problem terms, that's: if there's a hole at 1 or 2 ahead, and there's a hole at C with ground at H, and there's ground at D.
// so now for the above example we'd wait to jump until here:
// @
// #####.#.##.##.###
// ABCDEFGHI
// and all will be well.
cmds := []string{
// check if a hole at 1 or 2 ahead
"NOT A J",
"NOT B T",
// store that result in J
"OR T J",
// check if a hole at 3 ahead...
"NOT C T",
// and ground at 8 ahead (so we can immediately jump again if needed)...
"AND H T",
// combine those into J
"OR T J",
// and ensure we also still have a place to land if we jumped right away
"AND D J",
"RUN",
}
instructionStr := strings.Join(cmds, "\n") + "\n"
d.program.FeedInputString(instructionStr)
res := d.program.Run()
return fmt.Sprintf("Hull damage value when running: %s%d%s", u.TextBold, res, u.TextReset)
}

155
days/22.go
View File

@ -1,155 +0,0 @@
package days
import (
"fmt"
"math"
"math/big"
"strconv"
"strings"
u "parnic.com/aoc2019/utilities"
)
type day22Instruction int
const (
day22InstructionNewStack day22Instruction = iota
day22InstructionCut
day22InstructionDealIncrement
)
type day22Shuffle struct {
instruction day22Instruction
arg int
}
type Day22 struct {
shuffles []day22Shuffle
}
func (d *Day22) Parse() {
lines := u.GetStringLines("22p")
d.shuffles = make([]day22Shuffle, len(lines))
for idx, line := range lines {
split := strings.Split(line, " ")
if split[0] == "deal" {
if split[1] == "into" {
d.shuffles[idx] = day22Shuffle{instruction: day22InstructionNewStack}
} else if split[1] == "with" {
arg, err := strconv.Atoi(split[3])
if err != nil {
panic(err)
}
d.shuffles[idx] = day22Shuffle{
instruction: day22InstructionDealIncrement,
arg: arg,
}
}
} else if split[0] == "cut" {
arg, err := strconv.Atoi(split[1])
if err != nil {
panic(err)
}
d.shuffles[idx] = day22Shuffle{
instruction: day22InstructionCut,
arg: arg,
}
}
}
}
func (d Day22) Num() int {
return 22
}
func (d Day22) applyShuffle(s day22Shuffle, stack, scratch []int) {
switch s.instruction {
case day22InstructionNewStack:
for i := 0; i < len(stack)/2; i++ {
stack[i], stack[len(stack)-1-i] = stack[len(stack)-1-i], stack[i]
}
// there's probably a way to do these two in place...
case day22InstructionCut:
absArg := int(math.Abs(float64(s.arg)))
for i, v := range stack {
if s.arg > 0 {
if i < absArg {
scratch[len(scratch)-absArg+i] = v
} else {
scratch[i-absArg] = v
}
} else {
if i < absArg {
scratch[i] = stack[len(stack)-absArg+i]
} else {
scratch[i] = stack[i-absArg]
}
}
}
copy(stack, scratch)
case day22InstructionDealIncrement:
for i, v := range stack {
scratch[(i*s.arg)%len(stack)] = v
}
copy(stack, scratch)
}
}
func (d *Day22) Part1() string {
deckSize := 10007
// deckSize := 10
stack := make([]int, deckSize)
for i := range stack {
stack[i] = i
}
scratch := make([]int, len(stack))
for _, s := range d.shuffles {
d.applyShuffle(s, stack, scratch)
}
pos := -1
for i, v := range stack {
if v == 2019 {
pos = i
break
}
}
return fmt.Sprintf("Card 2019 is at position %s%d%s", u.TextBold, pos, u.TextReset)
}
func (d *Day22) Part2() string {
n, iter := big.NewInt(119315717514047), big.NewInt(101741582076661)
offset, increment := big.NewInt(0), big.NewInt(1)
for _, s := range d.shuffles {
switch s.instruction {
case day22InstructionNewStack:
increment.Mul(increment, big.NewInt(-1))
offset.Add(offset, increment)
case day22InstructionCut:
offset.Add(offset, big.NewInt(0).Mul(big.NewInt(int64(s.arg)), increment))
case day22InstructionDealIncrement:
increment.Mul(increment, big.NewInt(0).Exp(big.NewInt(int64(s.arg)), big.NewInt(0).Sub(n, big.NewInt(2)), n))
}
}
finalIncr := big.NewInt(0).Exp(increment, iter, n)
finalOffs := big.NewInt(0).Exp(increment, iter, n)
finalOffs.Sub(big.NewInt(1), finalOffs)
invmod := big.NewInt(0).Exp(big.NewInt(0).Sub(big.NewInt(1), increment), big.NewInt(0).Sub(n, big.NewInt(2)), n)
finalOffs.Mul(finalOffs, invmod)
finalOffs.Mul(finalOffs, offset)
answer := big.NewInt(0).Mul(big.NewInt(2020), finalIncr)
answer.Add(answer, finalOffs)
answer.Mod(answer, n)
return fmt.Sprintf("Card at position 2020: %s%d%s", u.TextBold, answer, u.TextReset)
}

170
days/23.go
View File

@ -1,170 +0,0 @@
package days
import (
"fmt"
"sync"
u "parnic.com/aoc2019/utilities"
)
type day23Computer struct {
program u.IntcodeProgram
id int
packetQueue chan u.Vec2[int64]
outputStep int
nextPacketDest int
sendingPacket u.Vec2[int64]
hasQueuedPacket bool
lastReceivedPacket u.Vec2[int64]
idle bool
}
func (d Day23) makeComputer(id int) *day23Computer {
c := &day23Computer{
program: d.program.Copy(),
id: id,
packetQueue: make(chan u.Vec2[int64]),
idle: true,
}
return c
}
type Day23 struct {
program u.IntcodeProgram
}
func (d *Day23) Parse() {
d.program = u.LoadIntcodeProgram("23p")
}
func (d Day23) Num() int {
return 23
}
func (d Day23) initComputers() []*day23Computer {
computers := make([]*day23Computer, 50)
for i := range computers {
computers[i] = d.makeComputer(i)
}
return computers
}
func (d Day23) execComputers(computers []*day23Computer, nat chan u.Vec2[int64]) *sync.WaitGroup {
wg := &sync.WaitGroup{}
wg.Add(len(computers))
for _, c := range computers {
go func(c *day23Computer) {
bootedUp := false
c.program.RunIn(func(inputStep int) int64 {
if !bootedUp {
bootedUp = true
return int64(c.id)
}
if c.hasQueuedPacket {
// fmt.Printf(" %d finished processing packet %v\n", c.id, c.lastReceivedPacket)
c.hasQueuedPacket = false
return c.lastReceivedPacket.Y
}
select {
case c.lastReceivedPacket = <-c.packetQueue:
// fmt.Printf("computer %d received packet %v\n", c.id, packet)
c.hasQueuedPacket = true
return c.lastReceivedPacket.X
default:
c.idle = true
return -1
}
}, func(val int64, state u.IntcodeProgramState) {
c.idle = false
switch c.outputStep {
case 0:
c.nextPacketDest = int(val)
case 1:
c.sendingPacket.X = val
case 2:
c.sendingPacket.Y = val
if c.nextPacketDest == 255 {
// fmt.Printf("computer %d sending %v to 255\n", c.id, c.sendingPacket)
nat <- c.sendingPacket
} else {
// fmt.Printf("computer %d sending %v to computer %d\n", c.id, c.sendingPacket, c.nextPacketDest)
computers[c.nextPacketDest].packetQueue <- c.sendingPacket
}
}
c.outputStep = (c.outputStep + 1) % 3
})
wg.Done()
}(c)
}
return wg
}
func (d *Day23) Part1() string {
computers := d.initComputers()
natChan := make(chan u.Vec2[int64])
wg := d.execComputers(computers, natChan)
answer := <-natChan
for _, c := range computers {
c.program.Stop()
}
// not really necessary, but let's make sure they all shut down in case
// we're running all days at once
wg.Wait()
return fmt.Sprintf("First packet sent to 255 Y value: %s%d%s", u.TextBold, answer.Y, u.TextReset)
}
func (d *Day23) Part2() string {
computers := d.initComputers()
natChan := make(chan u.Vec2[int64])
wg := d.execComputers(computers, natChan)
answerChan := make(chan int64)
go func() {
var currVal u.Vec2[int64]
var lastVal u.Vec2[int64]
hasReceived := false
for {
select {
case currVal = <-natChan:
hasReceived = true
default:
}
allIdle := true
for _, c := range computers {
if !c.idle {
allIdle = false
break
}
}
if allIdle && hasReceived {
// fmt.Printf("all idle, sending %v to computer 0\n", currVal)
if lastVal.Y == currVal.Y {
// fmt.Printf("found answer? %d\n", currVal.Y)
answerChan <- currVal.Y
}
computers[0].packetQueue <- currVal
lastVal = currVal
}
}
}()
answer := <-answerChan
for _, c := range computers {
c.program.Stop()
}
wg.Wait()
return fmt.Sprintf("First Y value sent to the NAT twice in a row: %s%d%s", u.TextBold, answer, u.TextReset)
}

289
days/24.go
View File

@ -1,289 +0,0 @@
package days
import (
"fmt"
"math"
u "parnic.com/aoc2019/utilities"
)
var (
day24AdjacentOffsets = []u.Vec2i{
{X: -1, Y: 0},
{X: 1, Y: 0},
{X: 0, Y: -1},
{X: 0, Y: 1},
}
)
type Day24 struct {
grid [][]bool
}
func (d *Day24) Parse() {
lines := u.GetStringLines("24p")
d.grid = make([][]bool, len(lines))
for i, line := range lines {
d.grid[i] = make([]bool, len(line))
for j, ch := range line {
d.grid[i][j] = ch == '#'
}
}
}
func (d Day24) Num() int {
return 24
}
func (d Day24) calcActivatedNeighbors(grid [][]bool, i, j int) int {
activatedNeighbors := 0
for _, o := range day24AdjacentOffsets {
newI := i + o.X
newJ := j + o.Y
if newI < 0 || newI >= len(grid) || newJ < 0 || newJ >= len(grid[i]) {
continue
}
if grid[newI][newJ] {
activatedNeighbors++
}
}
return activatedNeighbors
}
func (d Day24) recursiveCalcActivatedNeighbors(gridMap map[int][][]bool, mapIdx, i, j int) int {
activatedNeighbors := 0
numNeighbors := 0
thisGrid := gridMap[mapIdx]
for _, o := range day24AdjacentOffsets {
newI := i + o.X
newJ := j + o.Y
if newI < 0 || newI >= len(thisGrid) || newJ < 0 || newJ >= len(thisGrid[i]) {
continue
}
if newI == 2 && newJ == 2 {
continue
}
numNeighbors++
if thisGrid[newI][newJ] {
activatedNeighbors++
}
}
checkLower := (i == 1 && j == 2) ||
(i == 2 && (j == 1 || j == 3)) ||
(i == 3 && j == 2)
if checkLower {
if lowerGrid, exists := gridMap[mapIdx+1]; exists {
if i == 1 {
for _, b := range lowerGrid[0] {
numNeighbors++
if b {
activatedNeighbors++
}
}
} else if i == 2 {
if j == 1 {
for _, r := range lowerGrid {
numNeighbors++
if r[0] {
activatedNeighbors++
}
}
} else if j == 3 {
for _, r := range lowerGrid {
numNeighbors++
if r[len(lowerGrid[0])-1] {
activatedNeighbors++
}
}
}
} else if i == 3 {
for _, b := range lowerGrid[len(lowerGrid)-1] {
numNeighbors++
if b {
activatedNeighbors++
}
}
}
}
}
checkUpper := (i == 0) || (i == len(thisGrid)-1) ||
((i != 0 && i != len(thisGrid)) && (j == 0 || j == len(thisGrid[0])-1))
if checkUpper {
if upperGrid, exists := gridMap[mapIdx-1]; exists {
if i == 0 {
numNeighbors++
if upperGrid[1][2] {
activatedNeighbors++
}
} else if i == len(thisGrid)-1 {
numNeighbors++
if upperGrid[3][2] {
activatedNeighbors++
}
}
if j == 0 {
numNeighbors++
if upperGrid[2][1] {
activatedNeighbors++
}
} else if j == len(thisGrid[0])-1 {
numNeighbors++
if upperGrid[2][3] {
activatedNeighbors++
}
}
}
}
return activatedNeighbors
}
func (d Day24) calcRating(grid [][]bool) int {
rating := 0
for i, r := range grid {
for j := range r {
pow := (i * len(r)) + j
if grid[i][j] {
result := int(math.Pow(2, float64(pow)))
rating += result
}
}
}
return rating
}
func (d Day24) numBugs(gridMap map[int][][]bool) int {
ret := 0
for _, v := range gridMap {
for _, r := range v {
for _, b := range r {
if b {
ret++
}
}
}
}
return ret
}
func copy2d[T comparable](dest [][]T, src [][]T) {
for i, r := range src {
copy(dest[i], r)
}
}
func (d Day24) Draw(grid [][]bool) {
for _, r := range grid {
for _, c := range r {
if c {
fmt.Print("#")
} else {
fmt.Print(".")
}
}
fmt.Println()
}
fmt.Println()
}
func (d *Day24) Part1() string {
grid := make([][]bool, len(d.grid))
scratch := make([][]bool, len(grid))
for i, g := range d.grid {
grid[i] = make([]bool, len(g))
scratch[i] = make([]bool, len(g))
copy(grid[i], d.grid[i])
}
found := false
answer := 0
seenRatings := make([]int, 0)
for i := 1; !found; i++ {
// d.Draw(grid)
for i, r := range grid {
for j := range r {
numActivated := d.calcActivatedNeighbors(grid, i, j)
if grid[i][j] {
scratch[i][j] = numActivated == 1
} else {
scratch[i][j] = numActivated == 1 || numActivated == 2
}
}
}
rating := d.calcRating(scratch)
if u.ArrayContains(seenRatings, rating) {
found = true
// d.Draw(scratch)
answer = rating
}
seenRatings = append(seenRatings, rating)
copy2d(grid, scratch)
}
return fmt.Sprintf("First repeated biodiversity rating is %s%d%s", u.TextBold, answer, u.TextReset)
}
func (d *Day24) Part2() string {
makeGrid := func(initialGrid [][]bool) ([][]bool, [][]bool) {
grid := make([][]bool, len(d.grid))
scratch := make([][]bool, len(grid))
for i, g := range d.grid {
grid[i] = make([]bool, len(g))
scratch[i] = make([]bool, len(g))
if initialGrid != nil {
copy(grid[i], initialGrid[i])
}
}
return grid, scratch
}
gridMap := make(map[int][][]bool)
scratchMap := make(map[int][][]bool)
gridMap[0], scratchMap[0] = makeGrid(d.grid)
min := 0
max := 0
for i := 0; i < 200; i++ {
gridMap[min-1], scratchMap[min-1] = makeGrid(nil)
gridMap[max+1], scratchMap[max+1] = makeGrid(nil)
min, max = min-1, max+1
// if i == 10 {
// keys := u.MapKeys(gridMap)
// sort.Slice(keys, func(i, j int) bool { return keys[i] < keys[j] })
// for _, k := range keys {
// fmt.Println("Depth", k)
// d.Draw(gridMap[k])
// }
// fmt.Println("# bugs:", d.numBugs(gridMap))
// }
for depth, grid := range gridMap {
for i, r := range grid {
for j := range r {
if i == 2 && j == 2 {
continue
}
numActivated := d.recursiveCalcActivatedNeighbors(gridMap, depth, i, j)
if grid[i][j] {
scratchMap[depth][i][j] = numActivated == 1
} else {
scratchMap[depth][i][j] = numActivated == 1 || numActivated == 2
}
}
}
}
for d := range gridMap {
copy2d(gridMap[d], scratchMap[d])
}
}
return fmt.Sprintf("Bugs present after 200 minutes: %s%d%s", u.TextBold, d.numBugs(gridMap), u.TextReset)
}

2
go.mod
View File

@ -1,3 +1,5 @@
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 Normal file
View File

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

2
inputs/19p.txt
View File

@ -1 +1 @@
109,424,203,1,21102,11,1,0,1105,1,282,21101,0,18,0,1105,1,259,2101,0,1,221,203,1,21102,1,31,0,1105,1,282,21102,1,38,0,1105,1,259,20102,1,23,2,21201,1,0,3,21102,1,1,1,21102,57,1,0,1106,0,303,2102,1,1,222,21002,221,1,3,20101,0,221,2,21101,0,259,1,21101,0,80,0,1105,1,225,21101,44,0,2,21102,91,1,0,1105,1,303,1202,1,1,223,21002,222,1,4,21102,259,1,3,21102,1,225,2,21102,225,1,1,21101,118,0,0,1106,0,225,21002,222,1,3,21101,163,0,2,21101,0,133,0,1106,0,303,21202,1,-1,1,22001,223,1,1,21102,148,1,0,1106,0,259,1202,1,1,223,20101,0,221,4,21001,222,0,3,21102,1,24,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,195,0,0,105,1,108,20207,1,223,2,21002,23,1,1,21102,-1,1,3,21102,1,214,0,1106,0,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,2101,0,-4,249,22102,1,-3,1,22101,0,-2,2,22101,0,-1,3,21102,250,1,0,1106,0,225,21202,1,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,2106,0,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,22102,1,-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,21202,-2,1,3,21101,0,343,0,1106,0,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,21101,384,0,0,1105,1,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,21202,1,1,-4,109,-5,2105,1,0 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

113
inputs/20p.txt
View File

@ -1,113 +0,0 @@
G R U E Z S S
W N C K Z G D
#################################.###########.###.#######.#########.#.#######.#####################################
#.#.......#.#.........#.#.#.....#.#.....#.#.#...#.....#.........#.....#...#.#...........#.......#.....#.....#.#...#
#.#####.###.###.###.#.#.#.###.###.#.###.#.#.###.#.###.###.#####.#.###.###.#.###.#########.###.###.#######.###.#.###
#.#.#.#...#...#.#.#.#.................#.#...#...#.#.#...#.#.....#.#.#.#.....................#.#.......#.........#.#
#.#.#.#.###.#####.#########.###########.#.#.#.###.#.#######.###.#.#.#####.###.#.###.#.###.#.###.#######.#######.#.#
#...#...#.#.#.#.........#...#...#.......#.#...#.......#.....#.#.#.....#.....#.#...#.#.#...#.#...#.#.........#.#.#.#
#.#.###.#.#.#.#####.#.#.#######.#.#######.###.#.###.#####.###.#####.#.###.#########.#.#.#######.#.#####.#####.#.#.#
#.#...#.#.#.#.#.....#.#.................#.#...#.#.#.....#...#.#.#...#...#.#.....#.#.#.#...#.#.#...........#.#.....#
###.###.#.#.#.#.#.#####.#.###.#########.#.#######.#.#####.###.#.#.#.#####.#.#.###.#.#######.#.#.###.#######.###.#.#
#...#.......#...#.#.#.#.#...#.#.........#.....#.......#.#.......#.#...#.....#.....#.#...#.........#...#.#.#.#.#.#.#
###.#######.#######.#.###########.#.#####.###.#####.###.#.#####.#.###.#.#.###.#.#######.###.#####.#####.#.#.#.#####
#.......#.#...#.......#.........#.#.#...#.#.#.#.....#.....#...#.#...#.#.#.#...#...#...#...#...#.#.#...........#.#.#
#.#.###.#.#.#########.#########.#.###.###.#.#####.#.###.#.#.#.#.#.###########.#.###.###.###.###.###.###.#.#####.#.#
#.#...#.....#.#...#.#.#.#.#.............#.....#...#...#.#.#.#...#...#.#.#.....#.........#...#.......#...#...#...#.#
###########.#.#.###.#.#.#.#######.#####.#.#####.#.#######.#####.###.#.#.#####.#.#.###.#####.###.#############.#.#.#
#.#.#.#.#.....#.#.....#.#.#.#.....#...#.#.....#.#.....#...#.#.#...#...#.#.#...#.#...#...#...#...#...#.#.......#.#.#
#.#.#.#.###.###.#####.#.#.#.#####.#.###.#.#########.#######.#.#.###.###.#.#.###.###.#####.#####.#.###.#####.#####.#
#.#...#.#...#.#.#...#...#.#.....#.#.....#.#...#.....#.......#.#.#...#.....#.#.#.#.......#.......#...#.#.#...#.#...#
#.#.#.#.###.#.#.###.#.###.#.#####.#.###.#.###.###.###.#.#.###.#.#.###.#.#.###.#.###.#####.#.#####.###.#.###.#.###.#
#.#.#.#.#...#.#...#...#.#.#...#...#...#.#.#.....#.#...#.#.#.....#.#...#.#.#.......#.......#...#.#.....#.........#.#
#.#.###.###.#.#.#####.#.#.#.###.#.#####.#.#.###.#.###.#.###.#.###.#.###.#####.#####.#####.#####.###.#########.#.#.#
#.....#...#.......#.#.#.......#.#.#...#.#...#.#.#.....#...#.#...#...#.#...#.......#...#.#...#...#...#.#.#.#.#.#.#.#
###.###.#######.###.#.#.#.#.#########.#.#####.#.#.#####.#######.#####.#.#####.#.#.###.#.#######.###.#.#.#.#.#.###.#
#.....#...#.#.#.......#.#.#.#.#.......#...#.....#.#.....#.......#.......#.#...#.#.#.#...#.....#.#.....#.#.#...#.#.#
###.###.###.#.#######.#.#####.#####.#.#.###.#########.#.###.#.#####.#####.###.#####.#######.###.###.###.#.#.###.#.#
#.....#.......#...#...#...#.#.#.#.#.#.#.#.......#.#...#.#.#.#...#.......#...#.......#...#.....#...#.#.........#...#
#.#####.#######.###.#.#.###.#.#.#.#.#.#.###.#.###.#.#####.#####.#####.#####.###.#######.###.###.###.#########.#.###
#...#...#...#.#.#...#.#.#.#.........#.....#.#.....#.......#.......#...#.............#...#...#.#.........#...#.#...#
#.###.###.###.#.#####.#.#.#.#####.#############.#######.#####.#####.#######.###########.###.#.###.#######.###.#.###
#...#...#...#...#.#...#...#.# S L B V G R #.#.#.#.....#.#.......#.#...#
#.###.#.#.#####.#.###.#.###.# D M E H X Q #.#.#.#####.#.###.#####.#.###
#.....#.#.................#.# #.........................#.#
#.###.###.#####.#.#.#.###.### #.#.#.###.#######.###.#.#.#.#
#.#.#.....#.#...#.#.#.#.....# RZ..#.#...#.....#.#...#.#.#.#..BE
#.#.#####.#.#####.#.#####.### #######.#####.#.#.#######.#.#
#.....#.#.....#.#.#.....#.#.# #.#.#.#.#.#...#.......#...#.#
###.###.###.#.#.#.#.###.#.#.# #.#.#.###.#####.#.#######.#.#
RI....#.....#.#.#...#.#.#.#....UW #.#.......#...#.#.#.#...#...#
#####.###############.###.### #.###.#####.#.#####.#.#.#####
#.....#.#.#...#.#.....#.#...# GW..........#.#.........#.#...#
#.###.#.#.#.###.###.###.##### #.###.#.#.###.#######.###.###
#...#...#.....#.#.......#....FM #.#...#.#.....#...#.........#
###.###.#.#.#.#.#.#########.# ###.#######.###.###########.#
AJ..#...#...#.#...#...#.....#.# #...#.#.#...#...#.#...#.#.#..GX
#.#.#########.#.#.#######.#.# #####.#.#######.#.###.#.#.###
#.....#.#.#.#.#.............# #...............#...#........DD
#######.#.#.###########.###.# ###.#######.###.#.#.#.#.###.#
#.....................#.#...# #.......#.....#...#.#.#.#...#
###.###.#.#.###.#####.####### #####.#########.###.#.###.###
GP..#...#.#.#.#.....#.#...#...# SG..#...#.....#...#.#.....#...#
#.###.#####.#.#.#.#.###.###.# #.#.###.#.#######.#######.###
#.#.....#.#.#.#.#.#.....#...# #.....#.#.#.#...#.#.#...#.#.#
#.#.#####.#########.#######.# #########.#.###.#.#.#.#####.#
#.....#...#..................SI DD....#........................UW
#.#######.#####.###.###.##### #.###.#####.#.###.#.###.#####
#.#.#...#...#.....#.#.#.#.#..AJ #.........#.#.#.#.#.#.....#.#
###.#.###.#.#########.###.#.# #.#####.###.#.#.#######.###.#
#.........#.#...#.....#.#.#.# #...#.....#.#...#.#.#.#.#....LM
#########.#.###.#.###.#.#.#.# #########.#.#.###.#.#.#####.#
AA......#.#.#.....#.#...#.....# #.#.#.#.#.#.#.#...#.#.#.....#
#.#####.#.#.###.#.#.###.#.### #.#.#.#.#########.#.#.#####.#
JO..........#...#...#.....#...# #.#.......#.#.............#.#
#####.###############.###.#.# #.#.#.#####.###.###.#.###.#.#
#.#.#...#.........#.#.#.#.#.# TX....#.............#.#...#...#
#.#.#######.#.#.#.#.###.###.# #.###.#.###.#####.###########
VH......#.....#.#.#.....#...#.# #.#...#.#...#...#.#.....#...#
#####.#.###########.###.##### #############.#####.###.#.#.#
#.....#.....#.#.......#.....# #.#...#...#.#.......#.#.#.#..RZ
#.#.#######.#.#######.#.##### #.###.###.#.###.#.###.#.#.###
#.#...........#.#............FW RN..#.....#...#.#.#.#.....#...#
#########.###.#.#.########### #.#.#.###.###.###.#.#####.###
#...#...#.#.....#.#.........# #...#.............#.......#.#
#.#.#.#################.#.#.# ###############.###########.#
AX..#...#.#...#.#...#...#.#.#..HR JO............#.#.#...........#
#.#.###.###.#.#.#####.###.#.# #.#.#####.#.#.###.#.#.#####.#
TX..#...#.......#...#.....#.#..EK #.#...#.#.#.......#.#...#.#..MM
###.#.###.#.#.#.#.###.#.#.### #.###.#.#######.#.###.###.#.#
#...#.....#.#...#.....#.....# #.#.#.....#.#...#...#.#.....#
#####.#.#.#####.###.#######.# R Y G U A M S #.#.#.#.###.#####.#.#.###.#.#
#.....#.#...#.....#.....#...# I Q P C X M Y #...#.#.#.....#...#.#...#.#.#
#####.#########.###.#####.###########.#####.###.###########.#####.###########.#.#######.#.###.#.#########.#.#####.#
#...#...#.#.......#.....#...#...#.....#.....#.....#.#.....#...#...........#...#...#...#.#.#.....#.#.......#.#.....#
#.#.#.###.###.#.#.#######.#####.###.###.###.#####.#.###.#.#.#########.#####.#####.#.#########.###.###.#####.###.#.#
#.#.......#...#.#.#.......#.....#.#.#.....#.#.....#...#.#.......#.#.#...#.......#.#.......#.#.#.#.....#.......#.#.#
#.#.#.#.#####.###########.#####.#.#.#.#.#.#####.###.###.#########.#.#.#######.###.#.#######.###.###.#.###.#.#.#.#.#
#.#.#.#...#.......#.......#.........#.#.#.....#.#.....#.........#.........#.#.#.....#.......#.......#.#.#.#.#.#.#.#
#######.#.#.#.#####.#.#########.#############.#.#.###.#######.#####.#.#####.#.#.#######.#####.#.#.###.#.#.#######.#
#.......#.#.#...#...#.#.........#.......#...#.#.....#.#.......#.....#...#.....#...........#.#.#.#.#.....#...#.....#
#.#.#.#####.#.#.#####.#.#######.#.###.###.###.#.###.#.#.###.#.#.#.###.#.#####.#.###.#.#.###.###.#.#.#.#####.#####.#
#.#.#.#.....#.#.#.....#...#.#.....#...#.......#.#...#.#...#.#.#.#...#.#.#.....#.#...#.#.......#.#.#.#...#.#.#.....#
#.###.###.#.###.###.#.#.###.#.#.#.#.###.###.#.#######.###.#.###.#######.#.#.#.#####.#.#.#.#############.#.#####.###
#.#.#.#.#.#...#.#...#.#.#.....#.#.#...#...#.#...#.....#...#...#...#.....#.#.#.....#.#.#.#.#.....#.#.#.......#...#.#
###.#.#.#.#.###.#####.#############.#.#.#.#.#######.###.###.###.#############.#####.#####.###.###.#.#.#####.###.#.#
#.......#.#.#.....#...#.#.......#...#.#.#.#.#.#.#.#...#...#.#.....#.#.#...#.....#.#.#...#...#.......#.....#...#...#
###.###.#.###.#########.#######.#####.#.#####.#.#.#.###.#######.###.#.#.#####.###.#.#.###.###.#####.#.#.###.###.###
#.....#.#.#.....#.....#.#.......#.#.#.#...#.......#.#.......#...#.....#.......#.........#.#.#.....#.#.#.#...#.....#
#.#####.#.###.#.#####.#.#######.#.#.#.#.#######.#.#.###.#####.#.###.#.###.#.#####.###.#####.#.#######.###.#.#.#.###
#.#.....#.#...#...#.......#.#.....#...#.#.#.....#...#.......#.#.....#.#...#...#.#...#...#.#.#.....#.#.#.#.#.#.#...#
#####.#.#.###.#######.#.###.###.#.#.###.#.#####.#######.#######.#.#####.###.###.###.#####.#.#.#####.###.#######.#.#
#.#.#.#.#.#.#.#...#...#...#.#.#.#...#.......#.#.....#.#.#...#...#.....#.#.......#.........#.#...#.#.........#.#.#.#
#.#.#######.#####.#####.###.#.#.#########.###.#####.#.#.#.#######.#########.#.###.#########.###.#.#.#########.#.#.#
#...#.#.#.#.....#.#...................#...#...#...#...#.....#...#.#...#...#.#.#.....#.#.......#.#.#.#.#.#.#...#.#.#
###.#.#.#.#.###.#.#####.#############.###.#.#.#.#.###.#.#.#####.#.#.#####.###.#.###.#.#####.###.#.#.#.#.#.###.#.###
#...........#.#.#...#...#.#.......#.#...#...#.#.#...#.#.#...#.#.......#.....#.#...#.#.#.#.#.....#.....#.#.....#...#
#####.#.#.#.#.###.#####.#.#.#.###.#.#.#######.#.###.#.#.###.#.#####.###.###.#.#.###.#.#.#.#.#####.###.#.#.#########
#.#...#.#.#.............#...#...#...#.....#...#...#...#.#.#.#...#...#...#.#...#.#...................#.............#
#.#####.#######.#.###.###.#.#.#####.#.#######.###.#####.#.###.#.#.#####.#.###.#.#.#####.###.#####.###.#.###.#.#####
#.......#.......#...#...#.#.#.#.........#.....#.....#.......#.#.......#.....#.#.#.....#...#.....#...#.#...#.#.....#
###################################.#######.###.#########.#######.#########.#######.###############################
Y S R S F F H
Q Y Q I M W R

19
inputs/20s1.txt
View File

@ -1,19 +0,0 @@
A
A
#######.#########
#######.........#
#######.#######.#
#######.#######.#
#######.#######.#
##### B ###.#
BC...## C ###.#
##.## ###.#
##...DE F ###.#
##### G ###.#
#########.#####.#
DE..#######...###.#
#.#########.###.#
FG..#########.....#
###########.#####
Z
Z

37
inputs/20s2.txt
View File

@ -1,37 +0,0 @@
A
A
#################.#############
#.#...#...................#.#.#
#.#.#.###.###.###.#########.#.#
#.#.#.......#...#.....#.#.#...#
#.#########.###.#####.#.#.###.#
#.............#.#.....#.......#
###.###########.###.#####.#.#.#
#.....# A C #.#.#.#
####### S P #####.#
#.#...# #......VT
#.#.#.# #.#####
#...#.# YN....#.#
#.###.# #####.#
DI....#.# #.....#
#####.# #.###.#
ZZ......# QG....#..AS
###.### #######
JO..#.#.# #.....#
#.#.#.# ###.#.#
#...#..DI BU....#..LF
#####.# #.#####
YN......# VT..#....QG
#.###.# #.###.#
#.#...# #.....#
###.### J L J #.#.###
#.....# O F P #.#...#
#.###.#####.#.#####.#####.###.#
#...#.#.#...#.....#.....#.#...#
#.#####.###.###.#.#.#########.#
#...#.#.....#...#.#.#.#.....#.#
#.###.#####.###.###.#.#.#######
#.#.........#...#.............#
#########.###.###.#############
B J C
U P P

37
inputs/20s3.txt
View File

@ -1,37 +0,0 @@
Z L X W C
Z P Q B K
###########.#.#.#.#######.###############
#...#.......#.#.......#.#.......#.#.#...#
###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
#.#...#.#.#...#.#.#...#...#...#.#.......#
#.###.#######.###.###.#.###.###.#.#######
#...#.......#.#...#...#.............#...#
#.#########.#######.#.#######.#######.###
#...#.# F R I Z #.#.#.#
#.###.# D E C H #.#.#.#
#.#...# #...#.#
#.###.# #.###.#
#.#....OA WB..#.#..ZH
#.###.# #.#.#.#
CJ......# #.....#
####### #######
#.#....CK #......IC
#.###.# #.###.#
#.....# #...#.#
###.### #.#.#.#
XF....#.# RF..#.#.#
#####.# #######
#......CJ NM..#...#
###.#.# #.###.#
RE....#.# #......RF
###.### X X L #.#.#.#
#.....# F Q P #.#.#.#
###.###########.###.#######.#########.###
#.....#...#.....#.......#...#.....#.#...#
#####.#.###.#######.#######.###.###.#.#.#
#.......#.......#.#.#.#.#...#...#...#.#.#
#####.###.#####.#.#.#.#.###.###.#.###.###
#.......#.....#.#...#...............#...#
#############.#.#.###.###################
A O F N
A A D M

1
inputs/21p.txt
View File

File diff suppressed because one or more lines are too long

100
inputs/22p.txt
View File

@ -1,100 +0,0 @@
deal into new stack
cut -2732
deal into new stack
deal with increment 57
cut 5974
deal into new stack
deal with increment 32
cut -1725
deal with increment 24
cut 6093
deal with increment 6
cut -2842
deal with increment 14
cut 2609
deal with increment 12
cut -6860
deal with increment 51
cut -6230
deal with increment 61
cut 3152
deal with increment 28
cut 2202
deal into new stack
deal with increment 60
cut 433
deal into new stack
cut -6256
deal with increment 13
deal into new stack
cut 8379
deal into new stack
deal with increment 54
cut 1120
deal with increment 16
cut -5214
deal with increment 63
deal into new stack
cut -8473
deal with increment 11
cut 228
deal with increment 45
cut -6755
deal with increment 50
cut -3391
deal with increment 44
cut -1341
deal with increment 28
cut -6788
deal with increment 52
cut 3062
deal with increment 41
cut 4541
deal with increment 57
cut -7962
deal with increment 56
cut 9621
deal with increment 57
cut 3881
deal with increment 36
deal into new stack
deal with increment 45
cut 522
deal with increment 9
deal into new stack
deal with increment 60
deal into new stack
deal with increment 12
cut -9181
deal with increment 63
deal into new stack
deal with increment 14
cut -2906
deal with increment 10
cut 848
deal with increment 75
cut 798
deal with increment 29
cut 1412
deal with increment 10
deal into new stack
cut -5295
deal into new stack
cut 4432
deal with increment 72
cut -7831
deal into new stack
cut 6216
deal into new stack
deal with increment 7
cut -1720
deal into new stack
cut -5465
deal with increment 70
cut -5173
deal with increment 7
cut 3874
deal with increment 65
cut 921
deal with increment 8
cut -3094

3
inputs/22s1.txt
View File

@ -1,3 +0,0 @@
deal with increment 7
deal into new stack
deal into new stack

3
inputs/22s2.txt
View File

@ -1,3 +0,0 @@
cut 6
deal with increment 7
deal into new stack

3
inputs/22s3.txt
View File

@ -1,3 +0,0 @@
deal with increment 7
deal with increment 9
cut -2

10
inputs/22s4.txt
View File

@ -1,10 +0,0 @@
deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1

1
inputs/23p.txt
View File

File diff suppressed because one or more lines are too long

5
inputs/24p.txt
View File

@ -1,5 +0,0 @@
##..#
...##
.#.##
#..#.
..#..

5
inputs/24s1.txt
View File

@ -1,5 +0,0 @@
....#
#..#.
#..##
..#..
#....

5
inputs/24s2.txt
View File

@ -1,5 +0,0 @@
.....
.....
.....
#....
.#...

5
main.go
View File

@ -53,11 +53,6 @@ var dayMap = []day{
&days.Day17{}, &days.Day17{},
&days.Day18{}, &days.Day18{},
&days.Day19{}, &days.Day19{},
&days.Day20{},
&days.Day21{},
&days.Day22{},
&days.Day23{},
&days.Day24{},
} }
func main() { func main() {

6
utilities/bisect.go
View File

@ -12,8 +12,10 @@ import (
// and the failure is less than or equal to the acceptance threshold // and the failure is less than or equal to the acceptance threshold
// (usually 1, for integers). // (usually 1, for integers).
func Bisect[T Number](low, high, threshold T, tryFunc func(val T) bool) T { func Bisect[T Number](low, high, threshold T, tryFunc func(val T) bool) T {
currVal := low
for T(math.Abs(float64(high-low))) > threshold { for T(math.Abs(float64(high-low))) > threshold {
currVal := low + ((high - low) / 2) currVal = low + ((high - low) / 2)
success := tryFunc(currVal) success := tryFunc(currVal)
if success { if success {
low = currVal low = currVal
@ -22,5 +24,5 @@ func Bisect[T Number](low, high, threshold T, tryFunc func(val T) bool) T {
} }
} }
return low return currVal
} }

39
utilities/intcode.go
View File

@ -28,8 +28,6 @@ type IntcodeProgram struct {
program []int64 program []int64
relativeBase int relativeBase int
haltRequested bool haltRequested bool
printASCII bool
feedInput []rune
} }
type IntcodeProgramState struct { type IntcodeProgramState struct {
@ -142,15 +140,14 @@ func (p *IntcodeProgram) Reset() {
p.relativeBase = 0 p.relativeBase = 0
} }
func (p *IntcodeProgram) Run() int64 { func (p *IntcodeProgram) Run() {
return p.RunIn(func(int) int64 { return 0 }, func(int64, IntcodeProgramState) {}) p.RunIn(func(int) int64 { return 0 }, func(int64, IntcodeProgramState) {})
} }
func (p *IntcodeProgram) RunIn(inputFunc ProvideInputFunc, outputFunc ReceiveOutputFunc) int64 { func (p *IntcodeProgram) RunIn(inputFunc ProvideInputFunc, outputFunc ReceiveOutputFunc) {
p.init() p.init()
inputsRequested := 0 inputsRequested := 0
lastOutput := int64(0)
for instructionPointer := 0; instructionPointer < len(p.program) && !p.haltRequested; { for instructionPointer := 0; instructionPointer < len(p.program) && !p.haltRequested; {
instruction := p.GetMemory(instructionPointer) instruction := p.GetMemory(instructionPointer)
instructionPointer++ instructionPointer++
@ -187,28 +184,13 @@ func (p *IntcodeProgram) RunIn(inputFunc ProvideInputFunc, outputFunc ReceiveOut
case opInput: case opInput:
inputsRequested++ inputsRequested++
param1 := p.GetMemory(instructionPointer) param1 := p.GetMemory(instructionPointer)
var inputVal int64 p.setMemory(int(param1), inputFunc(inputsRequested), paramModes[0])
if len(p.feedInput) > 0 {
inputVal = int64(p.feedInput[0])
p.feedInput = p.feedInput[1:]
} else {
inputVal = inputFunc(inputsRequested)
}
if p.printASCII && inputVal <= 255 {
fmt.Printf("%c", rune(inputVal))
}
p.setMemory(int(param1), inputVal, paramModes[0])
instructionPointer += 1 instructionPointer += 1
case opOutput: case opOutput:
param1 := p.GetMemory(instructionPointer) param1 := p.GetMemory(instructionPointer)
param1Val := p.getParamValue(int(param1), paramModes[0]) outputFunc(p.getParamValue(int(param1), paramModes[0]), p.makeState(instructionPointer))
if p.printASCII && param1Val <= 255 {
fmt.Printf("%c", rune(param1Val))
}
outputFunc(param1Val, p.makeState(instructionPointer))
lastOutput = param1Val
instructionPointer += 1 instructionPointer += 1
@ -274,19 +256,8 @@ func (p *IntcodeProgram) RunIn(inputFunc ProvideInputFunc, outputFunc ReceiveOut
} }
p.haltRequested = false p.haltRequested = false
return lastOutput
} }
func (p *IntcodeProgram) Stop() { func (p *IntcodeProgram) Stop() {
p.haltRequested = true p.haltRequested = true
} }
func (p *IntcodeProgram) SetDebugASCIIPrint(enable bool) {
p.printASCII = enable
}
func (p *IntcodeProgram) FeedInputString(str string) {
p.feedInput = make([]rune, len(str))
copy(p.feedInput, []rune(str))
}