diff options
-rw-r--r-- | 2022/inputs/day_15.txt | 38 | ||||
-rw-r--r-- | 2022/src/bin/day_15.rs | 167 |
2 files changed, 205 insertions, 0 deletions
diff --git a/2022/inputs/day_15.txt b/2022/inputs/day_15.txt new file mode 100644 index 0000000..888e520 --- /dev/null +++ b/2022/inputs/day_15.txt @@ -0,0 +1,38 @@ +Sensor at x=2300471, y=2016823: closest beacon is at x=2687171, y=2822745 +Sensor at x=1315114, y=37295: closest beacon is at x=1671413, y=43557 +Sensor at x=1039523, y=3061589: closest beacon is at x=1570410, y=3710085 +Sensor at x=214540, y=3768792: closest beacon is at x=-355567, y=3900317 +Sensor at x=1641345, y=3524291: closest beacon is at x=1570410, y=3710085 +Sensor at x=1016825, y=1450262: closest beacon is at x=745731, y=2000000 +Sensor at x=2768110, y=3703050: closest beacon is at x=3133588, y=3984216 +Sensor at x=2213658, y=3522463: closest beacon is at x=1570410, y=3710085 +Sensor at x=3842967, y=3381135: closest beacon is at x=3839159, y=3421933 +Sensor at x=3952516, y=2683159: closest beacon is at x=3213800, y=2708360 +Sensor at x=172892, y=369117: closest beacon is at x=-228964, y=1438805 +Sensor at x=3999720, y=3498306: closest beacon is at x=3839159, y=3421933 +Sensor at x=1596187, y=307084: closest beacon is at x=1671413, y=43557 +Sensor at x=3863253, y=3406760: closest beacon is at x=3839159, y=3421933 +Sensor at x=3927553, y=3450758: closest beacon is at x=3839159, y=3421933 +Sensor at x=2774120, y=3228484: closest beacon is at x=2687171, y=2822745 +Sensor at x=3897140, y=3418751: closest beacon is at x=3839159, y=3421933 +Sensor at x=1880329, y=2843697: closest beacon is at x=2687171, y=2822745 +Sensor at x=33790, y=3243415: closest beacon is at x=-355567, y=3900317 +Sensor at x=438583, y=2647769: closest beacon is at x=745731, y=2000000 +Sensor at x=1540347, y=3177380: closest beacon is at x=1570410, y=3710085 +Sensor at x=3120086, y=3997791: closest beacon is at x=3133588, y=3984216 +Sensor at x=3428967, y=3105227: closest beacon is at x=3213800, y=2708360 +Sensor at x=2898335, y=1037911: closest beacon is at x=3213800, y=2708360 +Sensor at x=3456260, y=3578627: closest beacon is at x=3839159, y=3421933 +Sensor at x=1859971, y=3999725: closest beacon is at x=1570410, y=3710085 +Sensor at x=3147730, y=3999322: closest beacon is at x=3133588, y=3984216 +Sensor at x=3920847, y=71575: closest beacon is at x=3826138, y=-255533 +Sensor at x=956723, y=3999438: closest beacon is at x=1570410, y=3710085 +Sensor at x=1193760, y=3758205: closest beacon is at x=1570410, y=3710085 +Sensor at x=3999446, y=1929369: closest beacon is at x=3213800, y=2708360 +Sensor at x=1434466, y=2254087: closest beacon is at x=745731, y=2000000 +Sensor at x=200365, y=1856636: closest beacon is at x=745731, y=2000000 +Sensor at x=1859710, y=31159: closest beacon is at x=1671413, y=43557 +Sensor at x=3712613, y=3930105: closest beacon is at x=3133588, y=3984216 +Sensor at x=1660185, y=2900: closest beacon is at x=1671413, y=43557 +Sensor at x=1497065, y=93501: closest beacon is at x=1671413, y=43557 +Sensor at x=3832823, y=3346266: closest beacon is at x=3839159, y=3421933 diff --git a/2022/src/bin/day_15.rs b/2022/src/bin/day_15.rs new file mode 100644 index 0000000..be7645d --- /dev/null +++ b/2022/src/bin/day_15.rs @@ -0,0 +1,167 @@ +use nom::{ + bytes::complete::tag, + character::complete::{i64, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs, ops::Range}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_15.txt")?; + let sensors = Sensors::parser(&input).unwrap().1; + + dbg!(sensors.count_covered_non_beacons_in_row(2000000)); + + dbg!(sensors + .find_hole_in_range( + Point { x: 0, y: 0 }..Point { + x: 4000001, + y: 4000001 + } + ) + .tuning_frequency()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Sensors(Vec<Sensor>); + +#[derive(Debug, Clone)] +struct Sensor { + center: Point, + closest_beacon: Point, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: i64, + y: i64, +} + +impl Sensors { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Sensor::parser), Sensors)(input) + } + + fn ranges_in_row(&self, y: i64) -> Vec<Range<i64>> { + let mut ranges: Vec<Range<i64>> = self + .0 + .iter() + .filter_map(|s| s.get_range_in_row(y)) + .collect(); + + let mut any_changes = true; + while any_changes { + any_changes = false; + ranges.sort_unstable_by_key(|r| r.start); + if ranges.len() > 0 { + for i in 0..ranges.len() - 1 { + if ranges[i].end > ranges[i + 1].start { + ranges[i + 1].start = ranges[i].end; + any_changes = true; + } + } + ranges.retain(|r| !r.is_empty()); + } + } + ranges + } + + fn count_covered_non_beacons_in_row(&self, y: i64) -> u64 { + let ranges = self.ranges_in_row(y); + + // these beacons are all distinct, and are all definitely on + // the line because the beacons are how the line is found! + let beacons: BTreeSet<i64> = self + .0 + .iter() + .filter(|s| s.closest_beacon.y == y) + .map(|s| s.closest_beacon.x) + .collect(); + + ranges.into_iter().map(|r| r.count() as u64).sum::<u64>() - beacons.len() as u64 + } + + fn find_hole_in_range(&self, field_range: Range<Point>) -> Point { + let full_row_len = field_range.end.x - field_range.start.x; + for y in field_range.start.y..field_range.end.y { + let ranges = self.ranges_in_row(y); + let count = ranges + .into_iter() + .map(|mut r| { + if r.start < field_range.start.x { + r.start = field_range.start.x + }; + if r.end > field_range.end.x { + r.end = field_range.end.x + }; + r + }) + .map(|r| r.count() as i64) + .sum::<i64>(); + if full_row_len != count { + for x in field_range.start.x..field_range.end.x { + let p = Point { x, y }; + if !self.0.iter().any(|s| s.contains(&p)) { + return p; + } + } + } + } + panic!("Didn't find the hole as specified!") + } +} + +impl Sensor { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("Sensor at "), + Point::parser, + tag(": closest beacon is at "), + Point::parser, + )), + |(_, center, _, closest_beacon)| Sensor { + center, + closest_beacon, + }, + )(input) + } + + fn get_range_in_row(&self, y: i64) -> Option<Range<i64>> { + let dy = (self.center.y - y).abs(); + let dx = self.radius() - dy; + if dx < 0 { + None + } else { + let min_x = self.center.x - dx; + let max_x = self.center.x + dx; + Some(min_x..(max_x + 1)) + } + } + + fn radius(&self) -> i64 { + (self.center.x - self.closest_beacon.x).abs() + + (self.center.y - self.closest_beacon.y).abs() + } + + fn contains(&self, other: &Point) -> bool { + let d = (self.center.x - other.x).abs() + (self.center.y - other.y).abs(); + d <= self.radius() + } +} + +impl Point { + fn parser(input: &str) -> IResult<&str, Self> { + map(tuple((tag("x="), i64, tag(", y="), i64)), |(_, x, _, y)| { + Point { x, y } + })(input) + } + + fn tuning_frequency(&self) -> i64 { + self.x * 4000000 + self.y + } +} |