Explain and implement logic

Programs coded into a machine that runs a program that's coded into a machine that runs a program. I think this is how Javascript got invented or something.
Day 21 setup
2022-06-24 23:16:32 -05:00 · 2022-06-23 17:22:35 -05:00
14 changed files with 1 additions and 753 deletions
--- a/days/22.go
+++ b/days/22.go
@ -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)
 }
--- a/days/23.go
+++ b/days/23.go
@ -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)
 }
--- a/days/24.go
+++ b/days/24.go
@ -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)
 }
--- a/inputs/21p.txt
+++ b/inputs/21p.txt
--- a/inputs/22p.txt
+++ b/inputs/22p.txt
@ -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
--- a/inputs/22s1.txt
+++ b/inputs/22s1.txt
@ -1,3 +0,0 @@
 deal with increment 7
 deal into new stack
 deal into new stack
--- a/inputs/22s2.txt
+++ b/inputs/22s2.txt
@ -1,3 +0,0 @@
 cut 6
 deal with increment 7
 deal into new stack
--- a/inputs/22s3.txt
+++ b/inputs/22s3.txt
@ -1,3 +0,0 @@
 deal with increment 7
 deal with increment 9
 cut -2
--- a/inputs/22s4.txt
+++ b/inputs/22s4.txt
@ -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
--- a/inputs/23p.txt
+++ b/inputs/23p.txt
--- a/inputs/24p.txt
+++ b/inputs/24p.txt
@ -1,5 +0,0 @@
 ##..#
 ...##
 .#.##
 #..#.
 ..#..
--- a/inputs/24s1.txt
+++ b/inputs/24s1.txt
@ -1,5 +0,0 @@
 ....#
 #..#.
 #..##
 ..#..
 #....
--- a/inputs/24s2.txt
+++ b/inputs/24s2.txt
@ -1,5 +0,0 @@
 .....
 .....
 .....
 #....
 .#...
--- a/main.go
+++ b/main.go
@ -55,9 +55,6 @@ var dayMap = []day{
 	&days.Day19{},
 	&days.Day20{},
 	&days.Day21{},
 	&days.Day22{},
 	&days.Day23{},
 	&days.Day24{},
 }
 func main() {