Initial commit

1 files changed, 205 insertions, 0 deletions

diff --git a/d22/src/main.rs b/d22/src/main.rs
new file mode 100644
index 0000000..71b17c0
--- /dev/null
+++ b/d22/src/main.rs
@@ -0,0 +1,205 @@
+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);
+    }
+}*/