Module aoc::year2018::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.