diff options
| -rw-r--r-- | input/day15.txt | 33 | ||||
| -rw-r--r-- | input/day15_ex.txt | 14 | ||||
| -rw-r--r-- | src/day14.rs | 34 | ||||
| -rw-r--r-- | src/day15.rs | 126 | ||||
| -rw-r--r-- | src/main.rs | 2 |
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!")); } |