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

#[derive(Clone, Debug)]
struct Node {
    goal:  bool,
    //size:  usize,
    used:  usize,
    avail: usize,
}

fn parse(lines: Vec<&str>) -> Vec<Vec<Node>> {
    let mut nodes = Vec::with_capacity(36);

    let mut y = 0;
    let mut column = Vec::with_capacity(25);
    // Skip the first two lines; see `input.txt' to see why
    for i in 2..lines.len() {
        let words: Vec<&str> = lines[i].split_ascii_whitespace().collect();

        // Read the `df -h' data, ignoring the node name
        let node = Node {
            goal:  false,
            //size:  words[1].trim_end_matches('T').parse().unwrap(),
            used:  words[2].trim_end_matches('T').parse().unwrap(),
            avail: words[3].trim_end_matches('T').parse().unwrap(),
        };
        column.push(node);

        y += 1;
        // The grid size is hardcoded at 25 rows here
        if y > 24 {
            nodes.push(column);

            y = 0;
            column = Vec::with_capacity(25);
        }
    }

    // In part 2, we want the data in the top-right corner
    nodes.last_mut().unwrap()[0].goal = true;

    nodes
}

fn solve_part1(state: &Vec<Vec<Node>>) -> usize {
    let mut pairs = Vec::new();

    for x1 in 0..state.len() {
        for y1 in 0..state[0].len() {
            for x2 in 0..state.len() {
                for y2 in 0..state[0].len() {
                    // Check for a "viable pair" according to puzzle description
                    if (x1 != x2 || y1 != y2) && state[x1][y1].used > 0 {
                        if state[x1][y1].used < state[x2][y2].avail {
                            pairs.push(((x1, y1), (x2, y2)));
                        }
                    }
                }
            }
        }
    }

    pairs.len()
}


fn serialize(state: &Vec<Vec<Node>>) -> String {
    let mut result = String::new();

    // Print grid like the example in part 2's description.
    // Some information is deliberately lost in this step.
    for y in 0..state[0].len() {
        for x in 0..state.len() {
            if state[x][y].goal {
                result.push('G');
            } else if state[x][y].used > 100 {
                result.push('#');
            } else if state[x][y].used == 0 {
                result.push('_');
            } else {
                result.push('.');
            }
        }
        result.push('\n');
    }

    result
}

fn solve_part2(start: &Vec<Vec<Node>>) -> usize {
    // We will do a breadth-first search of the state space, with the catch
    // that `serialize()' maps several states onto the same representation
    let mut visited = HashSet::from([serialize(&start)]);
    let mut queue = VecDeque::from([(start.clone(), 0)]);

    loop {
        let (state, depth) = queue.pop_front().unwrap();

        // End condition: did we move the target data to top-left node?
        if state[0][0].goal {
            return depth;
        }

        // There is one empty node; find its coordinates
        let mut empty = (36, 25);
        for x in 0..state.len() {
            for y in 0..state[0].len() {
                if state[x][y].used == 0 {
                    empty = (x, y);
                }
            }
        }

        // Get coordinates of up to four neighbours of `empty'
        let mut neighbours = Vec::new();
        if empty.0 > 0 {
            neighbours.push((empty.0 - 1, empty.1));
        }
        if empty.0 < state.len() - 1 {
            neighbours.push((empty.0 + 1, empty.1));
        }
        if empty.1 > 0 {
            neighbours.push((empty.0, empty.1 - 1));
        }
        if empty.1 < state[0].len() - 1 {
            neighbours.push((empty.0, empty.1 + 1));
        }

        // Generate new states, one for swapping `empty' with each neighbour
        let mut new_states = Vec::new();
        for neigh in neighbours {
            // Some nodes are large and full; their data won't fit in `empty',
            // so we ignore them. Otherwise, we assume that the data will fit;
            // this assumption is justified by the example given for part 2.
            if state[neigh.0][neigh.1].used > 100 {
                continue;
            }

            let mut ns = state.clone();

            let amount = ns[neigh.0][neigh.1].used;
            ns[neigh.0][neigh.1].used  -= amount;
            ns[neigh.0][neigh.1].avail += amount;

            ns[empty.0][empty.1].used  += amount;
            ns[empty.0][empty.1].avail -= amount;

            if ns[neigh.0][neigh.1].goal {
                ns[empty.0][empty.1].goal = true;
                ns[neigh.0][neigh.1].goal = false;
            }

            new_states.push(ns);
        }

        for ns in new_states {
            // Via `serialize()' many uninteresting states are discarded here
            let ser = serialize(&ns);
            if !visited.contains(&ser) {
                visited.insert(ser);
                queue.push_back((ns, depth + 1));
            }
        }
    }
}

fn main() {
    // Read data from input text file
    let input = fs::read_to_string("input.txt").unwrap();
    let lines = input.lines().collect();
    let nodes = parse(lines);

    // Part 1 gives 864 for me
    println!("Part 1 solution: {}", solve_part1(&nodes));

    // Part 2 gives 244 for me
    println!("Part 2 solution: {}", solve_part2(&nodes));
}

// Disabled because I'm too lazy to rewrite `parse()'
// to make it handle different grid sizes properly
/*#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part2_example1() {
        let lines = vec![
            "root@ebhq-gridcenter# df -h",
            "Filesystem            Size  Used  Avail  Use%",
            "/dev/grid/node-x0-y0   10T    8T     2T   80%",
            "/dev/grid/node-x0-y1   11T    6T     5T   54%",
            "/dev/grid/node-x0-y2   32T   28T     4T   87%",
            "/dev/grid/node-x1-y0    9T    7T     2T   77%",
            "/dev/grid/node-x1-y1    8T    0T     8T    0%",
            "/dev/grid/node-x1-y2   11T    7T     4T   63%",
            "/dev/grid/node-x2-y0   10T    6T     4T   60%",
            "/dev/grid/node-x2-y1    9T    8T     1T   88%",
            "/dev/grid/node-x2-y2    9T    6T     3T   66%",
        ];
        let nodes = parse(lines);
        assert_eq!(solve_part2(&nodes), 7);
    }
}*/