use std::collections::HashMap;

#[path = "../lib.rs"]
mod lib;

fn parse_input() -> Vec<Vec<u8>> {
    return lib::iter_input().map(|line| {
        return line.bytes().collect();
    }).collect();
}

fn get_neighbors(map: &Vec<Vec<u8>>, x0: usize, y0: usize, sloped: bool) -> Vec<(usize, usize, usize)> {
    let mut result = vec![];
    let mut queue = vec![];
    queue.push((x0, y0, x0, y0, 0));

    while let Some((px, py, x, y, steps)) = queue.pop() {
        if y == 0 {
            if steps == 0 {
                queue.push((x, y, x, 1, 1));
            }
        } else if y == map.len() - 1 {
            result.push((x, y, steps));
        } else {
            let mut neighbors = vec![];
            for (nx, ny, b) in [
                (x + 1, y, b'>'),
                (x - 1, y, b'<'),
                (x, y + 1, b'v'),
                (x, y - 1, b'^'),
            ] {
                if (nx, ny) != (px, py)
                    && (!sloped || map[y][x] == b'.' || map[y][x] == b)
                    && map[ny][nx] != b'#'
                {
                    neighbors.push((nx, ny));
                }
            }
            if (x, y) == (x0, y0) || neighbors.len() == 1 {
                for (nx, ny) in neighbors {
                    queue.push((x, y, nx, ny, steps + 1));
                }
            } else if neighbors.len() > 0 {
                result.push((x, y, steps));
            }
        }
    }
    return result;
}

fn map2vec(map: &HashMap<(usize, usize), Vec<(usize, usize, usize)>>) -> Vec<Vec<(usize, usize)>> {
    let mut result: Vec<Vec<(usize, usize)>> = vec![];
    let mut indices = HashMap::new();

    let mut keys: Vec<&(usize, usize)> = map.keys().collect();
    keys.sort_by_key(|(x, y)| (y, x));

    for (x, y) in keys.iter() {
        indices.insert((x, y), result.len());
        result.push(vec![]);
    }

    for ((x, y), n) in map.iter() {
        let i = indices.get(&(x, y)).unwrap();
        for (nx, ny, steps) in n {
            let j = indices.get(&(nx, ny)).unwrap();
            result[*i].push((*j, *steps));
        }
    }

    return result;
}

fn get_graph(map: &Vec<Vec<u8>>, sloped: bool) -> Vec<Vec<(usize, usize)>> {
    let mut queue = vec![];
    let mut graph = HashMap::new();

    let y0 = 0;
    let x0 = map[y0].iter().position(|b| *b != b'#').unwrap();
    queue.push((x0, y0));

    while let Some((x, y)) = queue.pop() {
        if graph.contains_key(&(x, y)) {
            continue;
        }

        let n = get_neighbors(map, x, y, sloped);
        for (nx, ny, _steps) in n.iter() {
            queue.push((*nx, *ny));
        }
        graph.insert((x, y), n);
    }

    return map2vec(&graph);
}

fn get_longest_path(graph: &Vec<Vec<(usize, usize)>>) -> usize {
    assert!(graph.len() < 64);

    let mut queue = vec![];
    queue.push((0, 1u64, 0));

    let mut result = 0;

    while let Some((i, history, steps)) = queue.pop() {
        if i == graph.len() - 1 {
            result = result.max(steps);
        } else {
            for (j, s) in graph[i].iter() {
                let h = history | (1 << *j);
                if h != history {
                    queue.push((*j, h, steps + *s));
                }
            }
        }
    }

    return result;
}

fn main() {
    let map = parse_input();

    println!("part1: {}", get_longest_path(&get_graph(&map, true)));
    println!("part2: {}", get_longest_path(&get_graph(&map, false)));
}