day12.rs (3757B)
1 fn accessible_adjescent_cells(to: (usize,usize), grid: &Vec<Vec<char>>) -> Vec<(usize,usize)>{ 2 let height = grid.len(); 3 let width = grid[0].len(); 4 let mut adjescent: Vec<(usize,usize)> = vec![]; 5 if to.0 > 0 { 6 adjescent.push((to.0-1,to.1)); 7 } 8 if to.0 < (height-1) { 9 adjescent.push((to.0+1, to.1)); 10 } 11 if to.1 > 0 { 12 adjescent.push((to.0,to.1-1)); 13 } 14 if to.1 < (width-1) { 15 adjescent.push((to.0,to.1+1)); 16 } 17 adjescent.into_iter().filter(|from| { 18 let ch_to = grid[to.0][to.1] as u32; 19 let ch_from = grid[from.0][from.1] as u32; 20 ch_to <= ch_from + 1 21 }).collect() 22 } 23 24 pub fn run(input: String) { 25 let mut grid: Vec<Vec<char>> = input.lines().map(|line| {line.chars().collect()}).collect(); 26 let mut maybe_start: Option<(usize,usize)> = None; 27 let mut maybe_end: Option<(usize,usize)> = None; 28 let height = grid.len(); 29 let width = grid[0].len(); 30 for i in 0..height { 31 for j in 0..width { 32 let ch = grid[i][j]; 33 if ch == 'S' { 34 maybe_start = Some((i,j)); 35 } else if ch == 'E' { 36 maybe_end = Some((i,j)); 37 } 38 } 39 } 40 let start = maybe_start.expect("couldn't find start!"); 41 let end = maybe_end.expect("couldn't find end!"); 42 // Update the grid with heights for start and end 43 grid[start.0][start.1] = 'a'; 44 grid[end.0][end.1] = 'z'; 45 46 // Deliberately doing this from end to start, 'cos that's what part 2 will re-use most of. 47 let mut scores: Vec<Vec<i32>> = (0..height).map(|_| {[-1].repeat(width)}).collect(); 48 scores[end.0][end.1] = 0; 49 // 'foo: while scores[start.0][start.1] == -1 { 50 'foo: loop { 51 let mut blocked = true; 52 // Iterate out a round 53 for i in 0..height { 54 for j in 0..width { 55 let cell_score = scores[i][j]; 56 // For every currently visited cell 57 if cell_score != -1 { 58 // Check if surrounding cells are accessible 59 let ac = accessible_adjescent_cells((i,j), &grid); 60 for c in ac { 61 // If they weren't reached yet, mark them with the new score 62 if scores[c.0][c.1] == -1 { 63 blocked = false; 64 scores[c.0][c.1] = cell_score + 1; 65 } 66 // Short circuit while looking for a specific square 67 // if (c.0,c.1) == start { 68 // println!("breaking early, found the start"); 69 // break 'foo; // No point continuing calculations if we got to the start already! 70 // } 71 } 72 } 73 } 74 } 75 // If we went a whole round without finding any more accessible cells then we've covered the whole map already 76 if blocked { 77 // println!("we're done here"); 78 break 'foo; 79 } 80 } 81 82 // Debugging... 83 // for i in 0..height { 84 // for j in 0..width { 85 // print!("{}", grid[i][j]); 86 // print!("{:04} ", scores[i][j]); 87 // } 88 // print!("\n"); 89 // } 90 91 // let minpath = scores[start.0][start.1]; 92 // println!("Day 12: {}", minpath); 93 let mut min_path_to_a:i32 = i32::MAX; 94 for i in 0..height { 95 for j in 0..width { 96 if grid[i][j] == 'a' && scores[i][j] != -1 { // consider only accessible ones, perhaps I shouldn't have used -1 to indicate inaccessible. 97 min_path_to_a = min_path_to_a.min(scores[i][j]); 98 } 99 } 100 } 101 println!("Day 12: {}", min_path_to_a); 102 }