commit 2d2c3b50224a67ec8b52aa871246c7672fd7c088
parent 9411152faa02ad1b7a725723db3403a1cfc5cba7
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Wed, 14 Dec 2022 21:51:26 -0800
Solution to day 15, part 1.
Diffstat:
| A | src/day_15.jl | | | 71 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 71 insertions(+), 0 deletions(-)
diff --git a/src/day_15.jl b/src/day_15.jl
@@ -0,0 +1,71 @@
+#!/usr/bin/env julia
+# https://adventofcode.com/2022/day/15
+using AdventOfCode
+
+example = readlines(IOBuffer("""
+ Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+ Sensor at x=9, y=16: closest beacon is at x=10, y=16
+ Sensor at x=13, y=2: closest beacon is at x=15, y=3
+ Sensor at x=12, y=14: closest beacon is at x=10, y=16
+ Sensor at x=10, y=20: closest beacon is at x=10, y=16
+ Sensor at x=14, y=17: closest beacon is at x=10, y=16
+ Sensor at x=8, y=7: closest beacon is at x=2, y=10
+ Sensor at x=2, y=0: closest beacon is at x=2, y=10
+ Sensor at x=0, y=11: closest beacon is at x=2, y=10
+ Sensor at x=20, y=14: closest beacon is at x=25, y=17
+ Sensor at x=17, y=20: closest beacon is at x=21, y=22
+ Sensor at x=16, y=7: closest beacon is at x=15, y=3
+ Sensor at x=14, y=3: closest beacon is at x=15, y=3
+ Sensor at x=20, y=1: closest beacon is at x=15, y=3"""))
+input = readlines("data/day_15.txt")
+
+function parse_input(input)
+ pattern = r"Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)"
+ matches = map(x->match(pattern, x), input)
+ @assert !any(map(isnothing, matches))
+ parse.(
+ Int,
+ permutedims(hcat(map(Base.Fix2(getfield, :captures), matches)...))
+ )
+end
+
+function beacon_distance(sensors::AbstractMatrix{Int})
+ abs.(sensors[:,1]-sensors[:,3]) + abs.(sensors[:,2]-sensors[:,4])
+end
+
+"""
+Scan a row and count spaces where a beacon cannot be.
+"""
+function scan_row(sensors::AbstractMatrix{Int}, row::Int)
+ # This tells us how far away each beacon is from the sensor that detects
+ # it. Any space closer than this to the sensor necessarily has no beacon.
+ # One effect of this is that we don't need to worry about scanners that are
+ # more than this distance from the row.
+ maxdist = beacon_distance(sensors)
+ sensoridx = findall(abs.(sensors[:,2] .- row) .< maxdist)
+
+ # Each sensor contributes a range of values that cannot be occupied on a
+ # given row. These ranges can overlap but we'll deal with that in the next
+ # step. For now, track the ranges.
+ beaconfree = Vector{UnitRange{Int}}()
+ for s_i = sensoridx
+ offset = maxdist[s_i]-abs(sensors[s_i,2] - row)
+ push!(beaconfree,
+ (sensors[s_i,1]-offset):(sensors[s_i,1]+offset))
+ end
+
+ # Deal with the overlap and actual beacons on the row
+ setdiff(reduce(union, beaconfree),
+ unique(sensors[sensoridx[sensors[sensoridx, 4] .== row], 3]))
+end
+
+function part_1(input, row)
+ length(scan_row(parse_input(input), row))
+end
+@assert part_1(example, 10) == 26
+@info part_1(input, 2000000)
+
+function part_2(input)
+ nothing
+end
+@info part_2(input)
