commit 0b96ba14f37aa50c59979169ae476634356c5438
parent 629c05412117d85c5d91960b0026abf448f150d9
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 2 Jul 2025 14:45:11 +0200
Day 15 2022
Diffstat:
5 files changed, 169 insertions(+), 0 deletions(-)
diff --git a/2022/15/a.rs 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
@@ -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
@@ -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
+}
diff --git a/2022/15/input b/2022/15/input
@@ -0,0 +1,27 @@
+Sensor at x=2208586, y=2744871: closest beacon is at x=2094814, y=3380585
+Sensor at x=3937279, y=2452476: closest beacon is at x=3597034, y=2313095
+Sensor at x=3535638, y=3151860: closest beacon is at x=4098735, y=3373876
+Sensor at x=1867584, y=2125870: closest beacon is at x=2685670, y=2236965
+Sensor at x=2290971, y=1583182: closest beacon is at x=2685670, y=2236965
+Sensor at x=3137806, y=2216828: closest beacon is at x=3233556, y=2000000
+Sensor at x=3393352, y=331000: closest beacon is at x=3233556, y=2000000
+Sensor at x=1444302, y=821689: closest beacon is at x=1683873, y=-199301
+Sensor at x=1084667, y=3412239: closest beacon is at x=2094814, y=3380585
+Sensor at x=439341, y=3916996: closest beacon is at x=-290982, y=4102300
+Sensor at x=295460, y=2114590: closest beacon is at x=362644, y=370187
+Sensor at x=2212046, y=3819484: closest beacon is at x=2094814, y=3380585
+Sensor at x=3413280, y=3862465: closest beacon is at x=4098735, y=3373876
+Sensor at x=3744934, y=1572303: closest beacon is at x=3597034, y=2313095
+Sensor at x=3349047, y=2522469: closest beacon is at x=3597034, y=2313095
+Sensor at x=171415, y=591241: closest beacon is at x=362644, y=370187
+Sensor at x=3237499, y=2150414: closest beacon is at x=3233556, y=2000000
+Sensor at x=559077, y=454593: closest beacon is at x=362644, y=370187
+Sensor at x=3030733, y=2047512: closest beacon is at x=3233556, y=2000000
+Sensor at x=1667358, y=3956837: closest beacon is at x=2094814, y=3380585
+Sensor at x=1850337, y=98963: closest beacon is at x=1683873, y=-199301
+Sensor at x=2699546, y=3157824: closest beacon is at x=2094814, y=3380585
+Sensor at x=1113195, y=98130: closest beacon is at x=1683873, y=-199301
+Sensor at x=59337, y=246804: closest beacon is at x=362644, y=370187
+Sensor at x=566043, y=29068: closest beacon is at x=362644, y=370187
+Sensor at x=2831421, y=2581088: closest beacon is at x=2685670, y=2236965
+Sensor at x=597818, y=749461: closest beacon is at x=362644, y=370187
diff --git a/2022/15/test b/2022/15/test
@@ -0,0 +1,14 @@
+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
