main.rs (4366B)
1 use regex::Regex;
2 use std::collections::HashSet;
3
4 #[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]
5 struct Pos(i32, i32);
6
7 #[derive(Debug)]
8 struct Sensor {
9 loc: Pos,
10 beacon: Pos,
11 }
12
13 impl Sensor {
14 fn from_str(s: &str) -> Option<Self> {
15 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]+)$")
16 .unwrap()
17 .captures(s)
18 {
19 Some(Sensor{
20 loc: Pos(cap.name("sensor_x").unwrap().as_str().parse::<i32>().unwrap(), cap.name("sensor_y").unwrap().as_str().parse::<i32>().unwrap()),
21 beacon: Pos(cap.name("beacon_x").unwrap().as_str().parse::<i32>().unwrap(), cap.name("beacon_y").unwrap().as_str().parse::<i32>().unwrap()),
22 })
23 } else {
24 None
25 }
26 }
27
28 fn get_banned_range(&self, y: i32) -> Option<(i32, i32)> {
29 let dist = (self.loc.0 - self.beacon.0).abs() + (self.loc.1 - self.beacon.1).abs();
30 let y_dist = (self.loc.1 - y).abs();
31 let x_dist = dist - y_dist;
32 if x_dist >= 0 {
33 Some((self.loc.0 - x_dist, self.loc.0 + x_dist))
34 } else {
35 None
36 }
37 }
38 }
39
40 fn main() {
41 let input = std::fs::read_to_string("input.txt")
42 .unwrap()
43 .trim()
44 .split('\n')
45 .map(|s| Sensor::from_str(s).unwrap())
46 .collect::<Vec<Sensor>>();
47 // 6078701
48 println!("Part 1: {}", part_1(&input, 2000000));
49 // 12567351400528
50 println!("Part 2: {}", part_2(&input, (0, 4000000)).unwrap());
51 }
52
53 fn union((s1, e1): (i32, i32), (s2, e2): (i32, i32)) -> Option<(i32, i32)> {
54 if (s1 < s2 && e1 < s2) || (s1 > e2 && e1 > e2) {
55 None
56 } else {
57 Some((s1.min(s2), e1.max(e2)))
58 }
59 }
60
61 fn get_banned_ranges(input: &Vec<Sensor>, y: i32) -> Vec<(i32, i32)> {
62 let mut banned_ranges = Vec::new();
63 for sensor in input {
64 if let Some(mut curr) = sensor.get_banned_range(y) {
65 let mut banned_ranges_next = Vec::new();
66 for br in banned_ranges {
67 if let Some(new) = union(br, curr) {
68 curr = new;
69 } else {
70 banned_ranges_next.push(br);
71 }
72 }
73 banned_ranges_next.push(curr);
74 banned_ranges = banned_ranges_next;
75 }
76 }
77 banned_ranges
78 }
79
80 fn part_1(input: &Vec<Sensor>, y: i32) -> i32 {
81 let banned_ranges = get_banned_ranges(input, y);
82 let beacon_xs = input
83 .iter()
84 .filter_map(|b| {
85 if b.beacon.1 == y {
86 Some(b.beacon)
87 } else {
88 None
89 }
90 })
91 .collect::<HashSet<Pos>>()
92 .iter()
93 .map(|b| b.0)
94 .collect::<Vec<i32>>();
95 let beacon_count = {
96 let mut tmp = 0;
97 for x in beacon_xs.iter() {
98 for r in banned_ranges.iter() {
99 if x >= &r.0 && x <= &r.1 {
100 tmp += 1;
101 }
102 }
103 }
104 tmp
105 };
106 banned_ranges.iter().map(|(s, e)| e + 1 - s).sum::<i32>() - beacon_count
107 }
108
109 fn difference(
110 (s1, e1): (i32, i32),
111 (s2, e2): (i32, i32),
112 ) -> (Option<(i32, i32)>, Option<(i32, i32)>) {
113 match ((s2 <= s1 && s1 <= e2), (s2 <= e1 && e1 <= e2)) {
114 (true, true) => (None, None),
115 (true, false) => (Some((e2 + 1, e1)), None),
116 (false, true) => (Some((s1, s2 - 1)), None),
117 (false, false) => (Some((s1, s2 - 1)), Some((e2 + 1, e1))),
118 }
119 }
120
121 fn part_2(input: &Vec<Sensor>, (pos_min, pos_max): (i32, i32)) -> Option<i64> {
122 for y in pos_min..=pos_max {
123 let banned_ranges = get_banned_ranges(input, y);
124 let mut x_valid = vec![(pos_min, pos_max)];
125 for br in banned_ranges {
126 let mut x_valid_next = Vec::new();
127 for xv in x_valid {
128 let (d1, d2) = difference(xv, br);
129 if let Some(r1) = d1 {
130 x_valid_next.push(r1);
131 }
132 if let Some(r2) = d2 {
133 x_valid_next.push(r2);
134 }
135 }
136 x_valid = x_valid_next;
137 }
138 if !x_valid.is_empty() {
139 return Some(x_valid[0].0 as i64 * pos_max as i64 + y as i64);
140 }
141 }
142 None
143 }