summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--input/day12.txt41
-rw-r--r--input/day12_ex.txt5
-rw-r--r--src/day12.rs102
-rw-r--r--src/main.rs2
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!"));
}