diff options
Diffstat (limited to 'src/day15.rs')
| -rw-r--r-- | src/day15.rs | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/src/day15.rs b/src/day15.rs new file mode 100644 index 0000000..060bd3e --- /dev/null +++ b/src/day15.rs @@ -0,0 +1,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); +}
\ No newline at end of file |