use std::cmp::Reverse;
use std::collections::BinaryHeap;
use fixedbitset::FixedBitSet;
use petgraph::Graph;
use petgraph::graph::NodeIndex;
use petgraph::visit::{Visitable, VisitMap};

/// Get basin related to a given node.
///
/// # Arguments
///
/// * `graph` - The whole graph.
/// * `visited` - A visit lookahead...
/// * `node` - The current node position in the graph.
fn get_basin(graph: &Graph<i32, (), petgraph::Undirected>, visited: &mut FixedBitSet, node: &NodeIndex) -> Vec<NodeIndex> {
    let mut visit_next = BinaryHeap::new();
    let mut result = Vec::new();

    visit_next.push(*node);

    while let Some(walk) = visit_next.pop() {
        if visited.is_visited(&walk) {
            continue;
        }

        // Mark as visited, register if wanted into the result...
        visited.visit(walk);
        if graph[walk] < 9 {
            result.push(walk);
        }

        let neighbors = graph.neighbors(walk);
        for neighbor in neighbors {
            if graph[neighbor] < 9 {
                visit_next.push(neighbor);
            }
        }
    }

    result
}

fn aoc_09_part02(graph: &Graph<i32, (), petgraph::Undirected>) -> usize {
    let mut visited = graph.visit_map();
    let mut basins: Vec<Vec<NodeIndex>> = Vec::new();

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

            if !basin.is_empty() {
                basins.push(basin);
            }
        }
    });

    // Biggest first
    basins.sort_unstable_by_key(|b| Reverse(b.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(|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 false;
            }
        }

        true
    }).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);
}