day12.rs

use crate::common::get_input;
use std::collections::{BTreeMap, VecDeque};

type Point = (usize, usize);

fn get_index(character: char) -> usize {
    match character {
        'S' => 0,
        'E' => 25,
        character => "abcdefghijklmnopqrstuvwxyz"
            .chars()
            .position(|c| c == character)
            .unwrap(),
    }
}

fn get_position(input: &str, character: char) -> (usize, usize) {
    let row_index = input.lines().position(|line| line.contains("S")).unwrap();
    let col_index = input
        .lines()
        .collect::<Vec<_>>()
        .get(row_index)
        .unwrap()
        .chars()
        .position(|c| c == character)
        .unwrap();

    (row_index, col_index)
}

pub async fn part1() -> u32 {
    let input = get_input("https://adventofcode.com/2022/day/12/input").await;
    let map = input
        .lines()
        .map(|line| line.chars().map(|c| get_index(c)).collect::<Vec<_>>())
        .collect::<Vec<_>>();

    let mut distances: BTreeMap<Point, u32> = BTreeMap::new();
    let mut bfs = VecDeque::from([(0, get_position(input.as_str(), 'S'))]);

    while bfs.len() > 0 {
        let (distance, point) = bfs.pop_front().unwrap();
        if distances.contains_key(&point) {
            // We've already been here
            continue;
        } else {
            distances.insert(point, distance);
        }

        for point in [
            (point.0 as i32 + 1, point.1 as i32),
            (point.0 as i32 - 1, point.1 as i32),
            (point.0 as i32, point.1 as i32 + 1),
            (point.0 as i32, point.1 as i32 - 1),
        ]
        .iter()
        .filter(|(row, col)| {
            row >= &0 && row < &(map.len() as i32) && col >= &0 && col < &(map[0].len() as i32)
        })
        .map(|&(row, col)| (row as usize, col as usize))
        .filter(|&(row, col)| map[row][col] <= map[point.0][point.1] + 1)
        {
            bfs.push_back((distance + 1, point));
        }
    }

    *distances.get(&get_position(input.as_str(), 'E')).unwrap()
}

pub async fn part2() -> u32 {
    let input = get_input("https://adventofcode.com/2022/day/12/input").await;
    let map = input
        .lines()
        .map(|line| line.chars().map(|c| get_index(c)).collect::<Vec<_>>())
        .collect::<Vec<_>>();

    input
        .lines()
        .enumerate()
        .filter(|(_, line)| line.contains("a"))
        .map(|(i, line)| {
            line.chars()
                .enumerate()
                .filter(|(j, c)| c == &'a')
                .map(|(j, _)| (i, j))
                .collect::<Vec<_>>()
        })
        .flatten()
        .map(|point| {
            let mut distances: BTreeMap<Point, u32> = BTreeMap::new();
            let mut bfs = VecDeque::from([(0, point)]);

            while bfs.len() > 0 {
                let (distance, point) = bfs.pop_front().unwrap();
                if distances.contains_key(&point) {
                    // We've already been here
                    continue;
                } else {
                    distances.insert(point, distance);
                }

                for point in [
                    (point.0 as i32 + 1, point.1 as i32),
                    (point.0 as i32 - 1, point.1 as i32),
                    (point.0 as i32, point.1 as i32 + 1),
                    (point.0 as i32, point.1 as i32 - 1),
                ]
                .iter()
                .filter(|(row, col)| {
                    row >= &0
                        && row < &(map.len() as i32)
                        && col >= &0
                        && col < &(map[0].len() as i32)
                })
                .map(|&(row, col)| (row as usize, col as usize))
                .filter(|&(row, col)| map[row][col] <= map[point.0][point.1] + 1)
                {
                    bfs.push_back((distance + 1, point));
                }
            }

            *distances
                .get(&get_position(input.as_str(), 'E'))
                .unwrap_or(&1000)
        })
        .min()
        .unwrap()
}