day12

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!"));
 }