Using a binary space partition tree for Advent of Code 2022 #15

I 100%ed advent of code for the first time this year. Not sure I’ll have the energy to do it again another year, it kind of dominated my life over December when I should maybe have been getting my holiday shopping done, etcetera. I used Rust and got better at it but am still a n00b and found myself doing workarounds rather than idiomatic rusty ways of doing things as I tried to get the problems solved. Rust may be good for software engineering but for one-off algorithmic puzzles that you intend to throw away the things that make it great at preventing future bugs get in the way. (Insert rant here about how ability to solve algorithmic puzzles may be orthogonal or even antithetical to ability to write maintainable code, and so it’s problematic that the FAANG industry tends to hire for algorithmic puzzle solvers. But I’m not bitter.)

I was pretty happy with what I eventually came up with for #15 Part 2 - https://adventofcode.com/2022/day/15 - friends at work discovered one fast way of solving the problem, which was only considering the borders of these ginormous zones that we were trying to find a single cell in. That greatly reduced the space the algorithm had to search, and ran in under a second. (It took me a while to get that insight, so insert another rant about FAANG interviews and how they expect us to find insights under pressure in minutes. I want to write a whole article about that someday.)

I originally did something much slower (https://github.com/JamieFristrom/AdventOfCode2022) but thinking about it later the zones reminded me of the good old days when we used BSP trees for collision with the environment, thanks to the pioneering work of John Carmack. Some fairly elegant simple algorithms could quickly carve a space into zones and theoretically take us from using this linear algorithm which had to consider every one of hundreds of thousands of points in the map into a more complex (n log n) algorithm with a much smaller n – n is the number of zones, and there were only  about twenty of those. Assuming the tree balanced decently, and the operation itself wasn’t too expensive, it could well be faster than the big search – and it’s also a more general solution that doesn’t assume there’s only one valid point.

I didn’t have the energy to write a new BSP implementation myself, but digging around online I found something nice. A 2D BSP library for Java - https://commons.apache.org/proper/commons-geometry/tutorials/bsp-tree.html - was the easiest-looking library I found that that supported CSG style construction, so I’d be able to find a union of the zones. My theory was confirmed, it ran faster on my laptop (about .5 seconds) than the  Took .5 seconds to run on my laptop and the output was a nice boundary circling the good pixel.

Code Snippet

31. public final class AdventOfCode15 {
32.  
33.     /** No instantiation. */
34.     public static double manhattanDistance(double x0, double y0, double x1, double y1) {
35.         return Math.abs(x1-x0) + Math.abs(y1-y0);
36.     }
37.     /** Tutorial code entry point.
38.      * @param args command arguments; if given, the first argument is used as the location of
39.      *      output folder
40.      */
41.     public static void main(final String[] args) {
42.         SensorBeacon[] sensorBeacons = getPuzzleData();
43.  
44.         System.out.println(sensorBeacons[0].sensorX);
45.  
46.         final File outputFolder = new File(args.length > 0 ? args[0] : ".");
47.         //final BSPTreeSVGWriter svgWriter = new BSPTreeSVGWriter(Bounds2D.from(Vector2D.of(-1000000, -1000000), Vector2D.of(6000000, 6000000)));
48.  
49.         Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-3);
50.        
51.         RegionBSPTree2D searchSpace = LinePath.fromVertexLoop(Arrays.asList(
52.             Vector2D.of(0,0),
53.            
54.             Vector2D.of(0,4000000),
55.             Vector2D.of(4000000,4000000),
56.            
57.             Vector2D.of(4000000,0)
58.         ), precision).toTree();
59.  
60.         for (int i=0;i<sensorBeacons.length;i++) {
61.             double manhattanDist = manhattanDistance(sensorBeacons[i].sensorX, sensorBeacons[i].sensorY, sensorBeacons[i].beaconX, sensorBeacons[i].beaconY);
62.  
63.             RegionBSPTree2D sensorZone = LinePath.fromVertexLoop(Arrays.asList(
64.                 Vector2D.of(sensorBeacons[i].sensorX, sensorBeacons[i].sensorY - manhattanDist),
65.                 Vector2D.of(sensorBeacons[i].sensorX + manhattanDist, sensorBeacons[i].sensorY),
66.                 Vector2D.of(sensorBeacons[i].sensorX, sensorBeacons[i].sensorY + manhattanDist),
67.                 Vector2D.of(sensorBeacons[i].sensorX - manhattanDist, sensorBeacons[i].sensorY)
68.             ), precision).toTree();
69.  
70.             searchSpace.union(searchSpace, sensorZone);
71.         }
72.  
73.         //svgWriter.write(searchSpace, new File(outputFolder, "aoc.svg"));
74.  
75.         List<LinePath> boundaries = searchSpace.getBoundaryPaths();
76.         for (int i=0; i<boundaries.size(); i++) {
77.             System.out.println("LinePath ");
78.             for (int j=0; j<boundaries.get(i).getVertexSequence().size(); j++) {
79.                 System.out.println(boundaries.get(i).getVertexSequence().get(j));
80.             }  
81.         }
82.     }
83.  
84.     public static SensorBeacon[] getPuzzleData() {
85.        
86.         SensorBeacon[] sensorBeacons = new SensorBeacon[] {
87.             new SensorBeacon(2885528,2847539,2966570,2470834),
88.             new SensorBeacon(2224704,1992385,2018927,2000000),
89.             new SensorBeacon(3829144,1633329,2966570,2470834),
90.             new SensorBeacon(43913,426799,152363,369618),
91.             new SensorBeacon(2257417,2118161,2386559,2090397),
92.             new SensorBeacon(8318,3994839,-266803,2440278),
93.             new SensorBeacon(69961,586273,152363,369618),
94.             new SensorBeacon(3931562,3361721,3580400,3200980),
95.             new SensorBeacon(476279,3079924,-266803,2440278),
96.             new SensorBeacon(2719185,2361091,2966570,2470834),
97.             new SensorBeacon(2533382,3320911,2260632,3415930),
98.             new SensorBeacon(3112735,3334946,3580400,3200980),
99.             new SensorBeacon(1842258,3998928,2260632,3415930),
100.             new SensorBeacon(3712771,3760832,3580400,3200980),
101.             new SensorBeacon(1500246,2684955,2018927,2000000),
102.             new SensorBeacon(3589321,142859,4547643,-589891),
103.             new SensorBeacon(1754684,2330721,2018927,2000000),
104.             new SensorBeacon(2476631,3679883,2260632,3415930),
105.             new SensorBeacon(27333,274008,152363,369618),
106.             new SensorBeacon(158732,2405833,-266803,2440278),
107.             new SensorBeacon(2955669,3976939,3035522,4959118),
108.             new SensorBeacon(1744196,13645,152363,369618),
109.             new SensorBeacon(981165,1363480,2018927,2000000),
110.             new SensorBeacon(2612279,2151377,2386559,2090397),
111.             new SensorBeacon(3897,2076376,-266803,2440278),
112.             new SensorBeacon(2108479,1928318,2018927,2000000),
113.             new SensorBeacon(1913043,3017841,2260632,3415930),
114.             new SensorBeacon(2446778,785075,2386559,2090397),
115.             new SensorBeacon(2385258,2774943,2386559,2090397),
116.             new SensorBeacon(3337656,2916144,3580400,3200980),
117.             new SensorBeacon(380595,66906,152363,369618),
118.             new SensorBeacon(1593628,3408455,2260632,3415930)
119.         };
120.  
121.         return sensorBeacons;
122.     }
123. }
124.  
125. class SensorBeacon {
126.     // from looking at the sample data, which only goes up to 5 million or so, double precision shouldn't be lossy
127.     public double sensorX;
128.     public double sensorY;
129.     public double beaconX;
130.     public double beaconY;
131.  
132.     public SensorBeacon(double _sensorX, double _sensorY, double _beaconX, double _beaconY) {
133.         sensorX = _sensorX;
134.         sensorY = _sensorY;
135.         beaconX = _beaconX;
136.         beaconY = _beaconY;
137.     }
138. }