Day 15

2 files changed, 205 insertions, 0 deletions

diff --git a/2022/inputs/day_15.txt b/2022/inputs/day_15.txt
new file mode 100644
index 0000000..888e520
--- /dev/null
+++ b/2022/inputs/day_15.txt
@@ -0,0 +1,38 @@
+Sensor at x=2300471, y=2016823: closest beacon is at x=2687171, y=2822745
+Sensor at x=1315114, y=37295: closest beacon is at x=1671413, y=43557
+Sensor at x=1039523, y=3061589: closest beacon is at x=1570410, y=3710085
+Sensor at x=214540, y=3768792: closest beacon is at x=-355567, y=3900317
+Sensor at x=1641345, y=3524291: closest beacon is at x=1570410, y=3710085
+Sensor at x=1016825, y=1450262: closest beacon is at x=745731, y=2000000
+Sensor at x=2768110, y=3703050: closest beacon is at x=3133588, y=3984216
+Sensor at x=2213658, y=3522463: closest beacon is at x=1570410, y=3710085
+Sensor at x=3842967, y=3381135: closest beacon is at x=3839159, y=3421933
+Sensor at x=3952516, y=2683159: closest beacon is at x=3213800, y=2708360
+Sensor at x=172892, y=369117: closest beacon is at x=-228964, y=1438805
+Sensor at x=3999720, y=3498306: closest beacon is at x=3839159, y=3421933
+Sensor at x=1596187, y=307084: closest beacon is at x=1671413, y=43557
+Sensor at x=3863253, y=3406760: closest beacon is at x=3839159, y=3421933
+Sensor at x=3927553, y=3450758: closest beacon is at x=3839159, y=3421933
+Sensor at x=2774120, y=3228484: closest beacon is at x=2687171, y=2822745
+Sensor at x=3897140, y=3418751: closest beacon is at x=3839159, y=3421933
+Sensor at x=1880329, y=2843697: closest beacon is at x=2687171, y=2822745
+Sensor at x=33790, y=3243415: closest beacon is at x=-355567, y=3900317
+Sensor at x=438583, y=2647769: closest beacon is at x=745731, y=2000000
+Sensor at x=1540347, y=3177380: closest beacon is at x=1570410, y=3710085
+Sensor at x=3120086, y=3997791: closest beacon is at x=3133588, y=3984216
+Sensor at x=3428967, y=3105227: closest beacon is at x=3213800, y=2708360
+Sensor at x=2898335, y=1037911: closest beacon is at x=3213800, y=2708360
+Sensor at x=3456260, y=3578627: closest beacon is at x=3839159, y=3421933
+Sensor at x=1859971, y=3999725: closest beacon is at x=1570410, y=3710085
+Sensor at x=3147730, y=3999322: closest beacon is at x=3133588, y=3984216
+Sensor at x=3920847, y=71575: closest beacon is at x=3826138, y=-255533
+Sensor at x=956723, y=3999438: closest beacon is at x=1570410, y=3710085
+Sensor at x=1193760, y=3758205: closest beacon is at x=1570410, y=3710085
+Sensor at x=3999446, y=1929369: closest beacon is at x=3213800, y=2708360
+Sensor at x=1434466, y=2254087: closest beacon is at x=745731, y=2000000
+Sensor at x=200365, y=1856636: closest beacon is at x=745731, y=2000000
+Sensor at x=1859710, y=31159: closest beacon is at x=1671413, y=43557
+Sensor at x=3712613, y=3930105: closest beacon is at x=3133588, y=3984216
+Sensor at x=1660185, y=2900: closest beacon is at x=1671413, y=43557
+Sensor at x=1497065, y=93501: closest beacon is at x=1671413, y=43557
+Sensor at x=3832823, y=3346266: closest beacon is at x=3839159, y=3421933
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
+    }
+}