mdcontainer.rs

use std::ops::{Deref, DerefMut, Index, IndexMut};

/// A container that can be indexed by `D`-dimensional indices.
///
/// Generic arguments:
/// - `T`: element type
/// - `C`: type of the underlying container
/// - `D`: number of dimensions
///
/// `C` must impl `Deref<Target = [T]>`, and `DerefMut` for mutable operations.
pub struct MdContainer<T, C, const D: usize>
where
    C: Deref<Target = [T]>,
{
    inner: C,
    dimensions: [usize; D],
}

/// A `D`-dimensional index
pub type MdIndex<const D: usize> = [usize; D];

/// A `D`-dimensional slice
pub type MdSpan<'a, T, const D: usize> = MdContainer<T, &'a [T], D>;
/// A `D`-dimensional mutable slice
pub type MdSpanMut<'a, T, const D: usize> = MdContainer<T, &'a mut [T], D>;
/// A `D`-dimensional `Vec`
pub type MdVec<T, const D: usize> = MdContainer<T, Vec<T>, D>;

impl<T, C: Deref<Target = [T]>, const D: usize> MdContainer<T, C, D> {
    /// Creates an `MdContainer` from its underlying container and extents
    pub fn new(inner: C, dimensions: MdIndex<D>) -> Self {
        assert!(inner.len() == dimensions.into_iter().product());

        Self { inner, dimensions }
    }

    /// Returns the dimensions (also referred to as extents) of this multi-dimensional container
    pub fn dimensions(&self) -> MdIndex<D> {
        self.dimensions
    }

    /// Returns the number of elements in this container
    pub fn len(&self) -> usize {
        // self.dimensions.into_iter().product()
        self.inner.len()
    }

    /// Returns `true` if `index` is within bounds
    pub fn in_bounds(&self, index: MdIndex<D>) -> bool {
        for i in 0..D {
            let d = self.dimensions[i];
            let j = index[i];

            if !(0..d).contains(&j) {
                return false;
            }
        }

        true
    }

    /// Converts `index` to a one-dimensional `usize`
    pub fn to_real_index(&self, index: MdIndex<D>) -> usize {
        if D == 0 {
            return 0;
        }

        let mut result = index[0];
        for i in 1..D {
            result *= self.dimensions[i];
            result += index[i];
        }
        result
    }

    /// Returns a reference to the element with one-dimensional index `index`, without performing bounds checking
    pub unsafe fn get_unchecked_by_usize(&self, index: usize) -> &T {
        self.inner.get_unchecked(index)
    }

    /// Returns a reference to the element at index `index`, without performing bounds checking
    pub unsafe fn get_unchecked(&self, index: MdIndex<D>) -> &T {
        let real_index = self.to_real_index(index);

        self.inner.get_unchecked(real_index)
    }

    /// Returns a reference to the element at index `index`
    pub fn get(&self, index: MdIndex<D>) -> Option<&T> {
        self.in_bounds(index)
            .then(|| unsafe { self.get_unchecked(index) })
    }
}

impl<T, C: DerefMut<Target = [T]>, const D: usize> MdContainer<T, C, D> {
    /// Returns a mutable reference to the element with one-dimensional index `index`, without performing bounds checking
    pub unsafe fn get_unchecked_by_usize_mut(&mut self, index: usize) -> &mut T {
        self.inner.get_unchecked_mut(index)
    }

    /// Returns a mutable reference to the element at index `index`, without performing bounds checking
    pub unsafe fn get_unchecked_mut(&mut self, index: MdIndex<D>) -> &mut T {
        let real_index = self.to_real_index(index);

        self.inner.get_unchecked_mut(real_index)
    }

    /// Returns a mutable reference to the element at index `index`
    pub fn get_mut(&mut self, index: MdIndex<D>) -> Option<&mut T> {
        self.in_bounds(index)
            .then(|| unsafe { self.get_unchecked_mut(index) })
    }
}

impl<T, C: Deref<Target = [T]>, const D: usize> Index<MdIndex<D>> for MdContainer<T, C, D> {
    type Output = T;

    fn index(&self, index: MdIndex<D>) -> &Self::Output {
        self.get(index).expect("out of bounds access")
    }
}

impl<T, C: DerefMut<Target = [T]>, const D: usize> IndexMut<MdIndex<D>> for MdContainer<T, C, D> {
    fn index_mut(&mut self, index: MdIndex<D>) -> &mut Self::Output {
        self.get_mut(index).expect("out of bounds access")
    }
}

impl<T, const D: usize> MdVec<T, D> {
    /// Creates an `MdVec<T, D>`. Works like `vec![T; D]` would if `D` could be an array.
    pub fn new_vec(value: T, dimensions: MdIndex<D>) -> Self
    where
        T: Clone,
    {
        Self::new(vec![value; dimensions.into_iter().product()], dimensions)
    }
}

zzzz-example.rs

use std::{collections::VecDeque, io::Read};

pub mod mdspan;

use mdspan::{MdIndex, MdVec};

fn main() {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    let mut words = input.split_ascii_whitespace();

    macro_rules! read {
        (raw) => {
            words.next().unwrap()
        };
        ($ty:ty) => {
            words.next().unwrap().parse::<$ty>().unwrap()
        };
        () => {
            read!(_)
        };
    }

    type Coord = MdIndex<3>;

    let w: usize = read!();
    let h: usize = read!();
    let d: usize = read!();
    let start: Coord = [read!(), read!(), read!()];
    let goal: Coord = [read!(), read!(), read!()];

    let mut grid = MdVec::new_vec(false, [w, h, d]);

    for z in 0..d {
        for y in 0..h {
            let line = read!(raw).as_bytes();
            for x in 0..w {
                if line[x] == b'#' {
                    grid[[x, y, z]] = true;
                }
            }
        }
    }

    let mut visited = MdVec::new_vec(false, [w, h, d]);

    visited[start] = true;
    let mut queue = VecDeque::new();
    queue.push_back((start, 0));

    let mut dist = None;
    while let Some((p @ [x, y, z], d)) = queue.pop_front() {
        if p == goal {
            dist = Some(d);
        }

        for (xd, yd, zd) in [
            (-1, 0, 0),
            (1, 0, 0),
            (0, -1, 0),
            (0, 1, 0),
            (0, 0, -1),
            (0, 0, 1),
        ] {
            let x = (x as isize + xd) as usize;
            let y = (y as isize + yd) as usize;
            let z = (z as isize + zd) as usize;

            let p = [x, y, z];

            if grid[p] && !visited[p] {
                visited[p] = true;
                queue.push_back((p, d + 1));
            }
        }
    }

    if let Some(dist) = dist {
        println!("{}", dist);
    } else {
        println!("Tunnelen kan ikke bygges!");
    }
}