Advent of code 2022, day 12.

main.rs

use std::fs;
use pathfinding::prelude::dijkstra;

type Board = Vec<Vec<char>>;
type Height = u32;
type Cost = usize;

#[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(usize, usize);

fn main() {
    let board = read_board();
    let (starts, goal) = find_starts_and_goal(&board);

    let shortest_path_length = starts
        .iter()
        .map(|start| find_path_length(&board, &start, &goal))
        .filter(|result| !result.is_none())
        .map(|option| option.unwrap())
        .min()
        .unwrap();
    println!("{:?}", shortest_path_length);
}

fn read_board() -> Board {
    fs::read_to_string("input.txt").unwrap()
        .lines()
        .map(|line| line.chars().collect::<Vec<char>>())
        .collect::<Board>()
}

fn find_starts_and_goal(board: &Board) -> (Vec<Pos>, Pos) {
    let mut starts = Vec::<Pos>::new();
    let mut goal: Option<Pos> = None;
    for (row_idx, row) in board.iter().enumerate() {
        for (col_idx, char) in row.iter().enumerate() {
            if *char == 'a' || *char == 'S' {
                starts.push(Pos(row_idx, col_idx));
            }
            if *char == 'E' {
                goal = Some(Pos(row_idx, col_idx));
            }
        }
    }
    (starts, goal.unwrap())
}

fn find_path_length(board: &Board, start: &Pos, goal: &Pos) -> Option<usize> {
    dijkstra(
        start,
        |p| successors(&board, p),
        |p| p == goal,
    ).map(|(_, cost)| cost)
}

fn successors(board: &Board, position: &Pos) -> Vec<(Pos, Cost)> {
    neighbours(position, board.len(), board[0].len())
        .into_iter()
        .filter(|neighbour| is_reachable(&board, position, &neighbour))
        .map(|neighbour| (neighbour, 1))
        .collect()
}

fn neighbours(position: &Pos, rows: usize, columns: usize) -> Vec<Pos> {
    let &Pos(row, column) = position;
    let mut result: Vec<Pos> = Vec::new();
    if row > 0 {
        result.push(Pos(row - 1, column))
    }
    if row < rows - 1 {
        result.push(Pos(row + 1, column))
    }
    if column > 0 {
        result.push(Pos(row, column - 1))
    }
    if column < columns - 1 {
        result.push(Pos(row, column + 1))
    }
    result
}

fn is_reachable(board: &Board, source: &Pos, destination: &Pos) -> bool {
    let old_h = height(&board, source);
    let new_h = height(&board, &destination);

    new_h <= old_h + 1
}

fn height(board: &Board, position: &Pos) -> Height {
    let &Pos(row, column) = position;
    let char = board[row][column];

    height_of(char)
}

fn height_of(char: char) -> Height {
    let updated = match char {
        'S' => 'a',
        'E' => 'z',
        _ => char,
    };
    updated as Height
}