Module day06

Chronal Coordinates

Both parts can be solved with a BFS approach. The bounding box of the coordinates is roughly 300 wide by 300 high so the total complexity would be approximately O(90,000).

A much faster approach for both parts is a sweep line algorithm. We sweep from top to bottom (minimum y coordinate to maximum y coordinate) computing the area a slice at a time. There are 50 coordinates so the complexity of this approach is much lower at approximately O(300 * 50) = O(15000).

Structs

Input

Functions

next 🔒

Calculate the change in distance moving down or right.

parse

Parse points while keeping track of the min and max y coordinates.

part1

Sweep line approach computing the area of each finite coordinate. A coordinate has infinite area if any point on the edge of the bounding box formed by the minimum and maximum x and y coordinates is closest to that coordinate.

part2

part2_testable

Sweep from top to bottom to find the size of the roughly circular area that is less than a specified maximum distance from all other points.

prev 🔒

Calculate the change in distance moving left or up.