1 files changed, 130 insertions, 0 deletions
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);
+    }
+}