advent_of_code_2022

My (attempted) solutions to the 2022 Advent of Code
git clone https://git.eamoncaddigan.net/advent_of_code_2022.git
Log | Files | Refs | README

day_23.jl (4226B)

      1 #!/usr/bin/env julia
      2 # https://adventofcode.com/2022/day/23
      3 using AdventOfCode
      4 
      5 example = readlines(IOBuffer("""
      6     ....#..
      7     ..###.#
      8     #...#.#
      9     .#...##
     10     #.###..
     11     ##.#.##
     12     .#..#.."""))
     13 input = readlines("data/day_23.txt")
     14 
     15 Elf = Tuple{Int, Int}
     16 ElfSet = AbstractSet{Elf}
     17 
     18 """
     19 Read the input and return a set of elf positions.
     20 """
     21 function parse_input(input::Vector{<:AbstractString})
     22     elves = Set{Elf}()
     23     for (y, line) = enumerate(input)
     24         for (x, c) = enumerate(split(line, ""))
     25             c == "#" && push!(elves, (y, x))
     26         end
     27     end
     28     elves
     29 end
     30 
     31 """
     32 Find the neighbors of an elf.
     33 
     34 Returns a 3x3 boolean matrix that is true IFF an elf is in a position relative
     35 to the given elf.
     36 """
     37 function neighbors(elf::Elf, elves::ElfSet)
     38     neighbors = zeros(Bool, (3, 3))
     39     for Δy = -1:1, Δx = -1:1
     40         if (Δy, Δx) == (0, 0) 
     41             neighbors[2+Δy, 2+Δx] = false # simplify move calculation
     42         else
     43             neighbors[2+Δy, 2+Δx] = (elf[1]+Δy, elf[2]+Δx) ∈ elves
     44         end
     45     end
     46     neighbors
     47 end
     48 
     49 """
     50 Propose a move for one elf at the given timestep.
     51 """
     52 function propose_move(elf::Elf, elves::ElfSet, timestep::Int)
     53     elfneighbs = neighbors(elf, elves)
     54     if !any(elfneighbs)
     55         return elf
     56     else
     57         for i = 0:3
     58             direction = [:n, :s, :w, :e][(i + timestep) % 4 + 1]
     59             if direction == :n
     60                 !any(elfneighbs[1, :]) && return (elf[1]-1, elf[2])
     61             elseif direction == :s
     62                 !any(elfneighbs[3, :]) && return (elf[1]+1, elf[2])
     63             elseif direction == :w
     64                 !any(elfneighbs[:, 1]) && return (elf[1], elf[2]-1)
     65             else # :e
     66                 !any(elfneighbs[:, 3]) && return (elf[1], elf[2]+1)
     67             end
     68         end
     69     end
     70     elf
     71 end
     72 
     73 """
     74 Find a mapping from proposed elf positions to current elf positions.
     75 
     76 timestep starts at 0 and should increment at each step in the process. This is
     77 a bit confusing (for me anyway), because the mapping is from *proposed*
     78 locations to *originating* locations, when the converse seems a bit more
     79 intuitive.
     80 """
     81 function moveelves(elves::ElfSet, timestep::Int)
     82     camefrom = Dict{Elf,Elf}()
     83     invalidmoves = Vector{Elf}()
     84     # Step 1: Propose moves for each elf, mark invalid moves
     85     for elf₁ = elves
     86         elf₂ = propose_move(elf₁, elves, timestep)
     87         if elf₂ ∈ keys(camefrom)
     88             # This is an invalid move. We'll mark it for now and leave the
     89             # current elf in its present location
     90             camefrom[elf₁] = elf₁
     91             push!(invalidmoves, elf₂)
     92         else
     93             # This move is fine (so far)
     94             camefrom[elf₂] = elf₁
     95         end
     96     end
     97 
     98     # Step 2: Put elves at marked-invalid locations back where they came from
     99     for elf₂ = invalidmoves
    100         camefrom[camefrom[elf₂]] = camefrom[elf₂]
    101         delete!(camefrom, elf₂)
    102     end
    103 
    104     camefrom
    105 end
    106 
    107 moveelves(elves::Dict{Elf,Elf}, timestep::Int) = moveelves(keys(elves), timestep)
    108 
    109 """
    110 Return the (height, width) of the area containing all elves.
    111 """
    112 function mapsize(elves::ElfSet)
    113     (ymin, ymax) = extrema(x -> x[1], elves)
    114     (xmin, xmax) = extrema(x -> x[2], elves)
    115     (ymax-ymin+1, xmax-xmin+1)
    116 end
    117 
    118 """
    119 Return the number of empty spots on the map.
    120 """
    121 function emptyspots(elves::ElfSet)
    122     prod(mapsize(elves)) - length(elves)
    123 end
    124 
    125 emptyspots(elves::Dict{Elf,Elf}) = emptyspots(keys(elves))
    126 
    127 function part_1(input)
    128     elves = parse_input(input)
    129     for ts = 0:9
    130         elves = moveelves(elves, ts)
    131     end
    132     emptyspots(elves)
    133 end
    134 @assert part_1(example) == 110
    135 @info part_1(input)
    136 
    137 function Base.:(==)(elves₁::Dict{Elf,Elf}, elves₂::ElfSet)
    138     keys(elves₁) == elves₂
    139 end
    140 
    141 function Base.:(==)(elves₁::ElfSet, elves₂::Dict{Elf,Elf})
    142     elves₁ == keys(elves₂)
    143 end
    144 
    145 function Base.:(==)(elves₁::Dict{Elf,Elf}, elves₂::Dict{Elf,Elf})
    146     keys(elves₁) == keys(elves₂)
    147 end
    148 
    149 function part_2(input)
    150     elves₁ = parse_input(input)
    151     for ts = 0:1_000_000
    152         elves₂ = moveelves(elves₁, ts)
    153         elves₁ == elves₂ && return ts+1
    154         elves₁ = elves₂
    155     end
    156     nothing
    157 end
    158 @assert part_2(example) == 20
    159 @info part_2(input)