day23.go

package main

import (
	"fmt"
	"math"
	"strings"
)

func main() {
	fmt.Println(part1(input1)) // 110
	fmt.Println(part1(input2)) // 4114
	fmt.Println(part2(input1)) // 20
	fmt.Println(part2(input2)) // 970
}

func part1(input string) int {
	elves := parse(input)
	for i := 0; i < 10; i++ {
		elves = simulate(elves, i)
	}

	return size(elves) - len(elves)
}

func part2(input string) int {
	elves := parse(input)

	var prev string

	var i int
	for {
		curr := fmt.Sprint(elves)
		if prev == curr {
			return i
		}
		prev = curr
		elves = simulate(elves, i)
		i++
	}

	return 0
}

func simulate(elves map[complex128]bool, i int) map[complex128]bool {
	type state struct {
		prev complex128
		next complex128
	}

	res := make(map[complex128]bool)
	count := make(map[complex128]int)

	var states []state

	for elf := range elves {
		// Surrounding is empty, stop.
		if !isOccupied(elves, elf, moves...) {
			res[elf] = true
			continue
		}

		n := len(states)

		// Check all four directions.
		for j := 0; j < len(directions); j++ {
			dir := directions[(i+j)%len(directions)]
			// Cannot move.
			if isOccupied(elves, elf, dir...) {
				continue
			}

			// Track the count of the moves.
			s := state{
				prev: elf,
				next: elf + dir[1],
			}
			states = append(states, s)
			count[s.next]++
			break
		}

		// Did not move.
		if len(states) == n {
			res[elf] = true
		}
	}

	for _, s := range states {
		// The only elf moving to that position.
		if count[s.next] == 1 {
			res[s.next] = true
		} else {
			res[s.prev] = true
		}
	}

	return res
}

var north = []complex128{
	complex(-1, -1),
	complex(0, -1),
	complex(1, -1),
}
var south = []complex128{
	complex(-1, 1),
	complex(0, 1),
	complex(1, 1),
}
var east = []complex128{
	complex(1, -1),
	complex(1, 0),
	complex(1, 1),
}
var west = []complex128{
	complex(-1, -1),
	complex(-1, 0),
	complex(-1, 1),
}

var directions = [][]complex128{north, south, west, east}
var moves []complex128 = append(north, append(south, append(west, append(east)...)...)...)

func isOccupied(grid map[complex128]bool, start complex128, positions ...complex128) bool {
	for _, p := range positions {
		if grid[p+start] {
			return true
		}
	}

	return false
}

func size(grid map[complex128]bool) int {
	minX, maxX, minY, maxY := math.MaxInt, math.MinInt, math.MaxInt, math.MinInt
	for p := range grid {
		x, y := int(real(p)), int(imag(p))
		if x < minX {
			minX = x
		}
		if x > maxX {
			maxX = x
		}
		if y < minY {
			minY = y
		}
		if y > maxY {
			maxY = y
		}
	}
	return (maxX - minX + 1) * (maxY - minY + 1)
}

func draw(grid map[complex128]bool) {
	minX, maxX, minY, maxY := math.MaxInt, math.MinInt, math.MaxInt, math.MinInt
	for p := range grid {
		x, y := int(real(p)), int(imag(p))
		if x < minX {
			minX = x
		}
		if x > maxX {
			maxX = x
		}
		if y < minY {
			minY = y
		}
		if y > maxY {
			maxY = y
		}
	}
	res := make([][]rune, maxY-minY+1)
	for y := range res {
		res[y] = make([]rune, maxX-minX+1)
		for x := range res[y] {
			res[y][x] = '.'
		}
	}
	for p := range grid {
		x, y := int(real(p)), int(imag(p))
		res[y-minY][x-minX] = '#'
	}
	for _, row := range res {
		fmt.Println(string(row))
	}
	fmt.Println(len(res)*len(res[0]), len(grid), minX, maxX, minY, maxY)
	fmt.Println()
}

func parse(input string) map[complex128]bool {
	rows := strings.Split(input, "\n")
	grid := make(map[complex128]bool)
	for r, row := range rows {
		for c, col := range row {
			if col != '#' {
				continue
			}
			grid[complex(float64(c), float64(r))] = true
		}
	}

	return grid
}

var input1 = `..............
..............
.......#......
.....###.#....
...#...#.#....
....#...##....
...#.###......
...##.#.##....
....#..#......
..............
..............
..............`

var input2 = `#.##.##...####..#.##.##....###....##...#..#####..#.##.##.#...###.##..#.##
.#....#..#.##..#.#.#...#..#..####..#.#.##.#.#..#.#..#.#..##.#..........#.
##.#####.###.#...######..###.#.#..##.#.##.#......#..##.....###.#.##.##.##
..#######.####.#..###...####..####....#.####.#.#..#.#.###.##.###.##..#...
.#..#.##...#...####.....##.#.#..#...###.....##..#.##..#.#.#.##.##.#.#.#..
####.#...#.#..##..###.####.#######.....#.##.#..#.#...#.##.#....#.........
..#.#.####...###.##.#..#.....#.##...#.#.####.....#..##....#..#####...##..
#####..##.....#.##..#.####....#.#....#.##....#.#....##.#####.#...####..##
#.#..#####.###..####..#.##..#######....##..#.###.#.#....##.#..##.##..#..#
..##.#.##.....###..#..#..#.####....#..####..##.###...#..#..#...##..##..##
#.###.##.#...##.##.#.##..####.##.#.#.###...##.#....#.#.#.##.##...#.##.#.#
.#####..###.#.###.###....#..#..#....#.##.#.###.#.####..###.#####.#.#####.
...#..##.##.#.#.###.#######.##.#...##..##...#......#..####.#.#...#.#####.
.#..###..######..#.#.##.##.#.##....##.#...#...#..#.#.##.#...#.#..#...#.##
##..#.#...#.###.#..#..#.###.###..###.#.......#####.##.####..#...#..#....#
...#..###...#...###.#.....#.###.##.###.####.##.....##..##.#.##.#.#...#.##
####.#......#..###..#.#...##.#.##..#...#.###...#..##.#..#.....####.##.###
##....#..#####..#####....##.#####.##.###..#.#####..###.##..#.#..###.#.###
##.##...##.###.#.#..#####...#..#...#....#..#.#.#.......##..#...#..######.
......#.###.#.##..####..#..##..##.###.#..##...#...#...#...#.###.#.#.##.##
....##..#...##.##.#.#.#..#..#.#...####.#.....#.#.#.##.#.....##.#...#.#.##
..#..###.#..###.####..#.#....#..##.#.##..###...#.##.#.####.##.#.#.#.#...#
...###.....####.######...####.....#.#.#.#...#..##.##...#.###..###.#.#####
#.##..#.##.#......#####..#...####.#...###...###.##...##.##...###.###.##.#
###....#..#.###..#.####.##.#...##..#..#..#....###...#......#..#..##.#.###
.####.#.###..#########...#.##############.##...#.##.##.#..#.#.##.#.#.###.
.#.##...#...###..#..#.#.#..#.#.#.#.##........#.##.#.#.##.##.#.#.##.######
##.#.#.###..###.###.#.#.....#.###..####.#.#..##.#.##..#.####..#.......##.
.#.#####.#..###..##.#..#...#.#.##..#..#..#..##.####.##.#..###.#......#...
.##..##..#..#.#..###...#.#.##.###..#..#...#.##.#.##..#.#.##..#....#...#..
..#......###..###..##...##.###..##.#.....#.###...##.##..#...#..#.#..#....
.#.#.#.#.#...###.#######..#..###...#.###.#.###.##....#...#.##......####..
#...#.##.#...#.#.#.###.#..#.#..##.###.######.#.#....###.##...#....#....#.
.###....#..####.#..#....##.#..##..#..#.#####.#.#...##.##...####.###.##..#
#...#.#...#...##.#####.#.#...##..#..##.#...#...###....##.######.#..#.##.#
#...##...##..#......####.#.#.##.##.#.......####...####...#..#..#.#..#.##.
.###....#.####..##.###..#....#...##.###..#...#.##.#...#####.###..#..#..##
##.#..##..###.#..#..####...#.##.##..#......####....#....#.###..##......##
##.##....#####.##.###.######..#..####..##.#.####.#..####.##...##....#####
.##.#..##..#.##..###.....#..#.##..####...#.##...#.#.#.#..##.###.....##...
.##.#...#...####..##.#....##...#..###.#.#..#....##.######.#...##.###..##.
##.##.###..#.##.#..#....#.##.#.##..#...#..##.#.####..##.##...#..##.##..##
.#..###.#.#.##..#..#.####.#.##.#..##.#....#.###.##..#.###...#..#....###..
####..#.#..###..#...##.##.###.##...#.##.##...##..#.##.##...#.#..#.#.#.#..
..###...#..#...........#.###.##..#..###..##.#.##.#...#.#..#.....##..#####
.....##....###..###.###..#..#...##..#......#.##..#.#.#..##..#.###.....#.#
..####.#......#...#.#.#.#..#..##....##..#.#...##.##.##.###.###...###...#.
##..#.#.#.##.###########.#.###....####.##.#.#...####..#.##.#...##...#....
##...#..#...####.#.####....#.########.######..###....###..##..#...#.###..
##.###.####..#.##.#.#####.##.###..#.#.#.##.##.##.####.##.#...#..#..##....
.#..#.#.##..##...#....#.#....#....###..#..##..###.##.####.##.####.##.#...
##.#.##.##...#.#..#.#...##...#...#..#......#.###......###.....#.#.#####.#
..#.##.##.###....#.#..###..#..##.####.###.##..##.##....#...##.#..#..##.##
#####.#...#..##..##.#.#.....##..#..##.##.##.####..#####.#..###..#.##..##.
####.##..........###.###.#####.#.#..##...##.....#..###..##..#.####..#.##.
#.....##.####...#..##.##..#..#....##..#...#..#.#.....#..#...#.###.##.#..#
#.#.##..###.#...##.#...###.#......#....##..##.##.###.#.#.#..#.##.####..##
##..###.#.#......##.##.##.#.#####.#.#.###...###.##.#......#.##########..#
.####....#..#...###.#..##.#.####..#.#..######.#.####..##....###..##..#..#
#..##.#.#...##.#.#.########.....#.##...#....#.####.###.########.#.##.#...
#.#######..#.##.#.#.#..####..##.#..###.####.#..#########....####....###..
..##.#...##...#..###.#..##.#..#...##.####.######.####.#..##.#...#.#..###.
.#..##.#.##..#......##.#.#.##.#####.#.###....#...###...#....#.###.....###
#......#.#..##....##.########.#..#..##.##......#.#..######..##.##..##.###
..##...#...#.#..#.#########..##..#####..#..#..##.#....##...#.#....##.#.#.
.##..###.####.#..#####.###..###..#......##...#.....####..###..#..##.#.##.
......###.#..#...#..#.#.##.#.###...##.#.#....####.#..#.######.#.#...####.
...#.##.####....##..##.#.###.###.....#..###...####..##..######.#..##.....
.....####.....###.#.#.......#####.#.#....##...#####..#..#.#..#.#.#..##.##
##..##.#..##..#..#.#####..##.####.#...#.#..#..###..#..#....#...#.###.##..
#.#..#.#########.####..#####..####.#.#####....#.#..##...#..####.#..###.#.
#..##.###.##..#....#...#..#.##..#..###..#####..#######.#####....#.##.....
####.####.########.#.###....#.#..#..#.#.#.#..#....#..#.....#..##..#.##.#.`