commit d9a3b9fb9cab0c3c7c7c83fdc5556c66af337971
parent c1f3cd0bf3859795b4ebce2aa04094990424224c
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Tue, 3 Jan 2023 23:05:34 -0800
Solution to day 23, part 1.
Diffstat:
| A | src/day_23.jl | | | 140 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 140 insertions(+), 0 deletions(-)
diff --git a/src/day_23.jl b/src/day_23.jl
@@ -0,0 +1,140 @@
+#!/usr/bin/env julia
+# https://adventofcode.com/2022/day/23
+using AdventOfCode
+
+example = readlines(IOBuffer("""
+ ....#..
+ ..###.#
+ #...#.#
+ .#...##
+ #.###..
+ ##.#.##
+ .#..#.."""))
+input = readlines("data/day_23.txt")
+
+Elf = Tuple{Int, Int}
+ElfSet = AbstractSet{Elf}
+
+"""
+Read the input and return a set of elf positions.
+"""
+function parse_input(input::Vector{<:AbstractString})
+ elves = Set{Elf}()
+ for (y, line) = enumerate(input)
+ for (x, c) = enumerate(split(line, ""))
+ c == "#" && push!(elves, (y, x))
+ end
+ end
+ elves
+end
+
+"""
+Find the neighbors of an elf.
+
+Returns a 3x3 boolean matrix that is true IFF an elf is in a position relative
+to the given elf.
+"""
+function neighbors(elf::Elf, elves::ElfSet)
+ neighbors = zeros(Bool, (3, 3))
+ for Δy = -1:1, Δx = -1:1
+ if (Δy, Δx) == (0, 0)
+ neighbors[2+Δy, 2+Δx] = false # simplify move calculation
+ else
+ neighbors[2+Δy, 2+Δx] = (elf[1]+Δy, elf[2]+Δx) ∈ elves
+ end
+ end
+ neighbors
+end
+
+"""
+Propose a move for one elf at the given timestep.
+"""
+function propose_move(elf::Elf, elves::ElfSet, timestep::Int)
+ elfneighbs = neighbors(elf, elves)
+ if !any(elfneighbs)
+ return elf
+ else
+ for i = 0:3
+ direction = [:n, :s, :w, :e][(i + timestep) % 4 + 1]
+ if direction == :n
+ !any(elfneighbs[1, :]) && return (elf[1]-1, elf[2])
+ elseif direction == :s
+ !any(elfneighbs[3, :]) && return (elf[1]+1, elf[2])
+ elseif direction == :w
+ !any(elfneighbs[:, 1]) && return (elf[1], elf[2]-1)
+ else # :e
+ !any(elfneighbs[:, 3]) && return (elf[1], elf[2]+1)
+ end
+ end
+ end
+ elf
+end
+
+"""
+Find a mapping from proposed elf positions to current elf positions.
+
+timestep starts at 0 and should increment at each step in the process. This is
+a bit confusing (for me anyway), because the mapping is from *proposed*
+locations to *originating* locations, when the converse seems a bit more
+intuitive.
+"""
+function moveelves(elves::ElfSet, timestep::Int)
+ camefrom = Dict{Elf,Elf}()
+ invalidmoves = Vector{Elf}()
+ # Step 1: Propose moves for each elf, mark invalid moves
+ for elf₁ = elves
+ elf₂ = propose_move(elf₁, elves, timestep)
+ if elf₂ ∈ keys(camefrom)
+ # This is an invalid move. We'll mark it for now and leave the
+ # current elf in its present location
+ camefrom[elf₁] = elf₁
+ push!(invalidmoves, elf₂)
+ else
+ # This move is fine (so far)
+ camefrom[elf₂] = elf₁
+ end
+ end
+
+ # Step 2: Put elves at marked-invalid locations back where they came from
+ for elf₂ = invalidmoves
+ camefrom[camefrom[elf₂]] = camefrom[elf₂]
+ delete!(camefrom, elf₂)
+ end
+
+ camefrom
+end
+
+moveelves(elves::Dict{Elf,Elf}, timestep::Int) = moveelves(keys(elves), timestep)
+
+"""
+Return the (height, width) of the area containing all elves.
+"""
+function mapsize(elves::ElfSet)
+ (ymin, ymax) = extrema(x -> x[1], elves)
+ (xmin, xmax) = extrema(x -> x[2], elves)
+ (ymax-ymin+1, xmax-xmin+1)
+end
+
+"""
+Return the number of empty spots on the map.
+"""
+function emptyspots(elves::ElfSet)
+ prod(mapsize(elves)) - length(elves)
+end
+
+emptyspots(elves::Dict{Elf,Elf}) = emptyspots(keys(elves))
+
+function part_1(input)
+ elves = parse_input(input)
+ for ts = 0:9
+ elves = moveelves(elves, ts)
+ end
+ emptyspots(elves)
+end
+@assert part_1(example) == 110
+@info part_1(input)
+
+function part_2(input)
+ nothing
+end
+@info part_2(input)
