ShareMyScreen/AdventOfCode/2022/15/BeaconExclusionZone

The Problem << >>

There are two ways to keep track of the excluded beacon positions: as marks in a 2-dimensional board or as a list of intervals. I take a peek at the full puzzle dataset and see a few intervals containing big numbers. That settles the matter: I will deal with intervals.

I think it will be good enough to capture the input as a brick of shape n,2 2 where the 2x2 element is (sensor y,sensor x) ,: (beacon y,beacon x).

require 'strings'
onepair =: {{  NB. y is one pair's line
sx =. 0 ". ',' taketo 'x=' takeafter y
sy =. 0 ". ':' taketo 'y=' takeafter y
bx =. 0 ". ',' taketo 'beacon is at x=' takeafter y
by =. 0 ". LF taketo 'y=' takeafter 'beacon' takeafter y
(sy,sx),:by,bx
}}
   ] sb =: onepair onaoclines
18  2
15 _2

16  9
16 10
...

Now I need to convert each (sensor,beacon) pair to an excluded interval along the given y, which I will call yline. This interval is centered on sensor_x and extends in both directions for (sensor-to-beacon distance minus |yline-sensor_y) positions. If that difference in negative, there is no interval.

I must decide how to represent the interval. Three possibilities are (start,length), (start,end), and (start,end+1). I think (start,end+1) will be best here because that way two adjacent intervals will be detectable as having the end+1 of the first equal to the start of the second.

   yline =. 10
   ]intvls =. (#~ </"1) ((<0 1) {"2 sb) + (- ,. >:) (+/"1 | -/"2 sb) - | yline - (<0 0) {"2 sb
12 13
 2 15
 2  3
_2  3
16 25
14 19
 NB. beacon distance of 3 and line distance of 1 gives (_2,3) to be added to sensor x; delete negative intervals

Now I will coalesce the intervals into a set of nonoverlapping intervals. This is a akin to parenthesis nesting. I'll write out the steps, starting with

12	13
2	15
2	3
...

Run the interval endpoints into a single list and associate a +1 with the start and a -1 with each end+1

12	13	2	15	2	3	...
1	_1	1	_1	1	_1	...

Combine any positions that are repeated into a single entry with the total of all the values at that position

12	1
13	_1
2	2
15	_1
3	_2
...

Remove any positions that have 0 as the total (none in this example)

Sort the positions into ascending order, carrying the total along with them

_2	1
2	2
3	_2
12	1
13	_1
...

Take the running sum of the sorted totals

_2	1
2	3
3	1
12	2
13	1
...

The surviving positions are in the rows just after a row with total=0 (these are the starting positions of the surviving intervals), and those exactly on a row with total=0 (these are the end+1 of the intervals). Put them into a table.

_2

25

That feels like a line of J. I'll write it.

   ] coalescedintvls =. _2 ]\ (#~  [: (+. _1&(|.!.1)) 0 = +/\)/ |: /:~ ([: (#~ 0 ~: {:"1) ] (, +/)/.. 1 _1 $~ $) , intvls
_2 25

Every beacon that was detected on yline must be included in the intervals, so to find the number of non-beacon positions I need to add up all the interval lengths and deduct the number of beacons found on the line:

   (-~/ +/ coalescedintvls) - +/ yline = (<1 0) {"2  sb
26

What? Wrong answer. Oh, I see, I need to deduct the number of different beacons on the line.

   (-~/ +/ coalescedintvls) - +/ yline = {."1 ~. }."2 sb
24

In Part 2, I have to perform the search on 4e6 lines and find the one point that is not in an interval. Rather than write an interval subtractor I'll just display only the lines that have more than one interval and get the final result by eye.

I want a verb that take the sensor/beacon positions and a line number and returns the intervals. I'll copy the lines above.

oneline =: {{  NB. x is sb, y is yline, result is intervals
intvls =. (#~ </"1) ((<0 1) {"2 x) + (- ,. >:) (+/"1 | -/"2 x) - | y - (<0 0) {"2 x
_2 ]\ (#~  [: (+. _1&(|.!.1)) 0 = +/\)/ |: /:~ ([: (#~ 0 ~: {:"1) ] (, +/)/.. 1 _1 $~ $) , intvls
}}"3 0
   (#~ 1 < #@>) sb <@oneline i. 21 
┌─────┐
│_3 14│
│15 26│
└─────┘
   
   ([: I. 1 < #@>) sb <@oneline i. 21
11
   4000000 #. 14 11
56000011