year2016/
day22.rs

1use utils::geometry::Vec2;
2use utils::prelude::*;
3
4/// Solving a sliding puzzle.
5///
6/// The solution assumes the input has one empty node, similar to the
7/// [15 puzzle](https://en.wikipedia.org/wiki/15_puzzle), as well as one immovable wall on the right
8/// (or immovable nodes below the empty node, like the example input).
9#[derive(Clone, Debug)]
10pub struct Day22 {
11    max_x: u32,
12    max_y: u32,
13    wall_x: u32,
14    empty: Vec2<u32>,
15}
16
17#[derive(Copy, Clone, Debug)]
18struct Node {
19    x: u32,
20    y: u32,
21    used: u32,
22    avail: u32,
23}
24
25impl Day22 {
26    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
27        let Some((_, input)) = input.split_once("Use%") else {
28            return Err(InputError::new(input, 0, "expected df header"));
29        };
30
31        let nodes = parser::u32()
32            .with_prefix("/dev/grid/node-x")
33            .then(parser::u32().with_prefix("-y"))
34            .then(
35                parser::u32()
36                    .with_prefix(parser::take_while1(u8::is_ascii_whitespace))
37                    .with_suffix(b'T')
38                    .repeat_n(parser::noop()),
39            )
40            .map_res(|(x, y, [size, used, avail])| {
41                if size == used + avail {
42                    Ok(Node { x, y, used, avail })
43                } else {
44                    Err("expected Used + Avail to equal Size")
45                }
46            })
47            .with_suffix(parser::take_while1(u8::is_ascii_whitespace))
48            .with_suffix(parser::number_range(0..=100))
49            .with_suffix("%")
50            .parse_lines(input.trim_ascii_start())?;
51
52        let max_x = nodes.iter().map(|n| n.x).max().unwrap();
53        let max_y = nodes.iter().map(|n| n.y).max().unwrap();
54        if ((max_x + 1) * (max_y + 1)) as usize != nodes.len() {
55            return Err(InputError::new(input, 0, "expected rectangular grid"));
56        }
57
58        // Check input has a single empty node
59        let (empty, mut non_empty): (Vec<_>, Vec<_>) = nodes.into_iter().partition(|n| n.used == 0);
60        let [empty] = empty[..] else {
61            return Err(InputError::new(input, 0, "expected one empty node"));
62        };
63
64        // Check no viable pairs can be formed between two non-empty nodes
65        let min_used = non_empty.iter().map(|n| n.used).min().unwrap_or(0);
66        let max_available = non_empty.iter().map(|n| n.avail).max().unwrap_or(0);
67        if min_used < max_available {
68            return Err(InputError::new(
69                input,
70                0,
71                "expected the maximum available space on non-empty nodes to be less than \
72                    the minimum used space on the non-empty nodes",
73            ));
74        }
75
76        // Check immovable nodes
77        non_empty.retain(|n| n.used > empty.avail);
78        non_empty.sort_unstable_by_key(|n| (n.y, n.x));
79        let wall_x = if !non_empty.is_empty() && non_empty[0].y < empty.y {
80            // Immovable nodes above empty node (real input), check they form a single wall
81            if non_empty.iter().any(|n| n.y != non_empty[0].y)
82                || non_empty.windows(2).any(|w| w[0].x + 1 != w[1].x)
83                || non_empty[0].x == 0
84                || non_empty[0].y < 2
85                || non_empty.last().unwrap().x != max_x
86            {
87                return Err(InputError::new(
88                    input,
89                    0,
90                    "expected either a single wall of immovable nodes",
91                ));
92            }
93            non_empty[0].x
94        } else {
95            // All immovable nodes are below the empty node (which happens in the example input)
96            // Add a fake to wall to the right as this adds no extra steps and avoids extra logic
97            empty.x + 1
98        };
99
100        Ok(Self {
101            max_x,
102            max_y,
103            empty: Vec2::new(empty.x, empty.y),
104            wall_x,
105        })
106    }
107
108    #[must_use]
109    pub fn part1(&self) -> u32 {
110        // All pairs are (empty node, one of the movable nodes), so the number of pairs is the
111        // number of movable nodes
112        (self.max_x + 1) * (self.max_y + 1) // All nodes
113            - (self.max_x - self.wall_x + 1) // Minus immovable nodes
114            - 1 // Minus empty node
115    }
116
117    #[must_use]
118    pub fn part2(&self) -> u32 {
119        (self.empty.x - (self.wall_x - 1)) // Move empty node left to avoid wall
120            + self.empty.y // Move empty node up to y=0
121            + ((self.max_x - 1) - (self.wall_x - 1)) // Move empty node right to x=(max - 1)
122            + ((self.max_x - 1) * 5) // Shuffle goal data to x=1
123            + 1 // Move goal data into x=0
124    }
125}
126
127examples!(Day22 -> (u32, u32) [
128    {file: "day22_example0.txt", part2: 7},
129]);
year2016/day22.rs

year2016/
day22.rs
