| use std::{
|
| cmp::max,
|
| sync::{
|
| mpsc::{self, Receiver, SyncSender},
|
| Arc,
|
| },
|
| thread::{self, ScopedJoinHandle},
|
| };
|
|
|
| struct Worker<'s, T> {
|
| reqs_out: SyncSender<usize>,
|
| handle: ScopedJoinHandle<'s, T>,
|
| }
|
|
|
| fn pt2_scan(reqs_in: Receiver<usize>, grid: Arc<Vec<Vec<i8>>>) -> i32 {
|
| let mut local_best = 0;
|
| for x in reqs_in {
|
| // Request to scan a row
|
| for (y, height) in grid[x].iter().enumerate() {
|
| let mut up = 0;
|
| let mut down = 0;
|
| let mut left = 0;
|
| let mut right = 0;
|
| for sx in (0..x).rev() {
|
| // Scan leftwards
|
| left += 1; // Elves can see through trees, as long as they're smaller or equal to their house's size.
|
| if grid[sx][y] >= *height {
|
| break;
|
| }
|
| }
|
| for sx in x + 1..grid.len() {
|
| // Scan rightwards
|
| right += 1;
|
| if grid[sx][y] >= *height {
|
| break;
|
| }
|
| }
|
| for sy in (0..y).rev() {
|
| // Scan upwards
|
| up += 1;
|
| if grid[x][sy] >= *height {
|
| break;
|
| }
|
| }
|
| for sy in y + 1..grid[x].len() {
|
| // Scan downwards
|
| down += 1;
|
| if grid[x][sy] >= *height {
|
| break;
|
| }
|
| }
|
| local_best = max(local_best, up * down * left * right); // Accumulate max
|
| }
|
| }
|
| // No more work, send result and bail.
|
| local_best
|
| }
|
|
|
| pub fn day_8(input: &str) -> anyhow::Result<()> {
|
| let mut grid: Vec<Vec<i8>> = Vec::new(); // Big ol' grid of tree heights
|
| let mut vis: Vec<Vec<bool>> = Vec::new(); // Visibility map, from the edge.
|
| let mut curr_max_y = Vec::new(); // Max height seen from each column
|
| // Scan left-to-right and top-to-bottom. Initial parse also happens here.
|
| for line in input.lines() {
|
| let mut row = Vec::new(); // Heights for this row
|
| let mut visline = Vec::new(); // Visibilty map for this row
|
| let mut curr_max_x = -1; // Highest tree seen left-to-right.
|
| for (y, char) in line.bytes().enumerate() {
|
| while curr_max_y.len() <= y {
|
| // Haven't seen this column yet? init to -1
|
| curr_max_y.push(-1);
|
| }
|
| let height = char.saturating_sub(b'0') as i8; // Char to int.
|
| row.push(height);
|
| if height > curr_max_x || height > curr_max_y[y] {
|
| // Is this visible?
|
| visline.push(true);
|
| if height > curr_max_x {
|
| // Highest left-to-right?
|
| curr_max_x = height;
|
| }
|
| if height > curr_max_y[y] {
|
| // Highest in this column top-to-bottom?
|
| curr_max_y[y] = height;
|
| }
|
| } else {
|
| // Not visible
|
| visline.push(false);
|
| }
|
| }
|
| vis.push(visline);
|
| grid.push(row);
|
| }
|
| // Column map is already perfectly sized, so let's reuse it.
|
| let arcgrid = Arc::new(grid);
|
| let p1grid = arcgrid.clone();
|
| thread::scope(|s| {
|
| s.spawn(|| {
|
| let mut visible_trees = 0; // Count up the number of visible trees. And show 'vis' while we're at it.
|
| curr_max_y.iter_mut().for_each(|i| *i = -1);
|
| // Now sweep from right to left and bottom to top. Same general idea.
|
| for (x, row) in p1grid.iter().enumerate().rev() {
|
| let mut curr_max_x = -1;
|
| for (y, height) in row.iter().enumerate().rev() {
|
| let curr_vis = &mut vis[x][y];
|
| if *height > curr_max_x || *height > curr_max_y[y] {
|
| // Higher than anything? Visible.
|
| *curr_vis = true;
|
| if *height > curr_max_x {
|
| curr_max_x = *height;
|
| }
|
| if *height > curr_max_y[y] {
|
| curr_max_y[y] = *height;
|
| }
|
| }
|
| if *curr_vis {
|
| visible_trees += 1;
|
| }
|
| }
|
| }
|
| println!("pt 1 {}", visible_trees);
|
| });
|
| // And now onto part 2, where we learn elves can see through trees if they're smaller than their house.
|
| let mut best = 0;
|
| let mut threads = Vec::new();
|
| for _ in 0..thread::available_parallelism().unwrap().into() {
|
| // Make pipes and spawn a worker for each core.
|
| let (reqs_out, reqs_in) = mpsc::sync_channel::<usize>(1);
|
| let grid = arcgrid.clone();
|
| let w = Worker {
|
| reqs_out,
|
| handle: s.spawn(|| pt2_scan(reqs_in, grid)),
|
| };
|
| threads.push(w)
|
| }
|
| for (i, _) in arcgrid.iter().enumerate() {
|
| threads[i % threads.len()].reqs_out.send(i).unwrap();
|
| }
|
| for thread in threads {
|
| drop(thread.reqs_out); // Close the work queue, thread will join after this.
|
| // Read the results from each thread, and join them in.
|
| best = max(thread.handle.join().unwrap(), best);
|
| }
|
| println!("pt 2 {}", best);
|
| });
|
| Ok(())
|
| }
|