Function aoc::y22d15::y22d15p2

pub fn y22d15p2(input: &str, max: i32) -> u64

The solution for part two of the day fifteen challenge.

I originally solved this challenge by checking the perimeter of each sensor (i.e., manhattan distance to beacon/range plus one) to see if it was in range of any other sensors. If it was not, then we found the free space and the missing beacon. However, after trying to solve a test that would only fail occasionally I found a different method based on this comment on the Advent of Code subreddit. The strategy is to instead compute the lines that surround the perimeter of each sensor then we can compute the intersection and see if these reduced number of points to check is free from any other scanners (just as I had implemented it before). As before, if the intersection is outside of the range of all of the other sensors then we’ve found the solution.

Given the input as a string and the upper bound of the search box as function parameters we can start by parsing the input as in part one to locate each of our sensors and their range based on the coordinates of the beacon that they detect. The range, as before, is computed as the Manhattan distance from the sensor to its beacon. Then we can compute the four bounding diagonals. Then we can loop through each set of diagonals and compute the intersection. If the intersection is within bounds then we simply check it against the every sensor to see if its in range. Once we have found an intersection that’s not in range then we’re done and can compute the answer based on the challenge prompt: the value of the x coordinate times 4,000,000 plus the value of the y coordinate. +

Example

// probably read the from the input file...
let input = concat!(
    "Sensor at x=0, y=0: closest beacon is at x=-2, y=0\n",
    "Sensor at x=4, y=0: closest beacon is at x=6, y=0\n",
    "Sensor at x=2, y=3: closest beacon is at x=0, y=3\n",
    "Sensor at x=3, y=4: closest beacon is at x=3, y=6\n",
    "Sensor at x=7, y=2: closest beacon is at x=9, y=2\n",
    "Sensor at x=6, y=6: closest beacon is at x=6, y=8\n",
    "Sensor at x=0, y=6: closest beacon is at x=0, y=8\n",
);
assert_eq!(y22d15p2(input, 6), 20000003);