diff options
Diffstat (limited to 'd22/src/main.rs')
| -rw-r--r-- | d22/src/main.rs | 205 |
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); + } +}*/ |