summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--input/day15.txt33
-rw-r--r--input/day15_ex.txt14
-rw-r--r--src/day14.rs34
-rw-r--r--src/day15.rs126
-rw-r--r--src/main.rs2
5 files changed, 192 insertions, 17 deletions
diff --git a/input/day15.txt b/input/day15.txt
new file mode 100644
index 0000000..68b61fa
--- /dev/null
+++ b/input/day15.txt
@@ -0,0 +1,33 @@
+Sensor at x=2899860, y=3122031: closest beacon is at x=2701269, y=3542780
+Sensor at x=1836719, y=1116779: closest beacon is at x=2037055, y=2000000
+Sensor at x=3995802, y=2706630: closest beacon is at x=3944538, y=3053285
+Sensor at x=2591204, y=2008272: closest beacon is at x=2597837, y=2509170
+Sensor at x=2546593, y=1538222: closest beacon is at x=2037055, y=2000000
+Sensor at x=252214, y=61954: closest beacon is at x=1087565, y=-690123
+Sensor at x=950, y=1106672: closest beacon is at x=-893678, y=1276864
+Sensor at x=1349445, y=1752783: closest beacon is at x=2037055, y=2000000
+Sensor at x=3195828, y=3483667: closest beacon is at x=3334657, y=3531523
+Sensor at x=2057761, y=2154359: closest beacon is at x=2037055, y=2000000
+Sensor at x=2315350, y=3364640: closest beacon is at x=2701269, y=3542780
+Sensor at x=327139, y=2426600: closest beacon is at x=-88420, y=3646947
+Sensor at x=3943522, y=2854345: closest beacon is at x=3944538, y=3053285
+Sensor at x=3358620, y=516881: closest beacon is at x=3260516, y=2246079
+Sensor at x=1788376, y=8679: closest beacon is at x=1087565, y=-690123
+Sensor at x=3344883, y=3537985: closest beacon is at x=3334657, y=3531523
+Sensor at x=2961064, y=2697125: closest beacon is at x=2597837, y=2509170
+Sensor at x=3780090, y=2093546: closest beacon is at x=3260516, y=2246079
+Sensor at x=3291917, y=3398703: closest beacon is at x=3334657, y=3531523
+Sensor at x=3999864, y=2998005: closest beacon is at x=3944538, y=3053285
+Sensor at x=2919272, y=3732950: closest beacon is at x=2701269, y=3542780
+Sensor at x=2057404, y=2947435: closest beacon is at x=2037055, y=2000000
+Sensor at x=1072126, y=645784: closest beacon is at x=1087565, y=-690123
+Sensor at x=3549465, y=2554712: closest beacon is at x=3260516, y=2246079
+Sensor at x=3550313, y=3121694: closest beacon is at x=3944538, y=3053285
+Sensor at x=3405149, y=3483630: closest beacon is at x=3334657, y=3531523
+Sensor at x=2600212, y=3961193: closest beacon is at x=2701269, y=3542780
+Sensor at x=1102632, y=3932527: closest beacon is at x=-88420, y=3646947
+Sensor at x=67001, y=3506079: closest beacon is at x=-88420, y=3646947
+Sensor at x=3994250, y=3975025: closest beacon is at x=3944538, y=3053285
+Sensor at x=3019750, y=2125144: closest beacon is at x=3260516, y=2246079
+Sensor at x=3282319, y=3656404: closest beacon is at x=3334657, y=3531523
+Sensor at x=2797371, y=3645126: closest beacon is at x=2701269, y=3542780 \ No newline at end of file
diff --git a/input/day15_ex.txt b/input/day15_ex.txt
new file mode 100644
index 0000000..652e631
--- /dev/null
+++ b/input/day15_ex.txt
@@ -0,0 +1,14 @@
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3 \ No newline at end of file
diff --git a/src/day14.rs b/src/day14.rs
index 97c06fe..a89ed06 100644
--- a/src/day14.rs
+++ b/src/day14.rs
@@ -1,7 +1,7 @@
const AIR: char = '.';
const ROCK: char = '#';
-const SANDSPAWN: char = '+';
-const MOVING_SAND: char = '*';
+//const SANDSPAWN: char = '+';
+//const MOVING_SAND: char = '*';
const STUCK_SAND: char = 'o';
pub fn run(input: String) {
@@ -108,18 +108,18 @@ fn mov(grid: &Vec<Vec<char>>, sand: &(usize,usize)) -> Option<(usize,usize)> {
}
}
-fn print(grid: &Vec<Vec<char>>, sandspawn: &(usize,usize), sand: &(usize,usize)) {
- for (y, line) in grid.into_iter().enumerate() {
- for (x, ch) in line.into_iter().enumerate().skip(480) {
- let pt = (x,y);
- if sand == &pt {
- print!("{}", MOVING_SAND);
- } else if sandspawn == &pt {
- print!("{}", SANDSPAWN);
- } else {
- print!("{}", ch);
- }
- }
- print!("\n");
- }
-} \ No newline at end of file
+// fn print(grid: &Vec<Vec<char>>, sandspawn: &(usize,usize), sand: &(usize,usize)) {
+// for (y, line) in grid.into_iter().enumerate() {
+// for (x, ch) in line.into_iter().enumerate().skip(480) {
+// let pt = (x,y);
+// if sand == &pt {
+// print!("{}", MOVING_SAND);
+// } else if sandspawn == &pt {
+// print!("{}", SANDSPAWN);
+// } else {
+// print!("{}", ch);
+// }
+// }
+// print!("\n");
+// }
+// } \ No newline at end of file
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
diff --git a/src/main.rs b/src/main.rs
index 38ed88d..9b0ea44 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -16,6 +16,7 @@ mod day11;
mod day12;
mod day13;
mod day14;
+mod day15;
fn main() {
day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!"));
@@ -32,4 +33,5 @@ fn main() {
day12::run(fs::read_to_string("input/day12.txt").expect("Failed to read input file!"));
day13::run(fs::read_to_string("input/day13.txt").expect("Failed to read input file!"));
day14::run(fs::read_to_string("input/day14.txt").expect("Failed to read input file!"));
+ day15::run(fs::read_to_string("input/day15.txt").expect("Failed to read input file!"));
}