1use std::collections::VecDeque;
2
3#[cfg(feature = "visualization")]
4use svgplot::{Coordinate, SvgColor, SvgImage, SvgPath, SvgScript, SvgShape, SvgStrokeLinecap};
5
6use crate::input::Input;
7
8type Position = (usize, usize);
9
10struct Graph {
11 cells: Vec<u8>,
12 visited: Vec<bool>,
13 height: usize,
14 width: usize,
15}
16
17impl Graph {
18 fn parse(input: &str) -> Result<(Position, Position, Self), String> {
19 let height = input.bytes().filter(|b| *b == b'\n').count() + 1;
20 let width = input.lines().next().unwrap_or_default().len();
21 let mut start_pos = (0, 0);
22 let mut destination_pos = (0, 0);
23 let mut cells = vec![0_u8; height * width];
24 for (y, line) in input.lines().enumerate() {
25 if line.len() != width {
26 return Err("Not all rows have equal length".to_string());
27 }
28 for (x, val) in line.bytes().enumerate() {
29 cells[y * width + x] = if val == b'S' {
30 start_pos = (x, y);
32 b'a'
33 } else if val == b'E' {
34 destination_pos = (x, y);
36 b'z'
37 } else {
38 if !val.is_ascii_lowercase() {
39 return Err("Strange character in input".to_string());
40 }
41 val
42 } - b'a';
43 }
44 }
45 let visited = vec![false; cells.len()];
46 Ok((
47 start_pos,
48 destination_pos,
49 Self {
50 cells,
51 visited,
52 height,
53 width,
54 },
55 ))
56 }
57
58 fn height_at(&self, x: usize, y: usize) -> u8 {
59 self.cells[y * self.width + x]
60 }
61
62 fn mark_visited(&mut self, x: usize, y: usize) -> bool {
63 let old = self.visited[y * self.width + x];
64 self.visited[y * self.width + x] = true;
65 !old
66 }
67
68 fn can_go(&mut self, x: usize, y: usize, dx: i32, dy: i32) -> Option<Position> {
69 if (dx < 0 && x == 0)
70 || (dy < 0 && y == 0)
71 || (dx > 0 && x + 1 == self.width)
72 || (dy > 0 && y + 1 == self.height)
73 {
74 return None;
75 }
76 let new_x = (x as i32 + dx) as usize;
77 let new_y = (y as i32 + dy) as usize;
78 let from_height = self.height_at(new_x, new_y);
79 let to_height = self.height_at(x, y);
80 (to_height <= from_height + 1 && self.mark_visited(new_x, new_y)).then_some((new_x, new_y))
81 }
82}
83
84pub fn solve(input: &Input) -> Result<u32, String> {
85 let (start_pos, destination_pos, mut graph) = Graph::parse(input.text)?;
86
87 #[cfg(feature = "visualization")]
88 let mut svg = SvgImage::new().view_box((0, 0, graph.width as i64, graph.height as i64));
89 #[cfg(feature = "visualization")]
90 let mut current_render_step = 0;
91 #[cfg(feature = "visualization")]
92 let mut circles_render_script = String::from("const circlesPerStep = ['");
93 #[cfg(feature = "visualization")]
94 let mut path_render_script = String::from("const pathsPerStep = ['");
95
96 #[cfg(feature = "visualization")]
97 {
98 for draw_height in 0..26 {
99 let mut shape = SvgShape::new();
100 let hue = (f64::from(draw_height)).mul_add(-10., 225.);
101 for x in 0..graph.width {
102 for y in 0..graph.height {
103 let height = graph.height_at(x, y);
104 if height == draw_height {
105 shape = shape
106 .move_to_absolute(x as i32, y as i32)
107 .line_to_relative(1, 0)
108 .line_to_relative(0, 1)
109 .line_to_relative(-1, 0)
110 .close();
111 }
112 }
113 }
114 if !shape.is_empty() {
115 svg.add(
116 SvgPath {
117 shape,
118 ..Default::default()
119 }
120 .title(format!("Elevation: {draw_height}"))
121 .fill(SvgColor::Hsl(hue, 70, 40)),
122 );
123 }
124 }
125
126 if input.is_part_one() {
127 svg.add(
128 svgplot::SvgRect::default()
129 .x(start_pos.0 as Coordinate)
130 .y(start_pos.1 as Coordinate)
131 .width(1)
132 .height(1)
133 .fill(SvgColor::Rgb(255, 255, 255))
134 .title("Starting position - elevation 0".to_string()),
135 );
136 }
137 svg.add(
138 svgplot::SvgRect::default()
139 .x(destination_pos.0 as Coordinate)
140 .y(destination_pos.1 as Coordinate)
141 .width(1)
142 .height(1)
143 .fill(SvgColor::Rgb(255, 255, 255))
144 .title(format!(
145 "Destination - elevation {}",
146 graph.height_at(destination_pos.0, destination_pos.1)
147 )),
148 );
149 }
150
151 let mut to_visit = VecDeque::with_capacity(64);
152 graph.mark_visited(destination_pos.0, destination_pos.1);
153 to_visit.push_back((0, destination_pos));
154
155 while let Some((cost, pos)) = to_visit.pop_front() {
156 for (dx, dy) in [(-1, 0), (0, -1), (1, 0), (0, 1)] {
157 if let Some(new_pos) = graph.can_go(pos.0, pos.1, dx, dy) {
158 let new_cost = cost + 1;
159 let at_goal = if input.is_part_one() {
160 new_pos == start_pos
161 } else {
162 graph.height_at(new_pos.0, new_pos.1) == 0
163 };
164
165 #[cfg(feature = "visualization")]
166 {
167 if new_cost != current_render_step {
168 path_render_script.push_str("', '");
169 circles_render_script.push_str("', '");
170 current_render_step = new_cost;
171 }
172 let circle_radius = 0.4;
173 circles_render_script.push_str(
174 &SvgShape::new()
175 .circle_absolute(
176 new_pos.0 as f64 + 0.5,
177 new_pos.1 as f64 + 0.5,
178 circle_radius,
179 )
180 .data_string(),
181 );
182 path_render_script.push_str(
183 &SvgShape::at(new_pos.0 as f64 + 0.5, new_pos.1 as f64 + 0.5)
184 .line_to_relative(f64::from(-dx), f64::from(-dy))
185 .data_string(),
186 );
187 }
188
189 if at_goal {
190 #[cfg(feature = "visualization")]
191 {
192 let visited_path_id = svg.add_with_id(
193 SvgPath::default()
194 .stroke(SvgColor::Rgb(255, 255, 255))
195 .stroke_width(0.2)
196 .stroke_linecap(SvgStrokeLinecap::Round),
197 );
198 let circles_path_id =
199 svg.add_with_id(SvgPath::default().fill(SvgColor::Rgb(255, 255, 255)));
200
201 circles_render_script.push_str("'];");
202 path_render_script.push_str(&format!("'];\n window.onNewStep = (step) => {{\n\
203 document.getElementById('{circles_path_id}').setAttribute('d', circlesPerStep[step]);\n\
204 const pathData = pathsPerStep.slice(0, step+1).join('');\n\
205 document.getElementById('{visited_path_id}').setAttribute('d', pathData);\n\
206 }}"));
207 svg.add(SvgScript::new(format!(
208 "{circles_render_script}{path_render_script}"
209 )));
210 input.visualization.replace(
211 svg.data_attribute("steps".to_string(), format!("{new_cost}"))
212 .data_attribute("step-duration".to_string(), format!("{}", 100))
213 .to_svg_string(),
214 );
215 }
216 return Ok(new_cost);
217 }
218 to_visit.push_back((new_cost, new_pos));
219 }
220 }
221 }
222 Err("No solution found".to_string())
223}
224
225#[test]
226pub fn tests() {
227 use crate::input::{test_part_one, test_part_two};
228
229 let test_input = "Sabqponm\nabcryxxl\naccszExk\nacctuvwj\nabdefghi";
230 test_part_one!(test_input => 31);
231 test_part_two!(test_input => 29);
232
233 let real_input = include_str!("day12_input.txt");
234 test_part_one!(real_input => 528);
235 test_part_two!(real_input => 522);
236}