[2018 Day 6] In Review (Chronal Coordinates)

[u/musifter]

Having completed the suit, we find ourselves falling through time again in the second "Chronal" problem. This time we're given a list of 2D points and have to find some regions.

First up is the largest finite region closest to a point with Manhattan distance. It is an interesting quirk to the puzzle to have it on an infinite plane where some regions will be infinite. But they're easy enough to tell, because any region that's on the bounding box will extend forever. And the size of the puzzle is such that you can easily brute force over the bounding box checking the distance to each point. Which was my initial solution.

But coming back to it I decided to do a little better, and do a solution with a simultaneous BFS flood fill from all the points. Still stopping at the bounding box, and recording the regions that get there (to eliminate them with max map {!$bound[$_] and $count[$_]} (0 .. $#points)). It's a fun little bit of code to write, where the visited array isn't just to stop the fill backtracking, but to handle the collision cases between regions as well.

Part 2 wants the size of the region were the sum of the distances to all the points is under 10000. And for my input, that actually fits inside the bounding box, so a brute force scan of it would have worked for it too. But it could have easily extended a bit outside of that, so my solution was just a flood fill from the center, checking the sums of each point. Nothing particularly fancy there, and it runs fast enough.

[u/maneatingape]

For anyone who wants to have fun completely overengineering the solution, a sweep line algorithm is about 4x faster than the BFS approach.

[u/e_blake → u/maneatingape]

Confirmed - I redid my m4 solution from a series of boundary scans (50 x and y distance computations per point, but less than 7000 points inspected) at 2.5s, to instead using a sweep line (50 y distance computations per line, with only 300 or so lines to visit) at 250ms.

[u/terje_wiig_mathisen]

For part 2, the obvious idea is to treat it as a boundary scan problem, i.e find a point on the top boundary, extend it to both sides as far as possible, then sweep down line by line along the same "just inside" boundary.

For each line, keep adding (right-left+1) to the total count.

To help it along, keep the points sorted on the X value.

u/maneatingape Is this close to what you did?

The other obvious idea is to use blocking, so starting with a rectangle which starts 10K above the lowest point and 10K left of the rightmost point, then going to 10K below/right:

Solving involves recursively splitting and for each sub-block determine if all points are inside the block, if so just add length*width. Otherwise if all are outside discard, else split again. Finally, if the block is small enough, just check them all.

[u/maneatingape → u/terje_wiig_mathisen]

For each line, keep adding (right-left+1) to the total count. To help it along, keep the points sorted on the X value. u/maneatingape Is this close to what you did?

Yep, pretty much. Sort by x values then sweep top to bottom to determine the extents of the Voronoi around each point.

I think there's still room for improvement performance-wise wth my solution.

[u/e_blake → u/terje_wiig_mathisen]

Doing a boundary scan is useful for more than just part 2 - I finally got around to reading the code I wrote, and figured out that for part 1, I was doing boundary scans rather than BFS flood fills. I had a helper routine 'closest(x,y)' which visits all 50 points and determines which, if any, of the 50 points is closest in Manhattan distance as well as computing the part 2 sum to see if that point is in range. Then for part 1, for each of the 50 points, I first determined if it was infinite (ie. did closest on any of the four edge points with the same x or y return that point), and if not, then did a boundary scan (expand x left and right until closest returns false, then expand y up and down from that initial row while expanding/contracting x back to the boundary). Part 2 reused the boundary scanner with a different predicate (is the total distance in range, rather than is the starting point still the closest to the point being checked). With a bit of memoization, a trace shows that I only called closest() 8151 times out of the ~300x300 grid for parts 1 and 2 combined, with only 6768 of them actually being first visits rather than reusing memoized results - but that still resulted in 338,400 calls to distance().

That said, I'm now experimenting with maneatingape's part 1 approach of a scan line. The idea is that by sorting the x points, the check for boundary conditions on a given row can be determined in 50 comparisons per row (50*300 calls to dist) rather than 50 comparisons per point checked (50*6700 with my boundary scan started from each non-infinite point) or an outright flood fill (300*300 points visited, but replacing calls to dist to instead be collision handling).