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
|
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 {
// fn len(&self) -> u32 {
// (self.right - self.left).try_into().unwrap()
// }
fn contains(&self, x: i32) -> bool {
self.left <= x && x < self.right
}
}
pub fn run(input: String) {
// Am i trying to be too clever, or not clever enough?
// Where's my search space? I don't need to search _every_ integer 0-4_000_000 right? I can just search the
// edges of each beacon's outline surely.
// But that's already what I'm doing --
let re = Regex::new(r"Sensor at x=([-\d]+), y=([-\d]+): closest beacon is at x=([-\d]+), y=([-\d]+)").unwrap();
let search_y = 2_890_000..4_000_000; // Cheat, narrow the search space...
let search_x = 0..4_000_000;
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 (x, y) = search_y.into_iter().filter_map(|y| {
// if y % 10_000 == 0 {
// println!("checking y {}", 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)}); // not sure if this is necessary?
// Iterate to find the gap, skipping forward rather than basically iterating
let mut ix:i32 = 0;
'lp: while ix < search_x.end {
for l in &line_segments {
if l.contains(ix) {
ix = l.right;
continue 'lp
}
}
// No line segment contained this point, so it's our answer!
return Some((ix+1, y));
}
None
}).next().expect("no point found!");
println!("Day 15: {}", (x as i64)*4_000_000 + (y as i64));
}
|
