Advent of Code 2022, my solution for day 12

aoc_2022_day_12.rs

// See: https://adventofcode.com/2022/day/12

use std::collections::VecDeque;

#[derive(Debug, Copy, Clone)]
struct Point {
    character: char,
    elevation: usize,
    distance: Option<usize>,
}

type Map = Vec<Vec<Point>>;

fn get_coordinates(map: &Map, c: char) -> Vec<(usize, usize)> {
    let rows = map.len();
    let columns = map[0].len();
    let mut coordinates: Vec<(usize, usize)> = vec![];
    for y in 0..rows {
        for x in 0..columns {
            if map[y][x].character == c {
                coordinates.push((y, x));
            }
        }
    }
    coordinates
}

fn flood_fill(map: &mut Map, coordinates: (usize, usize)) {
    let rows = map.len();
    let columns = map[0].len();
    let mut queue: VecDeque<(usize, usize, usize)> = VecDeque::new();
    queue.push_back((coordinates.0, coordinates.1, 0));

    while !queue.is_empty() {
        if let Some((y, x, distance)) = queue.pop_front() {
            if map[y][x].distance.is_none() {
                map[y][x].distance = Some(distance);
                for offset in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
                    let new_y: isize = y as isize + offset.1;
                    let new_x: isize = x as isize + offset.0;
                    // check if (new_x, new_y) is point on map and point has no distance yet
                    if new_y >= 0
                        && new_y < rows as isize
                        && new_x >= 0
                        && new_x < columns as isize
                        && map[new_y as usize][new_x as usize].distance.is_none()
                        && map[new_y as usize][new_x as usize].elevation <= map[y][x].elevation + 1 {
                        queue.push_back((new_y as usize, new_x as usize, distance + 1));
                    }
                }
            }
        }
    }
}

fn parse(input: &str) -> Map {
    input
        .lines()
        .map(|line| {
            line
                .chars()
                .map(|c| {
                    Point {
                        character: c,
                        elevation: match c {
                            'E' => 'z' as usize - 'a' as usize,
                            'S' => 0,
                            _ => c as usize - 'a' as usize,
                        },
                        distance: None,
                    }
                })
                .collect()
        })
        .collect()
}

fn part_one(input: &str) -> Option<usize> {
    let mut map = parse(input);
    let start_coordinates = get_coordinates(&map, 'S')[0];
    flood_fill(&mut map, start_coordinates);
    let finish_coordinates = get_coordinates(&map, 'E')[0];
    map[finish_coordinates.0][finish_coordinates.1].distance
}

fn part_two(input: &str) -> Option<usize> {
    let map = parse(input);
    let start_coordinates = get_coordinates(&map, 'a');
    let finish_coordinates = get_coordinates(&map, 'E')[0];
    start_coordinates
        .iter()
        .filter_map(|&coordinates| {
            let mut map = parse(input);
            flood_fill(&mut map, coordinates);
            map[finish_coordinates.0][finish_coordinates.1].distance
        })
        .min()
}

fn main() {
    let input = include_str!("../inputs/12.txt");
    println!("Part 1 = {:?}", part_one(input));
    println!("Part 2 = {:?}", part_two(input));
}