pastemyst

aoc day 12. funny breadth first search

(at edit #0)

present

main.rs

Rustcopy raw

use std::{io::{stdin, Read}, collections::LinkedList};

fn main() {
    let mut stdin = stdin();
    let mut buf: Vec<u8> = vec![];
    stdin.read_to_end(&mut buf).unwrap();
    let chars: Vec<Vec<u8>> = buf.split(|n| *n == b'\n').map(|f| f.into()).collect();
    let mut st: (usize, usize) = (0,0);
    let mut fi: (usize, usize) = (0,0);
    for i in 0..chars.len() {
        for j in 0..chars[0].len() {
            if chars[i][j] == b'S' {
                st = (i, j);
            } else if chars[i][j] == b'E' {
                fi = (i, j);
            }
        }
    }

let elevations: Vec<Vec<i8>> = chars.iter().map(|row| {
        row.iter().map(|c| {
            (match c {
                b'S' => 0,
                b'E' => 25,
                _ => c - b'a'
            }) as i8
        }).collect()
    }).collect();

let mut visited: Vec<Vec<bool>> = vec![vec![false; elevations[0].len()]; elevations.len()];
    let mut queue: LinkedList<((usize, usize), u32)> = LinkedList::new();
    // visited[st.0][st.1] = true; // part 1
    // queue.push_back((st, 0));
    visited[fi.0][fi.1] = true; // part 2
    queue.push_back((fi, 0));

while !queue.is_empty() {
        let (p, depth) = queue.pop_front().unwrap();
        let c_el = elevations[p.0][p.1];
        // if p == fi { // part 1
        if c_el == 0 { // part 2
            println!("{}", depth); return;
        }
        for i in [(p.0+1 - 1, p.1+1), (p.0+1 + 1, p.1+1), (p.0+1, p.1+1 - 1), (p.0+1, p.1+1 + 1)] {
            if i.0 == 0 || i.1 == 0 { continue; }
            let j = (i.0-1, i.1-1);
            if j.0 >= elevations.len() || j.1 >= elevations[0].len() { continue; }
            // if elevations[j.0][j.1] - c_el <= 1 && !visited[j.0][j.1] { // part 1
            if c_el - elevations[j.0][j.1] <= 1 && !visited[j.0][j.1] { // part 2
                visited[j.0][j.1] = true;
                queue.push_back((j, depth + 1));
            }
        }
    }
}

created at:

stats: 56 lines, 253 words, 1.96kb