diff options
Diffstat (limited to 'src/day12.rs')
| -rw-r--r-- | src/day12.rs | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/src/day12.rs b/src/day12.rs new file mode 100644 index 0000000..62bdce1 --- /dev/null +++ b/src/day12.rs @@ -0,0 +1,102 @@ +fn accessible_adjescent_cells(to: (usize,usize), grid: &Vec<Vec<char>>) -> Vec<(usize,usize)>{ + let height = grid.len(); + let width = grid[0].len(); + let mut adjescent: Vec<(usize,usize)> = vec![]; + if to.0 > 0 { + adjescent.push((to.0-1,to.1)); + } + if to.0 < (height-1) { + adjescent.push((to.0+1, to.1)); + } + if to.1 > 0 { + adjescent.push((to.0,to.1-1)); + } + if to.1 < (width-1) { + adjescent.push((to.0,to.1+1)); + } + adjescent.into_iter().filter(|from| { + let ch_to = grid[to.0][to.1] as u32; + let ch_from = grid[from.0][from.1] as u32; + ch_to <= ch_from + 1 + }).collect() +} + +pub fn run(input: String) { + let mut grid: Vec<Vec<char>> = input.lines().map(|line| {line.chars().collect()}).collect(); + let mut maybe_start: Option<(usize,usize)> = None; + let mut maybe_end: Option<(usize,usize)> = None; + let height = grid.len(); + let width = grid[0].len(); + for i in 0..height { + for j in 0..width { + let ch = grid[i][j]; + if ch == 'S' { + maybe_start = Some((i,j)); + } else if ch == 'E' { + maybe_end = Some((i,j)); + } + } + } + let start = maybe_start.expect("couldn't find start!"); + let end = maybe_end.expect("couldn't find end!"); + // Update the grid with heights for start and end + grid[start.0][start.1] = 'a'; + grid[end.0][end.1] = 'z'; + + // Deliberately doing this from end to start, 'cos that's what part 2 will re-use most of. + let mut scores: Vec<Vec<i32>> = (0..height).map(|_| {[-1].repeat(width)}).collect(); + scores[end.0][end.1] = 0; + // 'foo: while scores[start.0][start.1] == -1 { + 'foo: loop { + let mut blocked = true; + // Iterate out a round + for i in 0..height { + for j in 0..width { + let cell_score = scores[i][j]; + // For every currently visited cell + if cell_score != -1 { + // Check if surrounding cells are accessible + let ac = accessible_adjescent_cells((i,j), &grid); + for c in ac { + // If they weren't reached yet, mark them with the new score + if scores[c.0][c.1] == -1 { + blocked = false; + scores[c.0][c.1] = cell_score + 1; + } + // Short circuit while looking for a specific square + // if (c.0,c.1) == start { + // println!("breaking early, found the start"); + // break 'foo; // No point continuing calculations if we got to the start already! + // } + } + } + } + } + // If we went a whole round without finding any more accessible cells then we've covered the whole map already + if blocked { + // println!("we're done here"); + break 'foo; + } + } + + // Debugging... + // for i in 0..height { + // for j in 0..width { + // print!("{}", grid[i][j]); + // print!("{:04} ", scores[i][j]); + // } + // print!("\n"); + // } + + // let minpath = scores[start.0][start.1]; + // println!("Day 12: {}", minpath); + let mut min_path_to_a:i32 = i32::MAX; + for i in 0..height { + for j in 0..width { + if grid[i][j] == 'a' && scores[i][j] != -1 { // consider only accessible ones, perhaps I shouldn't have used -1 to indicate inaccessible. + min_path_to_a = min_path_to_a.min(scores[i][j]); + } + } + } + println!("Day 12: {}", min_path_to_a); +}
\ No newline at end of file |