path: root/day12a/src/main.rs

/// --- Day 12: Hill Climbing Algorithm ---
///
/// You try contacting the Elves using your handheld device, but the river you're following must be
/// too low to get a decent signal.
///
/// You ask the device for a heightmap of the surrounding area (your puzzle input).  The heightmap
/// shows the local area from above broken into a grid; the elevation of each square of the grid is
/// given by a single lowercase letter, where a is the lowest elevation, b is the next-lowest, and
/// so on up to the highest elevation, z.
///
/// Also included on the heightmap are marks for your current position (S) and the location that
/// should get the best signal (E).  Your current position (S) has elevation a, and the location
/// that should get the best signal (E) has elevation z.
///
/// You'd like to reach E, but to save energy, you should do it in as few steps as possible.
/// During each step, you can move exactly one square up, down, left, or right.  To avoid needing
/// to get out your climbing gear, the elevation of the destination square can be at most one
/// higher than the elevation of your current square; that is, if your current elevation is m, you
/// could step to elevation n, but not to elevation o.  (This also means that the elevation of the
/// destination square can be much lower than the elevation of your current square.)
///
/// For example:
///
/// ```
/// Sabqponm
/// abcryxxl
/// accszExk
/// acctuvwj
/// abdefghi
/// ```
///
/// Here, you start in the top-left corner; your goal is near the middle.  You could start by
/// moving down or right, but eventually you'll need to head toward the e at the bottom.  From
/// there, you can spiral around to the goal:
///
/// ```
/// v..v<<<<
/// >v.vv<<^
/// .>vv>E^^
/// ..v>>>^^
/// ..>>>>>^
/// ```
///
/// In the above diagram, the symbols indicate whether the path exits each square moving up (^),
/// down (v), left (<), or right (>).  The location that should get the best signal is still E, and
/// . marks unvisited squares.
///
/// This path reaches the goal in 31 steps, the fewest possible.
///
/// What is the fewest steps required to move from your current position to the location that
/// should get the best signal?
use clap::Parser;
use itertools::Itertools;
use pathfinding::prelude::bfs;

use std::fs::File;
use std::hash::{Hash, Hasher};
use std::io::prelude::*;
use std::io::BufReader;
use std::path::PathBuf;

const FILEPATH: &'static str = "examples/input.txt";

#[derive(Parser, Debug)]
#[clap(author, version, about, long_about = None)]
struct Cli {
    #[clap(short, long, default_value = FILEPATH)]
    file: PathBuf,
}

#[derive(Clone, Debug)]
struct Arena(Vec<Vec<Node>>);

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

#[derive(Clone, Debug)]
struct Node {
    pos: Pos,
    value: char,
    connected: Vec<Pos>,
}

impl Node {
    fn new(pos: Pos, value: char) -> Self {
        Node {
            pos,
            value,
            connected: Vec::new(),
        }
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.pos == other.pos
    }
}

impl Eq for Node {}

impl Hash for Node {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.pos.hash(state);
    }
}

impl Arena {
    fn get(&self, coords: Pos) -> &Node {
        &self.0[coords.0][coords.1]
    }

    fn get_mut(&mut self, coords: Pos) -> &mut Node {
        &mut self.0[coords.0][coords.1]
    }
}

fn is_connected(x: char, y: char) -> bool {
    let (x, y) = match (x, y) {
        ('S', _) => ('a', y),
        ('E', _) => ('z', y),
        (_, 'S') => (x, 'a'),
        (_, 'E') => (x, 'z'),
        _ => (x, y),
    };

    let (x, y) = (x as i8, y as i8);
    i8::abs(x - y) <= 1 || x > y
}

fn main() {
    let args = Cli::parse();

    let file = File::open(&args.file).unwrap();
    let reader = BufReader::new(file);

    let mut arena = Arena(Vec::new());
    let _ = reader
        .lines()
        .enumerate()
        .map(|(idx, l)| {
            l.unwrap()
                .chars()
                .enumerate()
                .map(|(idy, c)| Node::new(Pos(idx, idy), c))
                .collect_vec()
        })
        .scan(&mut arena, |arena, row| {
            arena.0.push(row);
            Some(())
        })
        .last();

    let xdim = arena.0.len();
    let ydim = arena.0[0].len();

    let mut start_pos = None;
    let mut end_pos = None;

    for idx in 0..xdim {
        for idy in 0..ydim {
            let node_val = arena.get(Pos(idx, idy)).value;

            match node_val {
                'S' => start_pos = Some(Pos(idx, idy)),
                'E' => end_pos = Some(Pos(idx, idy)),
                _ => (),
            }

            if idx != 0 {
                let up_idx = Pos(idx - 1, idy);
                if is_connected(node_val, arena.get(up_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(up_idx);
                }
            }

            if idx != xdim - 1 {
                let down_idx = Pos(idx + 1, idy);
                if is_connected(node_val, arena.get(down_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(down_idx);
                }
            }

            if idy != 0 {
                let left_idx = Pos(idx, idy - 1);
                if is_connected(node_val, arena.get(left_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(left_idx);
                }
            }

            if idy != ydim - 1 {
                let right_idx = Pos(idx, idy + 1);
                if is_connected(node_val, arena.get(right_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(right_idx);
                }
            }
        }
    }

    let start = arena.get(start_pos.unwrap());
    let end = arena.get(end_pos.unwrap());

    let res = bfs(
        &start,
        |n| n.connected.iter().map(|&p| arena.get(p)),
        |&n| n == end,
    )
    .unwrap()
    .len()
        - 1;
    println!("{res}");
}