use petgraph::Graph;
use petgraph::graph::NodeIndex;

/// Get basin related to a given node.
///
/// # Arguments
///
/// * `graph` - The whole graph.
/// * `node` - The current node position in the graph.
/// * `result` - Where we store the basin currently seen elements.
fn get_basin(graph: &Graph<i32, (), petgraph::Undirected>, node: &NodeIndex, result: &mut Vec<NodeIndex>) {
    if result.contains(node) {
        return;
    }

    // We're sure its below 9 already there...
    result.push(*node);

    for neighbor in graph.neighbors(*node) {
        if graph[neighbor] < 9 {
            get_basin(graph, &neighbor, result);
        }
    }
}

fn aoc_09_part02(graph: &Graph<i32, (), petgraph::Undirected>) -> usize {
    // Just to avoid doing too much algo... The seen isn't really needed as we already got basins...
    let mut seen: Vec<NodeIndex> = Vec::new();
    let mut basins: Vec<Vec<NodeIndex>> = Vec::new();

    graph.node_indices().into_iter().for_each(|idx| {
        // Its a basin we haven't seen yet... So we trace it...
        if graph[idx] < 9 && !seen.contains(&idx) {
            // we find the basin
            let mut basin: Vec<NodeIndex> = Vec::new();
            get_basin(graph, &idx, &mut basin);

            if basin.len() > 0 {
                basins.push(basin.clone());
                for node in basin {
                    if !seen.contains(&node) {
                        seen.push(node);
                    }
                }
            }
        }
    });

    // Biggest first
    basins.sort_unstable_by(|a, b| b.len().cmp(&a.len()));

    // Selecting top 3 only and multiply their length
    basins[..=2].iter().fold(0, |acc, val| if acc == 0 { val.len() } else { acc * val.len() })
}

fn aoc_09_part01(graph: &Graph<i32, (), petgraph::Undirected>) -> i32 {
    let selected_nodes = graph.node_indices().into_iter().filter_map(|idx| {
        let nodes = graph.neighbors(idx);
        let node = graph[idx];
        for sibling in nodes {
            // The current node is not the minimum. We can stop here...
            if graph[sibling] <= node {
                return None;
            }
        }

        // That's a minimum, we keep it...
        Some(idx)
    }).collect::<Vec<_>>();

    // The result is 1 + its height for each point
    selected_nodes.iter().map(|idx| graph.node_weight(*idx).unwrap_or(&0) + 1).sum()
}

macro_rules! create_edge {
    ($graph: ident, $nodes: ident, $node: ident, $i: expr, $j: expr) => {
        if $i >= 0 && $j >= 0 {
            let el = $nodes.get($i as usize).and_then(|row| row.get($j as usize));
            if el.is_some() {
                $graph.add_edge($node, *el.unwrap(), ());
            }
        }
    }
}

/// Convert vec of vec into a graph.
///
/// # Arguments
///
/// * `input` - The input to convert as a graph (petgraph)
fn convert_to_graph(input: &[Vec<i32>]) -> Graph<i32, (), petgraph::Undirected> {
    let mut deps = Graph::<i32, (), petgraph::Undirected>::new_undirected();

    // Creating graph nodes
    let nodes = input.iter().map(|line| {
        line.iter().map(|el| deps.add_node(*el)).collect::<Vec<_>>()
    }).collect::<Vec<Vec<_>>>();

    // Creating graph edges
    for i in 0..nodes.len() as i32 {
        for j in 0..nodes[i as usize].len() as i32 {
            let node = nodes[i as usize][j as usize];
            // Up
            create_edge!(deps, nodes, node, i - 1, j);
            // Left
            create_edge!(deps, nodes, node, i, j - 1);
            // Its not a directed graph so we dont need to create dual sided links...
            // so up/left is enough to model the structure.
            // Down
            // create_edge!(deps, nodes, node, i + 1, j);
            // Right
            // create_edge!(deps, nodes, node, i, j + 1);
        }
    }

    deps
}

fn main() {
    let s = include_str!("../input.txt").lines().map(|line| {
        line.chars().filter_map(|c| c.to_string().parse::<i32>().ok()).collect::<Vec<_>>()
    }).collect::<Vec<Vec<_>>>();

    // We convert this to a graph...
    let graph = convert_to_graph(&s);
    // println!("{:#?}", petgraph::dot::Dot::new(&graph));

    let result = aoc_09_part01(&graph);
    println!("Result part 1: {}", result);

    let result = aoc_09_part02(&graph);
    println!("Result part 2: {}", result);
}