ShareMyScreen/AdventOfCode/2022/15/BeaconExclusionZoneJP
Sometimes, even buggy code can give the correct answers. This was one of these times, and I only found out when writing this text. While the "Entire solution" below has the correct code, Day 1 and the first part of Day 2 describe the buggy code for educative purpose.
Entire (correct) solution
i15=: freads '15.txt'
NB. parse each line into a 2 x 2 matrix
par =: (2 2$ [:". ] #~ e.&(Num_j_,' _'));._2@rplc&'-_'
NB. part 1: find how many squares cannot have a beacon (given detected beacon is closest)
int =: ] (0&<:@] # xs~ (-,.1++) ]) rad - ys |@:- [ NB. Matrices to intervals
'`xs ys' =: {.@{."2@]`({:@{."2@]) NB. x,y of sensors
rad =: +/@(|@:-/"2)@] NB. radius of sensor by L1 dist to beacon
NB. encode into x,.1/_1 with x being an edge location, and 1/_1 start or end indicator
encode =: (] /:"1~ ] ,: 1 _1$~#)@,
sumid =: ~.@{. ,: (,+/)/./ NB. sumid sums edge indicator per coordinate
count =: [: +/ {. ({:-{.);.2~ (0=+/\)@{: NB. count # OR of ranges given by start,end
nbr =: #@~.@([ (] #~ [={:"1@]) ({:"2@])) NB. number of given beacons on the row x
tot =: (count@sumid@encode@int - nbr) par NB. # possible beacons excluding given
part1 =: 2000000&tot
NB. part 2: Find only possible position for beacon within 0 <:x,y <: 4e6
nfzr =: ({. {~ 0 i.~ +/\@{:) NB. Find first square having nesting level 0
0&T.@0^:(0>.([: {. 8&T.)-1&T.) '' NB. spin up as many threads as CPU cores present
allrows =: {{ NB. parallel search all lines
nbatch=. 4000 NB. # rows per batch; tried out some values...
rowbatches=. (-nbatch) <\ i. x NB. group row indices in boxes per nbatch
vb=:nfzr@sumid@encode@int f. NB. verb returning first
for_b. rowbatches do. NB. For each batch ...
r=. > (>b) vb t.'worker' "0 _ y NB. run all lines on the workers
if. nbatch>offset=. r i.&1@:< x do. NB. Find the first with a hole
(>b) (+4e6&*)&(offset&{) r return. NB. if y+4e6*x
end.
end.
}}
part2=: 4e6 allrows par
(part1;part2)i15
Data and Parsing
Each sensor can see a single beacon in this problem. The input contains for each sensor a line with its coordinates and those of the closest beacon (L1 or Manhattan distance) to that sensor. Each sensor-beacon pair creates a rhomboid shape in which there cannot be any other beacons. The test data given is:
tst=: {{)n
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
}}
My first idea would be to simply enumerate all points in the reach of each sensor, i.e. up to and including the closest beacon. However, looking at the full data made me forget that quickly, as it has huge numbers.
To start with, I'd like to parse the input so we have an Nx2x2 array, with the first row for each line containing the sensor position, and the second the beacon position. Replacing all "-" by "_" and keeping only numbers, underscores and spaces makes each line executable J that just has to be reshaped:
par=: (2 2$ [:". ] #~ e.&(Num_j_,' _'));._2@rplc&'-_'
_2 <\ par tst NB. boxed per 2 for easy display
┌─────┬─────┬─────┬────┬─────┬─────┬────┐
│ 2 18│13 2│10 20│8 7│ 0 11│17 20│14 3│
│_2 15│15 3│10 16│2 10│ 2 10│21 22│15 3│
│ │ │ │ │ │ │ │
│ 9 16│12 14│14 17│2 0│20 14│16 7│20 1│
│10 16│10 16│10 16│2 10│25 17│15 3│15 3│
└─────┴─────┴─────┴────┴─────┴─────┴────┘
This looks right so far.
Part 1
For part 1, we'd need to find how many places cannot contain the beacon, that is all squares that are at a Manhattan distance less than or equal to the distance between a sensor and its respective beacon. Considering a single row in the field, this is, for every sensor, an interval. As the ranges are large in the real input, we'll need to work with the interval boundaries at each specific row:
int=: ] (0&<:@] # xs~ (-,.+) ]) rad - ys |@:- [ NB. Matrices (y) to intervals at row x
'`xs ys' =: {.@{."2@]`({:@{."2@]) NB. x , y of sensors
rad=: +/@(|@:-/"2)@] NB. radius of sensor by L1 dist to beacon
For ease, I split of verbs accessing the sensor's x and y coordinates (xs and ys), and the radius (rad), which is the sum of the absolute value of the differences between the coordinates of the senor and the beacon. For determining the intervals at the row given as x input to int, we need the remaining radius at this row (right part of int until the last ")"), being the radius minus the difference between the row and the row index of the sensor (ys). Adding this remaining radius to the xs gives the interval start and subtracting it gives the interval end. The intervals which are inverted, i.e. where the remaining radius is smaller than 0, are discarded.
Finding where beacons cannot be is pretty much the same as parentheses matching and determining where the nesting depth of the intervals is larger than 0. To encode these intervals so I can count them, I ravel the interval boundaries, and laminate the correct amount of 1's and _1's and sort them:
encode=: (] /:"1~ ] ,: 1 _1$~#)@,
10 encode@int par tst
_2 2 2 2 2 12 12 14 14 16 18 24
1 1 1 _1 _1 1 _1 _1 1 1 _1 _1
Good so far, but repeated entries for each column index (e.g. 2, 12, 24) in the first row should be summed together before I can do anything with this:
sumid =: ~.@{. ,: +//./ NB. sumid sums edge indicator per coordinate
10 sumid@encode@int par tst
_2 2 12 14 16 18 24
1 0 0 0 1 _1 _1
All settled, now we can count the intervals, finding where the running sum becomes 0. The locations of these 0's are the ending borders of the intervals that contain stretches of occupied squares, and I use those as frets. Making the difference between the end and start of each continuous interval, adding 1 to account for the end square not being counted otherwise, and summing then gives all occupied squares.
count =: [: +/ {. (1+{:-{.);.2~ (0=+/\)@{: NB. count # OR of ranges given by start,end
10 count@sumid@encode@int par tst
27
It should have been 26... Pondering a bit, I noticed places that are occupied by given beacons should not be counted as taken, but as possibly (actually, certainly) containing a beacon:
nbr =: #@~.@([ (] #~ [={:"1@]) ({:"2@])) NB. number of given beacons on the row x
10 nbr par tst
1
tot=: (count@sumid@encode@int - nbr) par NB. # possible beacons excluding given beacons
10 tot tst
26
part1 =: 2e6&tot NB. number taken positions on line 2e6
That works for the test data and my input.
Part 2
In part 2, the problem is finding the single position where the beacon can be in the range of (0,0) to (4e6,4e6). The interval part is entirely the same as for part 1. Finding the possible position is finding the first 0 in the running sum used in count. If the corresponding interval boundary is less than 4e6 (or 20 for the test input), we've found the spot. Note that the start of the intervals will start at 1 in the running sum, so the first 0 is always either a hole or the end of all intervals.
nfzr =: (1+{. {~ 0 i.~ +/\@{:) NB. Find first square having nesting level 0
Doing this for test data works (apparantly):
(] (]+4e6*{~) 1 i.~ 20 > ]) (i. 20) (nfzr@sumid@encode@int - nbr)"0 _ par tst
56000011
Hey, that's the right answer. And also the answer for (my) whole input was right, but, when taking a better look when debugging, it looks like I got lucky (or unlucky not to notice this bug):
(i. 4 5) (nfzr@sumid@encode@int - nbr)"0 _ par tst NB. index of first spot in 20 rows (4x5)
27 28 27 25 25
24 23 22 23 24
24 14 4 5 6
6 7 8 25 24
This shouldn't be, the position of the emergency beacon should be unique, while here there are already 7 possible positions. Given that the answers were right, I didn't find this bug until I wrote this text. It took me a few days, but I found the source when looking at row 12 for the field in the test input:
(, +/\@{:) sumid encode 12 int par tst
_2 1 2 3 4 10 12 14 16 26
1 1 _1 _1 1 1 _1 0 0 _1
1 2 1 0 1 2 1 1 1 0
The problem is not in nfzr, as the 0 in the running sum is really as detected at position 4 (1-based). The bug must lie in the encoding of the intervals. Lets look at int:
/:~ 12 int par tst
_2 2
1 3
4 12
10 14
14 14
14 26
16 16
Going through this list of intervals (sorted for convenience), we see that all spaces should have been covered, but the only place where there is no overlap, from the second to third row, is the one that is wrongly detected as "hole". Luckily the fix was easy: I can just change the interval ends:
int=: ] (0&<:@] # xs~ (-,.1++) ]) rad - ys |@:- [ NB. Added 1+ to interval end
/:~ 12 int par tst
_2 3
1 4
4 13
10 15
14 15
14 27
16 17
This change does not impact the encode and sumid, but count and nfzr need to be changed. Funny thing that both already had a 1 +, which makes this the prototypical off-by-one error:
count NB. old, buggy version
[: +/ {. (1 + {: - {.);.2~ (0 = +/\)@{:
nfzr NB. old, buggy version
1 + {. { ~ 0 i.~ +/\@{:
count =: [: +/ {. ({: - {.);.2~ (0 = +/\)@{: NB. removed 1+
nfzr =: {. { ~ 0 i.~ +/\@{: NB. removed 1+
10 tot tst NB. Part 1 for test input still correct
26
(20 allrows par) tst NB. Part 2 for test input also still correct
56000011
(i. 4 5) nfzr@sumid@encode@int"0 _ par tst NB. 20 rows, 4x5, only one smaller than 20
27 28 27 26 25
24 23 22 23 24
25 14 27 28 29
28 27 26 25 24
Great, no more spurious entries that are less than 20, and the 14 in row 11 is the only one. While this is now correct, a straight forward sequential solution is still horribly slow, even if it breaks off computation when the location is found:
allrows_seq =: {{
vb=. nfzr@sumid@encode@int f. NB. verb returning first
for_row. i. x do.
if. x>col=. row vb y do. 0 4e6 #. row,col return. end.
end.
}}
20 allrows_seq par tst
56000011
timex'4e6 allrows par i15'
82.8379
This is a good moment to whip out one of J's more recently acquired features: multi-threading! First, I need to start a thread-pool executing 0 T. as many times as the difference of the number of cores ([: {. 8&T.) minus the threads already available (1&T.):
0&T.@0^:(0>.([: {. 8&T.)-1&T.) '' NB. spin up as many threads as useful
After starting the threads, using the run task conjunction(t.), vb t. 'worker' runs verb vb on a worker thread, encapsulating the return value in a special box named pyx, which is a very neat system for allowing concurrent execution: The call to t. returns control to the calling thread immediately after computation is started on a worker thread and the calling thread will only block when the box is opened (you can "rattle" the box using 4&T. to see the status without opening it as well, but that's not needed here). A bit like the box of Schrödinger's cat.
To parallelize allrows_seq above, I define a verb allrows to split the rows in batches of size nbatch, create a verb vb to run on each row, then run the verb in parallel on a batch. If any of the results is less than the amount of rows (x), then we've found the spot, calculate the "frequency", if not, continue to the next batch:
allrows =: {{ NB. parallel search all lines
nbatch=. 4000 NB. # rows per batch; tried out some values...
rowbatches=. (-nbatch) <\ i. x NB. group row indices in boxes per nbatch
vb=:nfzr@sumid@encode@int f. NB. verb returning first
for_b. rowbatches do. NB. For each batch ...
r=. > (>b) vb t.'worker' "0 _ y NB. run all lines on the workers
if. nbatch>offset=. r i.&1@:< x do. NB. Find the first with a hole
(>b) (+4e6&*)&(offset&{) r return. NB. if y+4e6*x
end.
end.
}}
part2 =: 4e6 allrows par
This speeds the solution up from 82 seconds to about 19 seconds on my phone (on my oldish laptop it goes from 104s to 56s). I tried a more complicated take on this as well, queuing all row batches at once, and rattle boxes, treating the ones returned first. This approach was not quicker for this problem, I suspect because the work the main thread is doing is minimal compared to the time it takes to complete a batch of rows.