day15

2 files changed, 161 insertions, 0 deletions

diff --git a/inputs/day15 b/inputs/day15
new file mode 100644
index 0000000..43321ab
--- /dev/null
+++ b/inputs/day15
@@ -0,0 +1,31 @@
+Sensor at x=3859432, y=2304903: closest beacon is at x=3677247, y=3140958
+Sensor at x=2488890, y=2695345: closest beacon is at x=1934788, y=2667279
+Sensor at x=3901948, y=701878: closest beacon is at x=4095477, y=368031
+Sensor at x=2422190, y=1775708: closest beacon is at x=1765036, y=2000000
+Sensor at x=2703846, y=3282799: closest beacon is at x=2121069, y=3230302
+Sensor at x=172003, y=2579074: closest beacon is at x=-77667, y=3197309
+Sensor at x=1813149, y=1311283: closest beacon is at x=1765036, y=2000000
+Sensor at x=1704453, y=2468117: closest beacon is at x=1934788, y=2667279
+Sensor at x=1927725, y=2976002: closest beacon is at x=1934788, y=2667279
+Sensor at x=3176646, y=1254463: closest beacon is at x=2946873, y=2167634
+Sensor at x=2149510, y=3722117: closest beacon is at x=2121069, y=3230302
+Sensor at x=3804434, y=251015: closest beacon is at x=4095477, y=368031
+Sensor at x=2613561, y=3932220: closest beacon is at x=2121069, y=3230302
+Sensor at x=3997794, y=3291220: closest beacon is at x=3677247, y=3140958
+Sensor at x=98328, y=3675176: closest beacon is at x=-77667, y=3197309
+Sensor at x=2006541, y=2259601: closest beacon is at x=1934788, y=2667279
+Sensor at x=663904, y=122919: closest beacon is at x=1618552, y=-433244
+Sensor at x=1116472, y=3349728: closest beacon is at x=2121069, y=3230302
+Sensor at x=2810797, y=2300748: closest beacon is at x=2946873, y=2167634
+Sensor at x=1760767, y=2024355: closest beacon is at x=1765036, y=2000000
+Sensor at x=3098487, y=2529092: closest beacon is at x=2946873, y=2167634
+Sensor at x=1716839, y=634872: closest beacon is at x=1618552, y=-433244
+Sensor at x=9323, y=979154: closest beacon is at x=-245599, y=778791
+Sensor at x=1737623, y=2032367: closest beacon is at x=1765036, y=2000000
+Sensor at x=26695, y=3049071: closest beacon is at x=-77667, y=3197309
+Sensor at x=3691492, y=3766350: closest beacon is at x=3677247, y=3140958
+Sensor at x=730556, y=1657010: closest beacon is at x=1765036, y=2000000
+Sensor at x=506169, y=3958647: closest beacon is at x=-77667, y=3197309
+Sensor at x=2728744, y=23398: closest beacon is at x=1618552, y=-433244
+Sensor at x=3215227, y=3077078: closest beacon is at x=3677247, y=3140958
+Sensor at x=2209379, y=3030851: closest beacon is at x=2121069, y=3230302
diff --git a/src/bin/day15.rs b/src/bin/day15.rs
new file mode 100644
index 0000000..6f28b3c
--- /dev/null
+++ b/src/bin/day15.rs
@@ -0,0 +1,130 @@
+use regex::Regex;
+
+static DAY: u8 = 15;
+
+fn main() {
+    let input = advent::read_lines(DAY);
+    println!("{DAY}a: {}", positions_without_beacon(&input, 2000000));
+    println!("{DAY}b: {}", tuning_frequency(&input, 0, 4000000));
+}
+
+#[derive(PartialEq, Eq)]
+struct Position {
+    x: isize,
+    y: isize,
+}
+
+impl Position {
+    fn distance(&self, other: &Self) -> isize {
+        (self.x.abs_diff(other.x) + self.y.abs_diff(other.y)) as isize
+    }
+}
+
+struct SensorReading {
+    sensor: Position,
+    closest: Position,
+    range: isize,
+}
+
+impl SensorReading {
+    fn new(input: &str) -> SensorReading {
+        let re = Regex::new("Sensor at x=(-?[0-9]+), y=(-?[0-9]+): closest beacon is at x=(-?[0-9]+), y=(-?[0-9]+)").unwrap();
+
+        let cap = re.captures(input).expect("input should match regex");
+        let sensor = Position {
+            x: cap[1].parse::<isize>().unwrap(),
+            y: cap[2].parse::<isize>().unwrap(),
+        };
+        let closest = Position {
+            x: cap[3].parse::<isize>().unwrap(),
+            y: cap[4].parse::<isize>().unwrap(),
+        };
+        let range = sensor.distance(&closest);
+        SensorReading { sensor, closest, range }
+    }
+
+    fn signal_in_range(&self, pos: &Position) -> bool {
+        self.sensor.distance(pos) <= self.range
+    }
+}
+
+fn positions_without_beacon(input: &[String], y: isize) -> usize {
+    let readings = input.iter()
+                        .map(|x| SensorReading::new(x))
+                        .collect::<Vec<_>>();
+
+    let min_x = readings.iter()
+                        .map(|r| r.sensor.x - r.range)
+                        .min().unwrap();
+    let max_x = readings.iter()
+                        .map(|r| r.sensor.x + r.range)
+                        .max().unwrap();
+
+    let mut possible_positions = 0;
+    for x in min_x ..= max_x {
+        let pos = Position { x, y };
+        let in_range = readings.iter()
+                               .any(|r| r.signal_in_range(&pos));
+        let is_beacon = readings.iter()
+                                .any(|r| r.closest == pos);
+        if in_range && !is_beacon {
+            possible_positions += 1;
+        }
+    }
+    possible_positions
+}
+
+fn tuning_frequency(input: &[String], min_coord: isize, max_coord: isize) -> isize {
+    let readings = input.iter()
+                        .map(|x| SensorReading::new(x))
+                        .collect::<Vec<_>>();
+
+    let mut x = min_coord;
+    let mut y = min_coord;
+    loop {
+        if x > max_coord {
+            x = min_coord;
+            y += 1;
+        }
+        let pos = Position { x, y };
+        let reading = readings.iter()
+                              .find(|r| r.signal_in_range(&pos));
+
+        let reading = match reading {
+            Some(r) => r,
+            None => return x * 4000000 + y,
+        };
+
+        let dist_y = reading.sensor.y.abs_diff(pos.y) as isize;
+        /* move position outside of range of current sensor */
+        x = reading.sensor.x + reading.range + 1 - dist_y;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "Sensor at x=2, y=18: closest beacon is at x=-2, y=15",
+            "Sensor at x=9, y=16: closest beacon is at x=10, y=16",
+            "Sensor at x=13, y=2: closest beacon is at x=15, y=3",
+            "Sensor at x=12, y=14: closest beacon is at x=10, y=16",
+            "Sensor at x=10, y=20: closest beacon is at x=10, y=16",
+            "Sensor at x=14, y=17: closest beacon is at x=10, y=16",
+            "Sensor at x=8, y=7: closest beacon is at x=2, y=10",
+            "Sensor at x=2, y=0: closest beacon is at x=2, y=10",
+            "Sensor at x=0, y=11: closest beacon is at x=2, y=10",
+            "Sensor at x=20, y=14: closest beacon is at x=25, y=17",
+            "Sensor at x=17, y=20: closest beacon is at x=21, y=22",
+            "Sensor at x=16, y=7: closest beacon is at x=15, y=3",
+            "Sensor at x=14, y=3: closest beacon is at x=15, y=3",
+            "Sensor at x=20, y=1: closest beacon is at x=15, y=3",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+
+        assert_eq!(positions_without_beacon(&input, 10), 26);
+        assert_eq!(tuning_frequency(&input, 0, 20), 56000011);
+    }
+}