×

17
18

Spoilers[2022 Day 15 part 2] Comparison of different approaches (self.adventofcode)

submitted by RGodlike

I ended up implementing this part 3 times and comparing running speeds.

Initial implemention was running part 1 up to 4000000 times (stopping when the answer was found). Since my part 1 was fairly fast (using complex numbers to keep track of coordinates and intervals to check which x values for row 2000000 are within range). Duration: 327.97s. Not bad for a 4 line implementation.

Second implementation was after I realized the point we're looking for has to be on at least 4 different borders of sensor ranges. I collected all the border points (at Manhattan Distance of beacon_distance+1), filtered the ones that were on less than 4 borders, and for the points that were left I checked whether they were in range of any sensors. Seemed real smart at the time. Duration: 10+ min. After 10 min I hadn't started the final step yet, and I decided to stop it.

Third implemention is a faster version of the second one. Instead of creating a master list of all border points, I just go over each sensor, get the points on the border, and check for each whether they're in range of any sensors, stopping the program if one is found outside all the ranges. Duration: 3.77s. Baffled that it's such a jump from the second implementation.

TL:DR: Dont' sort or count all the occurances of a list with 85 million coordinates in it.

all 18 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Background-Vegetable 6 points7 points  (5 children)

How about

If you are finding borders anyway, you could find out where two borders are only one coordinate apart. The input guarantees the target is only 1 coordinate big.

even bigger spoiler:

If you can find two pairs of such borders, all you have to do is find an intersection....

0.077ms on my PC :)

[–]Diderikdm 2 points3 points  (2 children)

Did something pretty similar, find all intersection points of the diamonds of (manhattan + 1) and check these points against the distance to all scanners (in my case (288 intersections * 34 scanners) options -> runs in ~0.9 ms

^ is even more efficient though

[–]just_a_cactus 0 points1 point  (1 child)

I don’t quite understand how come you’ve got only 288 intersections, I used your approach and have gotten 400,000+. The solution came up in less than a minute anyway but still?

[–][deleted] 1 point2 points  (0 children)

What if the beacon is in the corner of the allowed area

[–]RGodlike[S] 0 points1 point  (0 children)

How are you comparing the distance between borders? I'm able to speed it up a little bit but still 3.33s, by finding two sensors at distance range_1 + range_2 + 2 and looping through all points on the intersection. But since that's still ~450000 coordinates (for which I have to check the distance to all other sensors) it's not super fast.

EDIT: Nevermind, the issue wasn't looping over all the points, but how I was creating the borders. Since I was only using complete borders (4 sides) I was using the intersection of both to get the shared border. That was taking the most time; cleverly only generating the border in the direction of the other sensor made it run in 0.74s. Still not your speed, but sub-second at least.

[–]1234abcdcba4321 2 points3 points  (0 children)

I like how there's so many viable approaches to this problem.

Like, how about this one? https://old.reddit.com/r/adventofcode/comments/zmcn64/2022_day_15_solutions/j0av419/ (...the second one, not the first)

[–]paul_sb76 2 points3 points  (5 children)

Using C# on an old laptop:

My first solution was also running the part 1 check 4000000 times. Fortunately Part 1 was implemented well (with interval intersections), so that was ~8 seconds.

That bugged me a bit, so I tried to find a solution where the complexity is independent of the grid size, indeed based on line intersections, or more precisely: for every y that contains a sensor (32 sensors): calculate all intervals at that y. Check the overlap between the intervals, and based on that, find a short list of only 47 y-coordinates where I needed to do the part 1 calculation. Running time: 4ms. I know it can be optimized further, but this is good enough for me. :-)

[–]daggerdragon[M] 1 point2 points  (0 children)

FYI: we can see your spoiler text on old.reddit and mobile apps because there's a space after the opening >! tag. Please remove that space for the spoiler Markdown to work properly.

[–]RGodlike[S] 1 point2 points  (1 child)

That's a very nice two-pronged approach.

Obviously it doesn't work for the format but I'd love an alternative leaderboard for AoC based on computation speed. Puzzles release at 5am local time for me so regular leaderboards aren't doable, but an efficiency-based once would cause me to go deep on some days for sure.

[–]paul_sb76 0 points1 point  (0 children)

I have no illusions about being on such a leaderboard either. ;-) I'm happy if I can achieve (or get close to) the optimal asymptotic complexity (big-O) for the puzzle. Today was an interesting puzzle in that regard, just like Day 6.

[–]Benur197 0 points1 point  (1 child)

Sorry for the late reply, but I'm trying to figure out a solution that was similar to what you've done, I dont get how you get the 47 y-coordinates from the list of 32 intervals

[–]paul_sb76 0 points1 point  (0 children)

I sort the sensors by their y-position, and then loop over them in increasing order. For every such sensor y, I consider all sensors with a lower y-coordinate, and get their "coverage interval" at the current y-coordinate. I sort those intervals (intervals that are fully contained in others may be ignored), and for every subsequent pair of intervals, I get a y-coordinate that should be inspected.

For instance, if the current y=10, and I have two sensors that cover the x-intervals [3,8] and [6,12] at that y, then I can conclude that at y=12, there may be a point (with x=7) that's not covered by the current set of intervals (though it may be covered by a sensor that is not currently considered, with higher y-coordinate). This y=12 is then added to the candidate set (of size 47 for me), ready to be inspected later, while considering the full set of sensors.

[–]clbrri 2 points3 points  (0 children)

I am sporting a vintage computing PC theme.

Also did several implementations. First got the second star with a naive extension of the solution for first case, plus something I thought was an optimization, which only optimized about half of the runtime. That took ~10 minutes to run.

This first algorithm was:

Loop through all y scanlines from 0..4_000_000, then for each scanline, find the intersection min-max overlap of each scanner diamond on that scanline.

Then from the union of those overlap ranges, see if there is a gap, which would be the answer. If not, interpret from the depth of those overlap pairs a "speed skip" to the y scanline position, that will be used to fast track through the iteration, to avoid needing to look at each scanline.

Then the second working program was a fix/improvement to the above algorithm, which optimized runtime down from 10 minutes to 822 milliseconds.

This fix was:

Track for each min-max scanline at each scanline, whether that scanline corresponds to a "waxing" or "waning" (growing or shrinking) scanline, to detect parallel scanline pairs where one is growing and the other one is shrinking next to it. This allows speed skipping in more scenarios (a bit difficult to explain in text maybe..)

Then took a walk outside and realized that

this scanline sweeping algorithm can be greatly simplified by rotating the coordinate system by 45 degrees, which makes all the scanner diamond shapes axis-aligned bounding boxes.

Then a top-down scanline sort-and-sweep algorithm trucks through those really fast, and at the end, rotate the coordinates back to the original coordinate system.

This gave a final runtime of 112 milliseconds on that 16MHz 386SX PC. Today was a fun one, I see there are quite a lot of different solutions to this out there, that I wouldn't have ever thought about!

Here is my final solution: https://imgur.com/a/rMyxxWQ

[–]hermesko 1 point2 points  (1 child)

Can elaborate why the number 4?

[–]RGodlike[S] 2 points3 points  (0 children)

Thinking it all out, I think it actually only has to be 2, and then two more sensors where it's within range 2 of it's border. Made the mistake of thinking we're looking for a square of size 1, and a square has 4 sides, but due to the coordinates being integers two of those sides can actually be one further away.

Nevertheless, for my answer it's actually on 4 borders and still didn't terminate.

[–]Zanthous 0 points1 point  (0 children)

So I ended up doing a semi-brute force approach for part 2 in the end, I just checked very point around every edge of every sensor's range which is still reasonably fast. I tried a ton of other stuff but they all failed for one reason or another (bad assumptions on how things work as usual). I'm going to have to go back over some better solutions here slowly.

[–]hrunt 0 points1 point  (0 children)

I started by taking Part 1 and merging the "cannot be beacon" range sets for every y-value for each sensor. The solution is in the y-value with two ranges in the range set. That took about 40s to

After that, from some of the conversation in the channel I gathered that the distress signal had to be adjacent to four bounding box intersections. I took each sensor, calculated it's four bounding corners (A, B, C, D), then calculated from those its four edges (AB, BC, CD, DA). Then I cycled through each sensor and determined whether its edges intersected with any other sensor's edges. For each intersection found, I looked at the four adjacent points and determined if they were inside any sensor's range. If an adjacent point was not in any sensor's range, that was the solution.

Total runtime for both parts (including interpreter spin-up) was 90ms. If I add a timer around just finding the distress frequency, it says 2.3ms., and it says 3.8ms for parsing the input and running both parts. I have not tried to optimize further.

Code for both solutions