commit 8e338fb74904687ed443c66495e9cbafcad1070f
parent 183e8d1cf7dd876123f6fce26b231da0eef3f827
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Mon, 19 Dec 2022 20:12:50 -0800
Solution to day 15, part 2.
I overhauled part 1 to run much faster, but part 2 is still pretty slow
(it brute-forces a solution). But it works, so I'm calling this done.
Diffstat:
| M | src/day_15.jl | | | 85 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------ |
1 file changed, 66 insertions(+), 19 deletions(-)
diff --git a/src/day_15.jl b/src/day_15.jl
@@ -1,6 +1,7 @@
#!/usr/bin/env julia
# https://adventofcode.com/2022/day/15
using AdventOfCode
+using DataStructures
example = readlines(IOBuffer("""
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
@@ -34,38 +35,84 @@ function beacon_distance(sensors::AbstractMatrix{Int})
end
"""
-Scan a row and count spaces where a beacon cannot be.
+Scan a row and return a list of ranges that can't contain unknown beacons.
"""
-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)
+function scan_row(sensors::AbstractMatrix{Int}, row::Int,
+ maxdist::Vector{Int} = beacon_distance(sensors))
+ # We only care about sensors that are contributing information for the
+ # current row: find those.
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}}()
+ # step.
+ beaconfree_tree = RBTree{Tuple{Int,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))
+ push!(beaconfree_tree,
+ (sensors[s_i,1]-offset, sensors[s_i,1]+offset))
+ end
+
+ # Now we build a list of beacon-free locations. We use a linked list here
+ # for quick pushes/pops, and we take advantage of the balanced tree we used
+ # on the first pass.
+ beaconfree = MutableLinkedList{Tuple{Int,Int}}(beaconfree_tree[1])
+ for i = 2:length(beaconfree_tree)
+ newzone = beaconfree_tree[i]
+ currentzone = pop!(beaconfree)
+ if newzone[1] <= currentzone[2]
+ push!(beaconfree,
+ (currentzone[1], max(currentzone[2], newzone[2])))
+ else
+ append!(beaconfree, currentzone, newzone)
+ end
+ end
+
+ beaconfree
+end
+
+"""
+Count the number of locations we know to not contain a beacon
+"""
+function count_beaconfree_locations(sensors::AbstractMatrix{Int}, row::Int)
+ beaconfree = scan_row(sensors, row)
+ sum(map(x->(x[2] - x[1]), beaconfree))
+end
+
+"""
+Find the first row that has a spot for a beacon.
+
+Returns a tuple containing the beacon's row and column number, searching only
+in the supplied ranges.
+"""
+function scan_all_rows(sensors::AbstractMatrix{Int}, search_max::Int)
+ maxdist = beacon_distance(sensors)
+ for row=0:search_max
+ beaconfree = scan_row(sensors, row, maxdist)
+ if length(beaconfree) == 1
+ if beaconfree[1][1] > 0
+ return((0, row))
+ elseif beaconfree[1][2] < search_max
+ return((search_max, row))
+ end
+ elseif length(beaconfree) == 2
+ return((beaconfree[1][2]+1, row))
+ else
+ error("Unexpected beacon-free range on row $row")
+ end
end
-
- # Deal with the overlap and actual beacons on the row
- setdiff(reduce(union, beaconfree),
- unique(sensors[sensoridx[sensors[sensoridx, 4] .== row], 3]))
+ return nothing
end
function part_1(input, row)
- length(scan_row(parse_input(input), row))
+ count_beaconfree_locations(parse_input(input), row)
end
@assert part_1(example, 10) == 26
@info part_1(input, 2000000)
-function part_2(input)
- nothing
+function part_2(input, search_max)
+ x, y = scan_all_rows(parse_input(input), search_max)
+ 4000000 * x + y
end
-@info part_2(input)
+@assert part_2(example, 20) == 56000011
+@info part_2(input, 4000000)
