summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMartin Ashby <martin@ashbysoft.com>2022-12-12 19:49:01 +0000
committerMartin Ashby <martin@ashbysoft.com>2022-12-12 19:49:01 +0000
commit7931bcffb0297d6f7a5bf8f67d15a59e8ef1517e (patch)
treee1082348dd5fbad33885273748e87ed191e9378a /src
parent09b05973d945c2affc89f07e09fd3a86f8bd7103 (diff)
downloadaoc2022-7931bcffb0297d6f7a5bf8f67d15a59e8ef1517e.tar.gz
aoc2022-7931bcffb0297d6f7a5bf8f67d15a59e8ef1517e.tar.bz2
aoc2022-7931bcffb0297d6f7a5bf8f67d15a59e8ef1517e.tar.xz
aoc2022-7931bcffb0297d6f7a5bf8f67d15a59e8ef1517e.zip
day12
Diffstat (limited to 'src')
-rw-r--r--src/day12.rs102
-rw-r--r--src/main.rs2
2 files changed, 104 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
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!"));
}