1use utils::point::Point2D;
2use utils::prelude::*;
3
4#[derive(Clone, Debug)]
10pub struct Day22 {
11 max_x: u32,
12 max_y: u32,
13 wall_x: u32,
14 empty: Point2D<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 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 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 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 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 empty.x + 1
98 };
99
100 Ok(Self {
101 max_x,
102 max_y,
103 empty: Point2D::new(empty.x, empty.y),
104 wall_x,
105 })
106 }
107
108 #[must_use]
109 pub fn part1(&self) -> u32 {
110 (self.max_x + 1) * (self.max_y + 1) - (self.max_x - self.wall_x + 1) - 1 }
116
117 #[must_use]
118 pub fn part2(&self) -> u32 {
119 (self.empty.x - (self.wall_x - 1)) + self.empty.y + ((self.max_x - 1) - (self.wall_x - 1)) + ((self.max_x - 1) * 5) + 1 }
125}
126
127examples!(Day22 -> (u32, u32) [
128 {file: "day22_example0.txt", part2: 7},
129]);