From 4093fa4f55257cf9f3ac41a83cd1f57bae53ae07 Mon Sep 17 00:00:00 2001 From: Reiner Herrmann Date: Sat, 17 Dec 2022 18:59:34 +0100 Subject: day15 --- inputs/day15 | 31 +++++++++++++ src/bin/day15.rs | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 161 insertions(+) create mode 100644 inputs/day15 create mode 100644 src/bin/day15.rs 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::().unwrap(), + y: cap[2].parse::().unwrap(), + }; + let closest = Position { + x: cap[3].parse::().unwrap(), + y: cap[4].parse::().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::>(); + + 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::>(); + + 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::>(); + + assert_eq!(positions_without_beacon(&input, 10), 26); + assert_eq!(tuning_frequency(&input, 0, 20), 56000011); + } +} -- cgit v1.2.3