From 8c2d4fdbc6dac9d568b32d853baf698b84aca68f Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Thu, 15 Dec 2022 01:56:48 -0500 Subject: day 15 --- benches/2022.rs | 5 ++ data/2022/15.txt | 32 +++++++++++ src/bin/2022/day15.rs | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2022/main.rs | 2 + src/grid.rs | 13 +++++ 5 files changed, 205 insertions(+) create mode 100644 data/2022/15.txt create mode 100644 src/bin/2022/day15.rs 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, + range_x: usize, + range_y: usize, + offset_x: usize, + offset_y: usize, +} + +impl Map { + fn nearby_sensor(&self, pos: (Row, Col)) -> Option { + self.sensors + .iter() + .copied() + .find(|sensor| sensor.in_radius(pos)) + } +} + +pub fn parse(fh: File) -> Result { + 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 { + 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 { + 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 for Row { type Output = Self; fn add(self, other: usize) -> Self::Output { -- cgit v1.2.3-54-g00ecf