day_15.jl (4143B)
1 #!/usr/bin/env julia 2 # https://adventofcode.com/2022/day/15 3 using AdventOfCode 4 using DataStructures 5 6 example = readlines(IOBuffer(""" 7 Sensor at x=2, y=18: closest beacon is at x=-2, y=15 8 Sensor at x=9, y=16: closest beacon is at x=10, y=16 9 Sensor at x=13, y=2: closest beacon is at x=15, y=3 10 Sensor at x=12, y=14: closest beacon is at x=10, y=16 11 Sensor at x=10, y=20: closest beacon is at x=10, y=16 12 Sensor at x=14, y=17: closest beacon is at x=10, y=16 13 Sensor at x=8, y=7: closest beacon is at x=2, y=10 14 Sensor at x=2, y=0: closest beacon is at x=2, y=10 15 Sensor at x=0, y=11: closest beacon is at x=2, y=10 16 Sensor at x=20, y=14: closest beacon is at x=25, y=17 17 Sensor at x=17, y=20: closest beacon is at x=21, y=22 18 Sensor at x=16, y=7: closest beacon is at x=15, y=3 19 Sensor at x=14, y=3: closest beacon is at x=15, y=3 20 Sensor at x=20, y=1: closest beacon is at x=15, y=3""")) 21 input = readlines("data/day_15.txt") 22 23 function parse_input(input) 24 pattern = r"Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)" 25 matches = map(x->match(pattern, x), input) 26 @assert !any(map(isnothing, matches)) 27 parse.( 28 Int, 29 permutedims(hcat(map(Base.Fix2(getfield, :captures), matches)...)) 30 ) 31 end 32 33 function beacon_distance(sensors::AbstractMatrix{Int}) 34 abs.(sensors[:,1]-sensors[:,3]) + abs.(sensors[:,2]-sensors[:,4]) 35 end 36 37 """ 38 Scan a row and return a list of ranges that can't contain unknown beacons. 39 """ 40 function scan_row(sensors::AbstractMatrix{Int}, row::Int, 41 maxdist::Vector{Int} = beacon_distance(sensors)) 42 # We only care about sensors that are contributing information for the 43 # current row: find those. 44 sensoridx = findall(abs.(sensors[:,2] .- row) .< maxdist) 45 46 # Each sensor contributes a range of values that cannot be occupied on a 47 # given row. These ranges can overlap but we'll deal with that in the next 48 # step. 49 beaconfree_tree = RBTree{Tuple{Int,Int}}(); 50 for s_i = sensoridx 51 offset = maxdist[s_i]-abs(sensors[s_i,2] - row) 52 push!(beaconfree_tree, 53 (sensors[s_i,1]-offset, sensors[s_i,1]+offset)) 54 end 55 56 # Now we build a list of beacon-free locations. We use a linked list here 57 # for quick pushes/pops, and we take advantage of the balanced tree we used 58 # on the first pass. 59 beaconfree = MutableLinkedList{Tuple{Int,Int}}(beaconfree_tree[1]) 60 for i = 2:length(beaconfree_tree) 61 newzone = beaconfree_tree[i] 62 currentzone = pop!(beaconfree) 63 if newzone[1] <= currentzone[2] 64 push!(beaconfree, 65 (currentzone[1], max(currentzone[2], newzone[2]))) 66 else 67 append!(beaconfree, currentzone, newzone) 68 end 69 end 70 71 beaconfree 72 end 73 74 """ 75 Count the number of locations we know to not contain a beacon 76 """ 77 function count_beaconfree_locations(sensors::AbstractMatrix{Int}, row::Int) 78 beaconfree = scan_row(sensors, row) 79 sum(map(x->(x[2] - x[1]), beaconfree)) 80 end 81 82 """ 83 Find the first row that has a spot for a beacon. 84 85 Returns a tuple containing the beacon's row and column number, searching only 86 in the supplied ranges. 87 """ 88 function scan_all_rows(sensors::AbstractMatrix{Int}, search_max::Int) 89 maxdist = beacon_distance(sensors) 90 for row=0:search_max 91 beaconfree = scan_row(sensors, row, maxdist) 92 if length(beaconfree) == 1 93 if beaconfree[1][1] > 0 94 return((0, row)) 95 elseif beaconfree[1][2] < search_max 96 return((search_max, row)) 97 end 98 elseif length(beaconfree) == 2 99 return((beaconfree[1][2]+1, row)) 100 else 101 error("Unexpected beacon-free range on row $row") 102 end 103 end 104 return nothing 105 end 106 107 function part_1(input, row) 108 count_beaconfree_locations(parse_input(input), row) 109 end 110 @assert part_1(example, 10) == 26 111 @info part_1(input, 2000000) 112 113 function part_2(input, search_max) 114 x, y = scan_all_rows(parse_input(input), search_max) 115 4000000 * x + y 116 end 117 @assert part_2(example, 20) == 56000011 118 @info part_2(input, 4000000)