1 files changed, 167 insertions, 0 deletions
diff --git a/2022/src/bin/day_15.rs b/2022/src/bin/day_15.rs
new file mode 100644
index 0000000..be7645d
--- /dev/null
+++ b/2022/src/bin/day_15.rs
@@ -0,0 +1,167 @@
+use nom::{
+    bytes::complete::tag,
+    character::complete::{i64, line_ending},
+    combinator::map,
+    multi::separated_list1,
+    sequence::tuple,
+    IResult,
+};
+use std::{collections::BTreeSet, fs, ops::Range};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_15.txt")?;
+    let sensors = Sensors::parser(&input).unwrap().1;
+
+    dbg!(sensors.count_covered_non_beacons_in_row(2000000));
+
+    dbg!(sensors
+        .find_hole_in_range(
+            Point { x: 0, y: 0 }..Point {
+                x: 4000001,
+                y: 4000001
+            }
+        )
+        .tuning_frequency());
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct Sensors(Vec<Sensor>);
+
+#[derive(Debug, Clone)]
+struct Sensor {
+    center: Point,
+    closest_beacon: Point,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Point {
+    x: i64,
+    y: i64,
+}
+
+impl Sensors {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(separated_list1(line_ending, Sensor::parser), Sensors)(input)
+    }
+
+    fn ranges_in_row(&self, y: i64) -> Vec<Range<i64>> {
+        let mut ranges: Vec<Range<i64>> = self
+            .0
+            .iter()
+            .filter_map(|s| s.get_range_in_row(y))
+            .collect();
+
+        let mut any_changes = true;
+        while any_changes {
+            any_changes = false;
+            ranges.sort_unstable_by_key(|r| r.start);
+            if ranges.len() > 0 {
+                for i in 0..ranges.len() - 1 {
+                    if ranges[i].end > ranges[i + 1].start {
+                        ranges[i + 1].start = ranges[i].end;
+                        any_changes = true;
+                    }
+                }
+                ranges.retain(|r| !r.is_empty());
+            }
+        }
+        ranges
+    }
+
+    fn count_covered_non_beacons_in_row(&self, y: i64) -> u64 {
+        let ranges = self.ranges_in_row(y);
+
+        // these beacons are all distinct, and are all definitely on
+        // the line because the beacons are how the line is found!
+        let beacons: BTreeSet<i64> = self
+            .0
+            .iter()
+            .filter(|s| s.closest_beacon.y == y)
+            .map(|s| s.closest_beacon.x)
+            .collect();
+
+        ranges.into_iter().map(|r| r.count() as u64).sum::<u64>() - beacons.len() as u64
+    }
+
+    fn find_hole_in_range(&self, field_range: Range<Point>) -> Point {
+        let full_row_len = field_range.end.x - field_range.start.x;
+        for y in field_range.start.y..field_range.end.y {
+            let ranges = self.ranges_in_row(y);
+            let count = ranges
+                .into_iter()
+                .map(|mut r| {
+                    if r.start < field_range.start.x {
+                        r.start = field_range.start.x
+                    };
+                    if r.end > field_range.end.x {
+                        r.end = field_range.end.x
+                    };
+                    r
+                })
+                .map(|r| r.count() as i64)
+                .sum::<i64>();
+            if full_row_len != count {
+                for x in field_range.start.x..field_range.end.x {
+                    let p = Point { x, y };
+                    if !self.0.iter().any(|s| s.contains(&p)) {
+                        return p;
+                    }
+                }
+            }
+        }
+        panic!("Didn't find the hole as specified!")
+    }
+}
+
+impl Sensor {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((
+                tag("Sensor at "),
+                Point::parser,
+                tag(": closest beacon is at "),
+                Point::parser,
+            )),
+            |(_, center, _, closest_beacon)| Sensor {
+                center,
+                closest_beacon,
+            },
+        )(input)
+    }
+
+    fn get_range_in_row(&self, y: i64) -> Option<Range<i64>> {
+        let dy = (self.center.y - y).abs();
+        let dx = self.radius() - dy;
+        if dx < 0 {
+            None
+        } else {
+            let min_x = self.center.x - dx;
+            let max_x = self.center.x + dx;
+            Some(min_x..(max_x + 1))
+        }
+    }
+
+    fn radius(&self) -> i64 {
+        (self.center.x - self.closest_beacon.x).abs()
+            + (self.center.y - self.closest_beacon.y).abs()
+    }
+
+    fn contains(&self, other: &Point) -> bool {
+        let d = (self.center.x - other.x).abs() + (self.center.y - other.y).abs();
+        d <= self.radius()
+    }
+}
+
+impl Point {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(tuple((tag("x="), i64, tag(", y="), i64)), |(_, x, _, y)| {
+            Point { x, y }
+        })(input)
+    }
+
+    fn tuning_frequency(&self) -> i64 {
+        self.x * 4000000 + self.y
+    }
+}