Rust

use std::collections::{HashSet, VecDeque};

use itertools::Itertools;

fn neighbours_of(i: usize, j: usize, side: usize) -> impl Iterator<Item = (usize, usize)> {
    [
        (i, j.wrapping_sub(1)),
        (i, j + 1),
        (
            if (i + j) % 2 == 0 {
                i.wrapping_sub(1)
            } else {
                i + 1
            },
            j,
        ),
    ]
    .into_iter()
    .filter(move |&(i, j)| i < side && j >= i && j < (2 * side - i - 1))
}

pub fn solve_part_1(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let mut queue = VecDeque::new();
    queue.push_back((0, 0));
    let mut pairs = 0;
    let mut visited = HashSet::new();
    while let Some((i, j)) = queue.pop_front() {
        if visited.contains(&(i, j)) {
            continue;
        }
        for (ni, nj) in neighbours_of(i, j, side) {
            if visited.contains(&(ni, nj)) {
                continue;
            }
            if data[i][j] == 'T' && data[ni][nj] == 'T' {
                pairs += 1;
            }
            queue.push_back((ni, nj));
        }
        visited.insert((i, j));
    }
    pairs.to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let mut front = (0..data.len())
        .cartesian_product(0..data[0].len())
        .filter(|&(i, j)| data[i][j] == 'S')
        .collect::<HashSet<_>>();
    let mut visited = HashSet::new();
    let mut steps = 0;
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            if data[i][j] == 'E' {
                return steps.to_string();
            }
            visited.insert((i, j));
            for (ni, nj) in neighbours_of(i, j, side) {
                if (data[ni][nj] == 'T' || data[ni][nj] == 'E') && !visited.contains(&(ni, nj)) {
                    next_front.insert((ni, nj));
                }
            }
        }
        steps += 1;
        front = next_front;
    }
    panic!("exit not found");
}

pub fn rotate(data: &[Vec<char>]) -> Vec<Vec<char>> {
    let mut result = vec![vec!['.'; data[0].len()]; data.len()];
    let side = data.len();
    for i in 0..data.len() {
        for j in i..(data[0].len() - i) {
            if (i + j) % 2 == 0 {
                result[i][j] = data[side - (i + j) / 2 - 1][i * 2 + side - (i + j) / 2 - 1];
            } else {
                result[i][j] = data[side - (i + j).div_ceil(2) - 1][side - (j - i).div_ceil(2) + i];
            }
        }
    }
    result
}

pub fn solve_part_3(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let data = [data.clone(), rotate(&data), rotate(&rotate(&data))];
    let mut front = (0..data[0].len())
        .cartesian_product(0..data[0][0].len())
        .filter(|&(i, j)| data[0][i][j] == 'S')
        .map(|(i, j)| (i, j, 0))
        .collect::<HashSet<_>>();
    let mut visited = HashSet::new();
    let mut steps = 0;
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j, rotation) in front.drain() {
            if data[rotation][i][j] == 'E' {
                return steps.to_string();
            }
            visited.insert((i, j, rotation));
            let next_rotation = (rotation + 1) % 3;
            for (ni, nj) in neighbours_of(i, j, side) {
                if (data[next_rotation][ni][nj] == 'T' || data[next_rotation][ni][nj] == 'E')
                    && !visited.contains(&(ni, nj, next_rotation))
                {
                    next_front.insert((ni, nj, next_rotation));
                }
            }
            if (data[next_rotation][i][j] == 'T' || data[next_rotation][i][j] == 'E')
                && !visited.contains(&(i, j, next_rotation))
            {
                next_front.insert((i, j, next_rotation));
            }
        }
        steps += 1;
        front = next_front;
    }
    panic!("exit not found");
}