commit 5244c3d41077b81a909346e430b580d921bea748
parent 8504ad38a94e6f2014f84db4bf2518a8a45ba825
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Thu, 15 Dec 2022 21:43:51 -0500
Add 2022 day 15
Diffstat:
3 files changed, 180 insertions(+), 0 deletions(-)
diff --git a/2022/day15/Cargo.toml b/2022/day15/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day15"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+regex = "1"+
\ No newline at end of file
diff --git a/2022/day15/input.txt b/2022/day15/input.txt
@@ -0,0 +1,27 @@
+Sensor at x=2983166, y=2813277: closest beacon is at x=3152133, y=2932891
+Sensor at x=2507490, y=122751: closest beacon is at x=1515109, y=970092
+Sensor at x=3273116, y=2510538: closest beacon is at x=3152133, y=2932891
+Sensor at x=1429671, y=995389: closest beacon is at x=1515109, y=970092
+Sensor at x=2465994, y=2260162: closest beacon is at x=2734551, y=2960647
+Sensor at x=2926899, y=3191882: closest beacon is at x=2734551, y=2960647
+Sensor at x=1022491, y=1021177: closest beacon is at x=1515109, y=970092
+Sensor at x=1353273, y=1130973: closest beacon is at x=1515109, y=970092
+Sensor at x=1565476, y=2081049: closest beacon is at x=1597979, y=2000000
+Sensor at x=1841125, y=1893566: closest beacon is at x=1597979, y=2000000
+Sensor at x=99988, y=71317: closest beacon is at x=86583, y=-1649857
+Sensor at x=3080600, y=3984582: closest beacon is at x=3175561, y=4138060
+Sensor at x=3942770, y=3002123: closest beacon is at x=3724687, y=3294321
+Sensor at x=1572920, y=2031447: closest beacon is at x=1597979, y=2000000
+Sensor at x=218329, y=1882777: closest beacon is at x=1597979, y=2000000
+Sensor at x=1401723, y=1460526: closest beacon is at x=1515109, y=970092
+Sensor at x=2114094, y=985978: closest beacon is at x=1515109, y=970092
+Sensor at x=3358586, y=3171857: closest beacon is at x=3152133, y=2932891
+Sensor at x=1226284, y=3662922: closest beacon is at x=2514367, y=3218259
+Sensor at x=3486366, y=3717867: closest beacon is at x=3724687, y=3294321
+Sensor at x=1271873, y=831354: closest beacon is at x=1515109, y=970092
+Sensor at x=3568311, y=1566400: closest beacon is at x=3152133, y=2932891
+Sensor at x=3831960, y=3146611: closest beacon is at x=3724687, y=3294321
+Sensor at x=2505534, y=3196726: closest beacon is at x=2514367, y=3218259
+Sensor at x=2736967, y=3632098: closest beacon is at x=2514367, y=3218259
+Sensor at x=3963402, y=3944423: closest beacon is at x=3724687, y=3294321
+Sensor at x=1483115, y=2119639: closest beacon is at x=1597979, y=2000000
diff --git a/2022/day15/src/main.rs b/2022/day15/src/main.rs
@@ -0,0 +1,143 @@
+use regex::Regex;
+use std::collections::HashSet;
+
+#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]
+struct Pos(i32, i32);
+
+#[derive(Debug)]
+struct Sensor {
+ loc: Pos,
+ beacon: Pos,
+}
+
+impl Sensor {
+ fn from_str(s: &str) -> Option<Self> {
+ if let Some(cap) = Regex::new(r"^Sensor at x=(?P<sensor_x>[-0-9]+), y=(?P<sensor_y>[-0-9]+): closest beacon is at x=(?P<beacon_x>[-0-9]+), y=(?P<beacon_y>[-0-9]+)$")
+ .unwrap()
+ .captures(s)
+ {
+ Some(Sensor{
+ loc: Pos(cap.name("sensor_x").unwrap().as_str().parse::<i32>().unwrap(), cap.name("sensor_y").unwrap().as_str().parse::<i32>().unwrap()),
+ beacon: Pos(cap.name("beacon_x").unwrap().as_str().parse::<i32>().unwrap(), cap.name("beacon_y").unwrap().as_str().parse::<i32>().unwrap()),
+ })
+ } else {
+ None
+ }
+ }
+
+ fn get_banned_range(&self, y: i32) -> Option<(i32, i32)> {
+ let dist = (self.loc.0 - self.beacon.0).abs() + (self.loc.1 - self.beacon.1).abs();
+ let y_dist = (self.loc.1 - y).abs();
+ let x_dist = dist - y_dist;
+ if x_dist >= 0 {
+ Some((self.loc.0 - x_dist, self.loc.0 + x_dist))
+ } else {
+ None
+ }
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| Sensor::from_str(s).unwrap())
+ .collect::<Vec<Sensor>>();
+ // 6078701
+ println!("Part 1: {}", part_1(&input, 2000000));
+ // 12567351400528
+ println!("Part 2: {}", part_2(&input, (0, 4000000)).unwrap());
+}
+
+fn union((s1, e1): (i32, i32), (s2, e2): (i32, i32)) -> Option<(i32, i32)> {
+ if (s1 < s2 && e1 < s2) || (s1 > e2 && e1 > e2) {
+ None
+ } else {
+ Some((s1.min(s2), e1.max(e2)))
+ }
+}
+
+fn get_banned_ranges(input: &Vec<Sensor>, y: i32) -> Vec<(i32, i32)> {
+ let mut banned_ranges = Vec::new();
+ for sensor in input {
+ if let Some(mut curr) = sensor.get_banned_range(y) {
+ let mut banned_ranges_next = Vec::new();
+ for br in banned_ranges {
+ if let Some(new) = union(br, curr) {
+ curr = new;
+ } else {
+ banned_ranges_next.push(br);
+ }
+ }
+ banned_ranges_next.push(curr);
+ banned_ranges = banned_ranges_next;
+ }
+ }
+ banned_ranges
+}
+
+fn part_1(input: &Vec<Sensor>, y: i32) -> i32 {
+ let banned_ranges = get_banned_ranges(input, y);
+ let beacon_xs = input
+ .iter()
+ .filter_map(|b| {
+ if b.beacon.1 == y {
+ Some(b.beacon)
+ } else {
+ None
+ }
+ })
+ .collect::<HashSet<Pos>>()
+ .iter()
+ .map(|b| b.0)
+ .collect::<Vec<i32>>();
+ let beacon_count = {
+ let mut tmp = 0;
+ for x in beacon_xs.iter() {
+ for r in banned_ranges.iter() {
+ if x >= &r.0 && x <= &r.1 {
+ tmp += 1;
+ }
+ }
+ }
+ tmp
+ };
+ banned_ranges.iter().map(|(s, e)| e + 1 - s).sum::<i32>() - beacon_count
+}
+
+fn difference(
+ (s1, e1): (i32, i32),
+ (s2, e2): (i32, i32),
+) -> (Option<(i32, i32)>, Option<(i32, i32)>) {
+ match ((s2 <= s1 && s1 <= e2), (s2 <= e1 && e1 <= e2)) {
+ (true, true) => (None, None),
+ (true, false) => (Some((e2 + 1, e1)), None),
+ (false, true) => (Some((s1, s2 - 1)), None),
+ (false, false) => (Some((s1, s2 - 1)), Some((e2 + 1, e1))),
+ }
+}
+
+fn part_2(input: &Vec<Sensor>, (pos_min, pos_max): (i32, i32)) -> Option<i64> {
+ for y in pos_min..=pos_max {
+ let banned_ranges = get_banned_ranges(input, y);
+ let mut x_valid = vec![(pos_min, pos_max)];
+ for br in banned_ranges {
+ let mut x_valid_next = Vec::new();
+ for xv in x_valid {
+ let (d1, d2) = difference(xv, br);
+ if let Some(r1) = d1 {
+ x_valid_next.push(r1);
+ }
+ if let Some(r2) = d2 {
+ x_valid_next.push(r2);
+ }
+ }
+ x_valid = x_valid_next;
+ }
+ if !x_valid.is_empty() {
+ return Some(x_valid[0].0 as i64 * pos_max as i64 + y as i64);
+ }
+ }
+ None
+}