diff options
| -rw-r--r-- | input/day12.txt | 41 | ||||
| -rw-r--r-- | input/day12_ex.txt | 5 | ||||
| -rw-r--r-- | src/day12.rs | 102 | ||||
| -rw-r--r-- | src/main.rs | 2 |
4 files changed, 150 insertions, 0 deletions
diff --git a/input/day12.txt b/input/day12.txt new file mode 100644 index 0000000..04998d3 --- /dev/null +++ b/input/day12.txt @@ -0,0 +1,41 @@ +abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa +abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa +abccccccccccaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccacccccccccccccccccccaaaaa +abcccccaaaacaaaaaaccaaaaaaaaaaaaaaaaacccccccccccccccaaaccccaccccccccccccccaaa +abccccaaaaacaaccccccaaaaaacaaacaacaaaaaaacccccccccccaaaacccaacccccccccccccaaa +abaaccaaaaaaccccaaacaaaacacaaacaaccaaaaaacccccccccccaklaccccccccccccccccccaac +abaaccaaaaaaccaaaaaacccccccaaacccaaaaaaaccccccccccckkkllllccccccccccccccccccc +abaaccaaaaaaccaaaaaacccccccaaaaacaaaaaaacccccccccckkkklllllcccccccaaaccaccccc +abacccccaacccccaaaaacccccccaaaaaccaaaaaaacccccccckkkkpppllllccccccaaaaaaccccc +abacccccccccccaaaaacccccccccaaaacccaaaaaaccccccckkkkpppppplllccccddddaaaccccc +abccccccccccccaaaaaccccccccccaaaccaaaccccccccccckkkppppppppllllldddddddaccccc +abccacccccccccccccccccccccccccccccaaccccccccccckkkopppupppplllmmmmdddddaacccc +abccaaacaaaccccccccccccccccccccaaaaaaaaccccccckkkkopuuuuupppllmmmmmmddddacccc +abccaaaaaaaccccccccccccccccccccaaaaaaaacccccjjkkkooouuuuuuppqqqqqmmmmddddcccc +abccaaaaaacccccccccccccccaaccccccaaaacccccjjjjjjoooouuxuuuppqqqqqqmmmmdddcccc +abcaaaaaaaacccccccccccccaaacccccaaaaaccccjjjjoooooouuuxxuuvvvvvqqqqmmmdddcccc +abaaaaaaaaaacccccccaaaaaaacaacccaacaaacccjjjooooouuuuxxxxvvvvvvvqqqmmmdddcccc +abaaaaaaaaaacccaaacaaaaaaaaaacccacccaaccjjjooootttuuuxxxyyvyyvvvqqqmmmeeecccc +abcccaaacaaacccaaaaaaacaaaaaccccccccccccjjjooottttxxxxxxyyyyyyvvqqqmmmeeccccc +abcccaaacccccccaaaaaacaaaaaccccaaccaacccjjjnnntttxxxxxxxyyyyyvvvqqqnneeeccccc +SbccccaacccccccaaaaaaaaacaaacccaaaaaacccjjjnnntttxxxEzzzzyyyyvvqqqnnneeeccccc +abcccccccccccccaaaaaaaaacaaccccaaaaaccccjjjnnnttttxxxxyyyyyvvvrrrnnneeecccccc +abcccaacccccccaaaaaaaaaccccccccaaaaaacccciiinnnttttxxxyyyyywvvrrrnnneeecccccc +abcccaaaaaaccaaaaaaaacccccccccaaaaaaaaccciiiinnnttttxyyywyyywvrrrnnneeecccccc +abcccaaaaaaccaaaaaaaacccccccccaaaaaaaacccciiinnnntttxwywwyyywwwrrnnneeecccccc +abcaaaaaaaccaaaaaaaaaccccccccccccaacccccccciiinnnttwwwwwwwwwwwwrrnnneeecccccc +abcaaaaaaaccaaaaaacccccccccccccccaaccccccaaiiiinnttwwwwwwwwwwwrrrnnnffecccccc +abcccaaaaaaccaaaaaccccccccccccccccccccaaaaaciiinnssswwwssssrwwrrrnnnfffcccccc +abaacaaccaaccaaaccccccccaacccccccccccccaaaaaiiinnssssssssssrrrrrronnfffcccccc +abaccaaccaacccccccccaaacaacccccccccccccaaaaaiiimmmssssssmoosrrrrooonffaaacccc +abaaaccccaaaaaaccccccaaaaaccccccccccccaaaaaccihmmmmsssmmmoooooooooofffaaacccc +abaaaccccaaaaaacccccccaaaaaacccccccccccccaacchhhmmmmmmmmmoooooooooffffaaccccc +abaacccaaaaaaaccccccaaaaaaaaccccaaccccccccccchhhhmmmmmmmgggggooofffffaaaccccc +abaacccaaaaaaaccccccaaaaaaaccccaaaaccccccccccchhhhmmmmhggggggggfffffaaaaccccc +abccccccaaaaaaacccccaacaaaaacccaaaaccccccccccchhhhhhhhggggggggggfffaacaaccccc +abccaacccaaaaaaccccccccaaaaaccaaaaacccccccccccchhhhhhhggaaaaaaccccccccccccccc +abccaaaccaaccccccccccccccaaaaaaaaaccccccccccccccchhhhaaaccaaaacccccccccccccaa +abaaaaaaaccccccccccccccccaaaaaaaaccccccccccccccccccccaaaccccaaccccccccccccaaa +abaaaaaaaccccccccaaaccccacaaaaaacccccccccccccccccccccaaaccccccccccccccccccaaa +abaaaaaacccccccaaaaacaaaaaaaaaaacccccccccccccccccccccaaccccccccccccccccaaaaaa +abaaaaaacccccccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaaaa
\ No newline at end of file diff --git a/input/day12_ex.txt b/input/day12_ex.txt new file mode 100644 index 0000000..433e0d2 --- /dev/null +++ b/input/day12_ex.txt @@ -0,0 +1,5 @@ +Sabqponm +abcryxxl +accszExk +acctuvwj +abdefghi
\ No newline at end of file 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 diff --git a/src/main.rs b/src/main.rs index 0d64697..885a516 100644 --- a/src/main.rs +++ b/src/main.rs @@ -13,6 +13,7 @@ mod day8; mod day9; mod day10; mod day11; +mod day12; fn main() { day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!")); @@ -26,4 +27,5 @@ fn main() { day9::run(fs::read_to_string("input/day9.txt").expect("Failed to read input file!")); day10::run(fs::read_to_string("input/day10.txt").expect("Failed to read input file!")); day11::run(fs::read_to_string("input/day11.txt").expect("Failed to read input file!")); + day12::run(fs::read_to_string("input/day12.txt").expect("Failed to read input file!")); } |