day 15

5 files changed, 205 insertions, 0 deletions

diff --git a/benches/2022.rs b/benches/2022.rs
index 99becce..1bf0670 100644
--- a/benches/2022.rs
+++ b/benches/2022.rs
@@ -29,6 +29,8 @@ mod day9;
 mod day13;
 #[path = "../src/bin/2022/day14.rs"]
 mod day14;
+#[path = "../src/bin/2022/day15.rs"]
+mod day15;
 // NEXT MOD
 
 day!(2022, 1, day1);
@@ -45,6 +47,7 @@ day!(2022, 11, day11);
 day!(2022, 12, day12);
 day!(2022, 13, day13);
 day!(2022, 14, day14);
+day!(2022, 15, day15);
 // NEXT DAY
 
 fn bench_2022(c: &mut criterion::Criterion) {
@@ -64,6 +67,7 @@ fn bench_2022(c: &mut criterion::Criterion) {
             day_combined!(2022, 12, day12);
             day_combined!(2022, 13, day13);
             day_combined!(2022, 14, day14);
+            day_combined!(2022, 15, day15);
             // NEXT DAY COMBINED
         })
     });
@@ -86,5 +90,6 @@ criterion::criterion_main!(
     bench_2022day12,
     bench_2022day13,
     bench_2022day14,
+    bench_2022day15,
     // NEXT GROUP
 );
diff --git a/data/2022/15.txt b/data/2022/15.txt
new file mode 100644
index 0000000..ec728e8
--- /dev/null
+++ b/data/2022/15.txt
@@ -0,0 +1,32 @@
+Sensor at x=3428425, y=2345067: closest beacon is at x=3431988, y=2379841
+Sensor at x=928237, y=25774: closest beacon is at x=1212315, y=-161555
+Sensor at x=2061220, y=2396791: closest beacon is at x=2038311, y=2495160
+Sensor at x=1830400, y=2994568: closest beacon is at x=1910058, y=3117415
+Sensor at x=2485733, y=2625804: closest beacon is at x=2038311, y=2495160
+Sensor at x=1855873, y=3971916: closest beacon is at x=1910058, y=3117415
+Sensor at x=119582, y=3929652: closest beacon is at x=311197, y=4221202
+Sensor at x=1069031, y=3509672: closest beacon is at x=1910058, y=3117415
+Sensor at x=3368023, y=2213635: closest beacon is at x=3431988, y=2379841
+Sensor at x=3713877, y=2460862: closest beacon is at x=3431988, y=2379841
+Sensor at x=3593503, y=2174008: closest beacon is at x=3507689, y=2000000
+Sensor at x=501760, y=93436: closest beacon is at x=1212315, y=-161555
+Sensor at x=3712703, y=214999: closest beacon is at x=3507689, y=2000000
+Sensor at x=1594824, y=2790273: closest beacon is at x=1910058, y=3117415
+Sensor at x=2539549, y=3190814: closest beacon is at x=1910058, y=3117415
+Sensor at x=3522790, y=2671548: closest beacon is at x=3431988, y=2379841
+Sensor at x=1001452, y=1327490: closest beacon is at x=1212315, y=-161555
+Sensor at x=629209, y=2451628: closest beacon is at x=-416149, y=2226089
+Sensor at x=2636827, y=1146266: closest beacon is at x=3507689, y=2000000
+Sensor at x=3909, y=625124: closest beacon is at x=1212315, y=-161555
+Sensor at x=3950231, y=3688780: closest beacon is at x=3888160, y=3226725
+Sensor at x=3449978, y=2328058: closest beacon is at x=3431988, y=2379841
+Sensor at x=3974214, y=2582925: closest beacon is at x=3888160, y=3226725
+Sensor at x=82663, y=3225533: closest beacon is at x=311197, y=4221202
+Sensor at x=1958305, y=2292045: closest beacon is at x=2038311, y=2495160
+Sensor at x=3465738, y=2123353: closest beacon is at x=3507689, y=2000000
+Sensor at x=2940758, y=3884337: closest beacon is at x=2746166, y=4800483
+Sensor at x=3429173, y=2275591: closest beacon is at x=3431988, y=2379841
+Sensor at x=1527349, y=38565: closest beacon is at x=1212315, y=-161555
+Sensor at x=3049925, y=2498038: closest beacon is at x=3431988, y=2379841
+Sensor at x=1593202, y=3335178: closest beacon is at x=1910058, y=3117415
+Sensor at x=3175520, y=3230234: closest beacon is at x=3888160, y=3226725
diff --git a/src/bin/2022/day15.rs b/src/bin/2022/day15.rs
new file mode 100644
index 0000000..18f4fff
--- /dev/null
+++ b/src/bin/2022/day15.rs
@@ -0,0 +1,153 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+fn dist(a: (Row, Col), b: (Row, Col)) -> usize {
+    a.0.abs_diff(b.0).0 + a.1.abs_diff(b.1).0
+}
+
+#[derive(Debug, Copy, Clone)]
+struct Sensor {
+    pos: (Row, Col),
+    beacon: (Row, Col),
+    radius: usize,
+}
+
+impl Sensor {
+    fn new(pos: (Row, Col), beacon: (Row, Col)) -> Self {
+        Self {
+            pos,
+            beacon,
+            radius: dist(pos, beacon),
+        }
+    }
+
+    fn in_radius(&self, pos: (Row, Col)) -> bool {
+        dist(self.pos, pos) <= self.radius
+    }
+}
+
+pub struct Map {
+    sensors: Vec<Sensor>,
+    range_x: usize,
+    range_y: usize,
+    offset_x: usize,
+    offset_y: usize,
+}
+
+impl Map {
+    fn nearby_sensor(&self, pos: (Row, Col)) -> Option<Sensor> {
+        self.sensors
+            .iter()
+            .copied()
+            .find(|sensor| sensor.in_radius(pos))
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    let mut sensor_positions = vec![];
+    for line in parse::raw_lines(fh) {
+        let cap = regex_captures!(r"Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)", &line)
+            .ok_or_else(|| anyhow::anyhow!("no match"))?;
+        let sensor_x: i64 = cap[1].parse()?;
+        let sensor_y: i64 = cap[2].parse()?;
+        let beacon_x: i64 = cap[3].parse()?;
+        let beacon_y: i64 = cap[4].parse()?;
+        sensor_positions.push((sensor_x, sensor_y, beacon_x, beacon_y));
+    }
+    let min_x = sensor_positions
+        .iter()
+        .map(|x| x.0)
+        .chain(sensor_positions.iter().map(|x| x.2))
+        .min()
+        .ok_or_else(|| anyhow::anyhow!("empty list"))?;
+    let min_y = sensor_positions
+        .iter()
+        .map(|x| x.1)
+        .chain(sensor_positions.iter().map(|x| x.3))
+        .min()
+        .ok_or_else(|| anyhow::anyhow!("empty list"))?;
+    let max_x = sensor_positions
+        .iter()
+        .map(|x| x.0)
+        .chain(sensor_positions.iter().map(|x| x.2))
+        .max()
+        .ok_or_else(|| anyhow::anyhow!("empty list"))?;
+    let max_y = sensor_positions
+        .iter()
+        .map(|x| x.1)
+        .chain(sensor_positions.iter().map(|x| x.3))
+        .max()
+        .ok_or_else(|| anyhow::anyhow!("empty list"))?;
+
+    let range_x = (max_x - min_x) as usize;
+    let range_y = (max_y - min_y) as usize;
+    let offset_x = -min_x as usize + range_x;
+    let offset_y = -min_y as usize + range_y;
+
+    let mut sensors = vec![];
+    for sensor in sensor_positions {
+        let pos = (
+            Row((sensor.1 + offset_y as i64) as usize),
+            Col((sensor.0 + offset_x as i64) as usize),
+        );
+        let beacon = (
+            Row((sensor.3 + offset_y as i64) as usize),
+            Col((sensor.2 + offset_x as i64) as usize),
+        );
+        sensors.push(Sensor::new(pos, beacon));
+    }
+    Ok(Map {
+        sensors,
+        range_x,
+        range_y,
+        offset_x,
+        offset_y,
+    })
+}
+
+pub fn part1(map: Map) -> Result<i64> {
+    let row = Row(2_000_000 + map.offset_y);
+    let mut total = 0;
+    for col in (0..(3 * map.range_x)).map(Col) {
+        if map.sensors.iter().any(|sensor| sensor.beacon == (row, col)) {
+            continue;
+        }
+        if map.nearby_sensor((row, col)).is_some() {
+            total += 1;
+        }
+    }
+    Ok(total)
+}
+
+pub fn part2(map: Map) -> Result<usize> {
+    for row in (0..=4_000_000).map(|r| Row(r + map.offset_y)) {
+        let mut col = Col(map.offset_x);
+        loop {
+            if let Some(sensor) = map.nearby_sensor((row, col)) {
+                let row_radius = sensor.radius - sensor.pos.0.abs_diff(row).0;
+                col = sensor.pos.1 + row_radius + 1;
+                if col > Col(4_000_000 + map.offset_x) {
+                    break;
+                }
+            } else {
+                return Ok((col.0 - map.offset_x) * 4_000_000
+                    + (row.0 - map.offset_y));
+            }
+        }
+    }
+    Ok(0)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 15).unwrap()).unwrap()).unwrap(),
+        4737443
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 15).unwrap()).unwrap()).unwrap(),
+        11482462818989
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
index 9cc2ba6..f295b53 100644
--- a/src/bin/2022/main.rs
+++ b/src/bin/2022/main.rs
@@ -25,6 +25,7 @@ mod day9;
 mod day12;
 mod day13;
 mod day14;
+mod day15;
 // NEXT MOD
 
 #[paw::main]
@@ -45,6 +46,7 @@ fn main(opt: Opt) -> Result<()> {
         12 => advent_of_code::day!(2022, opt.day, opt.puzzle, day12),
         13 => advent_of_code::day!(2022, opt.day, opt.puzzle, day13),
         14 => advent_of_code::day!(2022, opt.day, opt.puzzle, day14),
+        15 => advent_of_code::day!(2022, opt.day, opt.puzzle, day15),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }
diff --git a/src/grid.rs b/src/grid.rs
index 659ef01..f099189 100644
--- a/src/grid.rs
+++ b/src/grid.rs
@@ -2,11 +2,24 @@
     Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd, Debug, Default,
 )]
 pub struct Row(pub usize);
+
 #[derive(
     Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd, Debug, Default,
 )]
 pub struct Col(pub usize);
 
+impl Row {
+    pub fn abs_diff(self, other: Self) -> Self {
+        Self(self.0.abs_diff(other.0))
+    }
+}
+
+impl Col {
+    pub fn abs_diff(self, other: Self) -> Self {
+        Self(self.0.abs_diff(other.0))
+    }
+}
+
 impl std::ops::Add<usize> for Row {
     type Output = Self;
     fn add(self, other: usize) -> Self::Output {