Day 15 2022

3 files changed, 128 insertions, 0 deletions

diff --git a/2022/15/a.rs b/2022/15/a.rs
new file mode 100644
index 0000000..7b87150
--- /dev/null
+++ b/2022/15/a.rs
@@ -0,0 +1,30 @@
+use std::cmp::max;
+use std::collections::HashSet;
+mod common;
+use common::*;
+
+fn main() {
+    const Y: i64 = 2000000;
+    let sensors = read_sensors_from_stdin();
+    let mut ranges = sensors.iter()
+        .map(|s| s.get_range(Y))
+        .filter(|r| r.left <= r.right)
+        .collect::<Vec<_>>();
+    ranges.sort();
+    let mut current = Range { left: i64::MIN, right: i64::MIN };
+    let mut sum = 0;
+    for r in ranges {
+        current = Range {
+            left: max(current.right+1, r.left),
+            right: max(current.right, r.right)
+        };
+        sum += (current.right - current.left + 1) as usize;
+    }
+    sum -= sensors.iter()
+        .map(|s| s.b)
+        .collect::<HashSet<_>>() // Remove duplicates
+        .iter()
+        .filter(|b| b.y == Y)
+        .count();
+    println!("{sum}");
+}
diff --git a/2022/15/b.rs b/2022/15/b.rs
new file mode 100644
index 0000000..3c321e1
--- /dev/null
+++ b/2022/15/b.rs
@@ -0,0 +1,33 @@
+use std::cmp::max;
+mod common;
+use common::*;
+
+#[allow(non_snake_case)]
+fn get_pos(sensors: &Vec<Sensor>, N: i64) -> Pos {
+    for i in 0..=N {
+        let mut ranges = sensors.iter()
+            .map(|s| s.get_range(i))
+            .filter(|r| r.left <= r.right)
+            .collect::<Vec<_>>();
+        ranges.sort();
+        let mut lastr = ranges[0].right;
+        for j in 1..ranges.len() {
+            if lastr + 1 < ranges[j].left {
+                return Pos { x: lastr+1, y: i };
+            }
+            lastr = max(lastr, ranges[j].right);
+        }
+        if lastr < N {
+            return Pos { x: N, y: i };
+        }
+    }
+    panic!("Position not found");
+}
+
+fn main() {
+    const N: i64 = 4000000;
+    const M: i64 = 4000000;
+    let sensors = read_sensors_from_stdin();
+    let p = get_pos(&sensors, N);
+    println!("x = {}, y = {} -> {}", p.x, p.y, p.x * M + p.y);
+}
diff --git a/2022/15/common.rs b/2022/15/common.rs
new file mode 100644
index 0000000..bece484
--- /dev/null
+++ b/2022/15/common.rs
@@ -0,0 +1,65 @@
+#[derive(Copy, Clone, Hash, Eq, PartialEq)]
+pub struct Pos {
+    pub x: i64,
+    pub y: i64
+}
+
+#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
+pub struct Range {
+    pub left: i64,
+    pub right: i64
+}
+
+#[derive(Copy, Clone, Hash, Eq, PartialEq)]
+pub struct Sensor {
+    pub s: Pos,
+    pub b: Pos,
+    pub d: i64
+}
+
+pub fn distance(p: Pos, q: Pos) -> i64 {
+   (p.x-q.x).abs() + (p.y-q.y).abs() 
+}
+
+impl Sensor {
+    pub fn from_line(line: &str) -> Sensor {
+        let mut i = 1 + line.find('=').unwrap();
+        let mut j = line.find(',').unwrap();
+        let sx = line[i..j].parse::<i64>().unwrap();
+
+        i = j+4;
+        j = line.find(':').unwrap();
+        let sy = line[i..j].parse::<i64>().unwrap();
+
+        i = 1 + j + line[j..].find('=').unwrap();
+        j = i + line[i..].find(',').unwrap();
+        let bx = line[i..j].parse::<i64>().unwrap();
+
+        i = j+4;
+        j = line.len()-1;
+        let by = line[i..j].parse::<i64>().unwrap();
+
+        let s = Pos { x: sx, y: sy };
+        let b = Pos { x: bx, y: by };
+        let d = distance(s, b);
+        Sensor { s, b, d }
+    }
+
+    pub fn get_range(&self, y: i64) -> Range {
+        let d = distance(self.s, Pos { x: self.s.x, y });
+        Range {
+            left: self.s.x - self.d + d,
+            right: self.s.x + self.d - d
+        }
+    }
+}
+
+pub fn read_sensors_from_stdin() -> Vec<Sensor> {
+    let mut v = Vec::<Sensor>::new();
+    let mut line = String::new();
+    while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+        v.push(Sensor::from_line(&line));
+        line.clear();
+    }
+    v
+}