1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
use regex::Regex;
#[derive(Debug,Clone)]
struct Pos {
x: i32,
y: i32
}
#[derive(Debug)]
struct Sensor {
sensor_pos: Pos,
beacon_dist: u32
}
#[derive(Debug,Clone)]
struct LineSeg {
left: i32,
right: i32, // Exclusive!
}
impl LineSeg {
/**
* Calculates overlap of two line segments, and returns a maybe modified 'other' line segment to replace it
* Other segment start must be > our start (checked, but panics)
*/
fn dedup(&self, other:&Self) -> Option<LineSeg> {
if other.left >= self.left && other.right <= self.right {
None
} else if other.left >= self.left && other.left < self.right {
Some(LineSeg {left: self.right, right: other.right})
} else if other.right > self.left && other.right <= self.right {
panic!("Didn't expect a right overlap!");
} else {
Some(other.clone())
}
}
fn len(&self) -> u32 {
(self.right - self.left).try_into().unwrap()
}
}
pub fn run(input: String) {
let re = Regex::new(r"Sensor at x=([-\d]+), y=([-\d]+): closest beacon is at x=([-\d]+), y=([-\d]+)").unwrap();
//let search_y = 10..11;
let search_y = 2_000_000..2_000_001;
// let search_y = 0..20;
// let search_x = 0..20;
let sens: Vec<Sensor> = input.lines().map(|line| {
let cap = re.captures(line).expect("line didn't match regex!");
let sensor_x: i32 = cap[1].parse().expect("sx wasn't an i32!");
let sensor_y: i32 = cap[2].parse().expect("sy wasn't an i32!");
let beacon_x: i32 = cap[3].parse().expect("bx wasn't an i32!");
let beacon_y: i32 = cap[4].parse().expect("by wasn't an i32!");
let beacon_dist = sensor_x.abs_diff(beacon_x)+sensor_y.abs_diff(beacon_y);
Sensor {
sensor_pos: Pos { x: sensor_x, y: sensor_y },
beacon_dist,
}
}).collect();
// let ans = search_y.into_iter().filter_map(|y| {
let ans = search_y.into_iter().for_each(|y| {
let mut line_segments: Vec<LineSeg> = sens.iter().flat_map(|sen| {
// Map it to a line segment on the target line
let target_y_dist = sen.sensor_pos.y.abs_diff(y);
if target_y_dist >= sen.beacon_dist {
// It's too far from the target line entirely
None
} else {
// Reach along the line is the remaining beacon dist after reachig target y
let reach = sen.beacon_dist - target_y_dist;
let l = sen.sensor_pos.x-(reach as i32);
let r = sen.sensor_pos.x+(reach as i32);
//println!("{:?} yd {} reach {} l {} r {}", sen, yd, reach, l,r);
Some(LineSeg{left: l,right: r})
}
}).collect();
line_segments.sort_by(|ls1,ls2| {ls1.left.cmp(&ls2.left)});
//println!("{:?}", lss);
let deduped_line_segments: Vec<LineSeg> = line_segments.into_iter().fold(Vec::<LineSeg>::new(), |acc, ls| {
if let Some(nls) = acc.iter().fold(Some(ls), |lss, tls| {
if let Some(alss) = lss {
tls.dedup(&alss)
} else {
None
}
}) {
let mut nacc = acc.to_vec();
nacc.push(nls);
nacc
} else {
acc
}
});
let x_cov: u32 = deduped_line_segments.iter().map(|ls| {ls.len()}).sum();
println!("Day 15: {}", x_cov);
// Find two line segments with a gap of 1, within the search bounds
// deduped_line_segments[..].windows(2)
// .filter_map(|lss| {
// let ls1 = &lss[0];
// let ls2 = &lss[1];
// if ls1.right+1 < search_x.start {
// None
// } else if ls1.right > search_x.end {
// None
// } else if ls1.right+1 == ls2.left {
// println!("{:?}", deduped_line_segments);
// Some((ls1.right+1,y))
// } else {
// None
// }
// }).next()
}); //.next().expect("Couldn't find the answer!");
// let pos = loc.next().unwrap();
// println!("pos {:?}", pos);
//println!("{:?}", ddls);
// let ans: u32 = ddls.iter().map(|ls| {ls.len()}).sum();
// Now collapse the line segments down. Compare each with every other
// If one is fully contained, remove it.
// If one overlaps another, truncate it
println!("Day 15: {:?}", ans);
}
|
