Day 15

1 files changed, 271 insertions, 0 deletions

diff --git a/day15/main.go b/day15/main.go
new file mode 100644
index 0000000..377b961
--- /dev/null
+++ b/day15/main.go
@@ -0,0 +1,271 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strings"
+)
+
+func main() {
+	{
+		exampleFloor := readFloor("example_map.txt")
+		exampleMoves, _ := os.ReadFile("example_moves.txt")
+		fmt.Println(part1(exampleFloor, exampleMoves), 10092)
+	}
+
+	{
+		dataFloor := readFloor("data_map.txt")
+		dataMoves, _ := os.ReadFile("data_moves.txt")
+		fmt.Println(part1(dataFloor, dataMoves), 1492518)
+	}
+
+	// {
+	// 	var simpleFloor1 [][]byte
+	// 	simpleFloor1 = append(simpleFloor1, []byte("##########"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#........#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#........#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#.....O..#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#.....O..#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#.....O..#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#.....@..#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#........#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("#........#"))
+	// 	simpleFloor1 = append(simpleFloor1, []byte("##########"))
+
+	// 	simpleFloor := makeWide(simpleFloor1)
+	// 	simpleMoves := []byte("^^")
+	// 	part2(simpleFloor, simpleMoves)
+	// }
+
+	{
+		exampleFloor := makeWide(readFloor("example_map.txt"))
+		exampleMoves, _ := os.ReadFile("example_moves.txt")
+		fmt.Println(part2(exampleFloor, exampleMoves), 9021)
+	}
+
+	{
+		dataFloor := makeWide(readFloor("data_map.txt"))
+		dataMoves, _ := os.ReadFile("data_moves.txt")
+		fmt.Println(part2(dataFloor, dataMoves))
+	}
+}
+
+func part1(floor [][]byte, moves []byte) (result int) {
+	botx, boty := findInitialPosition(floor)
+
+	doMoves(moves, botx, boty, floor, doMovePart1)
+
+	for y, line := range floor {
+		for x, c := range line {
+			if c == 'O' {
+				result += y*100 + x
+			}
+		}
+	}
+
+	return
+}
+
+func doMovePart1(floor [][]byte, startx, starty int, dx, dy int) (endx, endy int) {
+	x := startx
+	y := starty
+	moved := 0
+	for {
+		moved += 1
+		x += dx
+		y += dy
+
+		if floor[y][x] == '#' {
+			return startx, starty
+		}
+
+		if floor[y][x] == '.' {
+			if moved > 1 {
+				floor[y][x] = 'O'
+			}
+			floor[starty+dy][startx+dx] = '@'
+			floor[starty][startx] = '.'
+			return startx + dx, starty + dy
+		}
+	}
+}
+
+func doMoves(moves []byte, botx int, boty int, floor [][]byte, doMoveFn func([][]byte, int, int, int, int) (int, int)) {
+	for _, move := range moves {
+		switch move {
+		case '^':
+			botx, boty = doMoveFn(floor, botx, boty, 0, -1)
+		case 'v':
+			botx, boty = doMoveFn(floor, botx, boty, 0, 1)
+		case '<':
+			botx, boty = doMoveFn(floor, botx, boty, -1, 0)
+		case '>':
+			botx, boty = doMoveFn(floor, botx, boty, 1, 0)
+		}
+	}
+}
+
+func findInitialPosition(floor [][]byte) (int, int) {
+	var botx, boty int
+	for y, line := range floor {
+		idx := strings.IndexByte(string(line), '@')
+		if idx >= 0 {
+			botx = idx
+			boty = y
+			break
+		}
+	}
+	return botx, boty
+}
+
+type QueuedMove struct {
+	x, y int
+	c    byte
+}
+
+func part2(floor [][]byte, moves []byte) (result int) {
+	var botx, boty int
+	for y, line := range floor {
+		idx := strings.IndexByte(string(line), '@')
+		if idx >= 0 {
+			botx = idx
+			boty = y
+			break
+		}
+	}
+
+	for _, move := range moves {
+		var queued []QueuedMove
+		var dx, dy int
+		switch move {
+		case '^':
+			dx, dy = 0, -1
+		case 'v':
+			dx, dy = 0, 1
+		case '<':
+			dx, dy = -1, 0
+		case '>':
+			dx, dy = 1, 0
+		default:
+			continue
+		}
+
+		if doMovePart2(floor, botx+dx, boty+dy, dx, dy, &queued) {
+			hasMadeMove := make(map[QueuedMove]bool)
+			for i := range queued {
+				m := queued[len(queued)-1-i]
+				_, alreadyMade := hasMadeMove[m]
+				if !alreadyMade {
+					floor[m.y][m.x] = m.c
+					floor[m.y-dy][m.x-dx] = '.'
+					hasMadeMove[m] = true
+				}
+			}
+
+			floor[boty][botx] = '.'
+			botx += dx
+			boty += dy
+			floor[boty][botx] = '@'
+		}
+
+		if !checkIntegrity(floor) {
+			panic("no")
+		}
+	}
+
+	for y, line := range floor {
+		for x, c := range line {
+			if c == '[' {
+				result += y*100 + x
+			}
+		}
+	}
+
+	return
+}
+
+func printMap(floor [][]byte) {
+	for _, line := range floor {
+		fmt.Println(string(line))
+	}
+}
+
+func checkIntegrity(floor [][]byte) bool {
+	for _, line := range floor {
+		for x, c := range line {
+			if c == '[' && line[x+1] != ']' {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+func enqueueMove(x, y int, c byte, queued *[]QueuedMove) {
+	*queued = append(*queued, QueuedMove{x, y, c})
+}
+
+func doMovePart2(floor [][]byte, x, y int, dx, dy int, queued *[]QueuedMove) bool {
+	switch floor[y][x] {
+	case '.':
+		return true
+	case '#':
+		return false
+	case '[':
+		if dx == 0 {
+			enqueueMove(x, y+dy, '[', queued)
+			enqueueMove(x+1, y+dy, ']', queued)
+			return doMovePart2(floor, x, y+dy, dx, dy, queued) && doMovePart2(floor, x+1, y+dy, dx, dy, queued)
+		} else if dx > 0 {
+			enqueueMove(x+1, y, '[', queued)
+			enqueueMove(x+2, y, ']', queued)
+			return doMovePart2(floor, x+2, y, dx, dy, queued)
+		}
+	case ']':
+		if dx == 0 {
+			enqueueMove(x-1, y+dy, '[', queued)
+			enqueueMove(x, y+dy, ']', queued)
+			return doMovePart2(floor, x-1, y+dy, dx, dy, queued) && doMovePart2(floor, x, y+dy, dx, dy, queued)
+		} else if dx < 0 {
+			enqueueMove(x-1, y, ']', queued)
+			enqueueMove(x-2, y, '[', queued)
+			return doMovePart2(floor, x-2, y, dx, dy, queued)
+		}
+	}
+	return false
+}
+
+func makeWide(floor [][]byte) (wide [][]byte) {
+	wide = make([][]byte, len(floor))
+	for y, line := range floor {
+		w := make([]byte, len(line)*2)
+		for i, c := range line {
+			switch c {
+			case '#':
+				w[i*2+0] = '#'
+				w[i*2+1] = '#'
+			case '.':
+				w[i*2+0] = '.'
+				w[i*2+1] = '.'
+			case 'O':
+				w[i*2+0] = '['
+				w[i*2+1] = ']'
+			case '@':
+				w[i*2+0] = '@'
+				w[i*2+1] = '.'
+			}
+		}
+		wide[y] = w
+	}
+	return
+}
+
+func readFloor(fileName string) (floor [][]byte) {
+	fp, _ := os.Open(fileName)
+	scanner := bufio.NewScanner(fp)
+	for scanner.Scan() {
+		floor = append(floor, []byte(strings.TrimSpace(scanner.Text())))
+	}
+	return
+}