1  use std::collections::HashSet;
  2  
  3  #[derive(Debug, Clone, Copy, PartialEq)]
  4  enum Tile {
  5      Empty,
  6      Box,
  7      Wall,
  8  }
  9  
 10  
 11  #[derive(Debug, Clone, Copy, PartialEq)]
 12  enum Tile2 {
 13      Empty,
 14      LeftBox,
 15      RightBox,
 16      Wall,
 17  }
 18  
 19  #[derive(Debug, Clone, Copy)]
 20  enum Movement {
 21      Up,
 22      Down,
 23      Left,
 24      Right,
 25  }
 26  
 27  #[derive(Debug, Clone)]
 28  struct Robot {
 29      x: i16,
 30      y: i16,
 31  }
 32  
 33  type Map = Vec<Vec<Tile>>;
 34  type Map2 = Vec<Vec<Tile2>>;
 35  
 36  impl Robot {
 37      fn get_offsets(mov: Movement) -> (i16, i16) {
 38          match mov {
 39              Movement::Up => (0, -1),
 40              Movement::Down => (0, 1),
 41              Movement::Left => (-1, 0),
 42              Movement::Right => (1, 0),
 43          }
 44      }
 45  }
 46  
 47  fn main() {
 48      // Parse map
 49      let mut initial_x: Option<u8> = None;
 50      let mut initial_y: Option<u8> = None;
 51      let mut initial_x2: Option<u8> = None;
 52      let mut initial_y2: Option<u8> = None;
 53      let input_parts = std::str::from_utf8(include_bytes!("input"))
 54          .unwrap()
 55          .split("\n\n")
 56          .collect::<Vec<&str>>();
 57      let mut map: Map = vec![];
 58      for (y, line) in input_parts.first().unwrap().lines().enumerate() {
 59          map.push(
 60              line.chars()
 61                  .enumerate()
 62                  .map(|(x, c)| match c {
 63                      '#' => Tile::Wall,
 64                      'O' => Tile::Box,
 65                      '.' => Tile::Empty,
 66                      '@' => {
 67                          initial_x = Some(x as u8);
 68                          initial_y = Some(y as u8);
 69                          return Tile::Empty;
 70                      }
 71                      _ => todo!("Unknown map tile"),
 72                  })
 73                  .collect(),
 74          );
 75      }
 76      let mut map2: Vec<Vec<Tile2>> = vec![];
 77      for (y, line) in input_parts.first().unwrap().lines().enumerate() {
 78          map2.push(
 79              line.chars()
 80                  .enumerate()
 81                  .map(|(x, c)| match c {
 82                      '#' => vec![Tile2::Wall, Tile2::Wall],
 83                      'O' => vec![Tile2::LeftBox, Tile2::RightBox],
 84                      '.' => vec![Tile2::Empty, Tile2::Empty],
 85                      '@' => {
 86                          initial_x2 = Some(2 * x as u8);
 87                          initial_y2 = Some(y as u8);
 88                          return vec![Tile2::Empty, Tile2::Empty];
 89                      }
 90                      _ => todo!("Unknown map tile"),
 91                  })
 92                  .flatten()
 93                  .collect(),
 94          );
 95      }
 96  
 97      let (h, _) = (map.len() as i16, map[0].len() as i16);
 98  
 99      let mut robot = Robot {
100          x: initial_x.unwrap() as i16,
101          y: initial_y.unwrap() as i16,
102      };
103      let mut robot2 = Robot {
104          x: initial_x2.unwrap() as i16,
105          y: initial_y2.unwrap() as i16,
106      };
107      // Parse movements
108      let movements = input_parts
109          .last()
110          .unwrap()
111          .chars()
112          .map(|c| match c {
113              '<' => Some(Movement::Left),
114              'v' => Some(Movement::Down),
115              '>' => Some(Movement::Right),
116              '^' => Some(Movement::Up),
117              _ => None,
118          })
119          .filter(|m| m.is_some())
120          .map(|m| m.unwrap())
121          .collect::<Vec<Movement>>();
122  
123      // Part 1
124      for mov in &movements {
125          //print_map(&map, Some(&robot));
126          // println!("Moving: {:?}", &mov);
127          let (dx, dy) = Robot::get_offsets(*mov);
128          let (nx, ny) = ((robot.x + dx) as usize, (robot.y + dy) as usize);
129          match map[ny][nx] {
130              Tile::Empty => {
131                  robot.x += dx;
132                  robot.y += dy;
133              }
134  
135              Tile::Box => match mov {
136                  Movement::Up | Movement::Down => {
137                      let range = match mov {
138                          Movement::Up => (0..=ny).rev().collect::<Vec<usize>>(),
139                          Movement::Down => (ny..h as usize).collect::<Vec<usize>>(),
140                          _ => todo!("Error"),
141                      };
142  
143                      let mut first_empty_row: Option<usize> = None;
144                      for y in range {
145                          if map[y][nx] == Tile::Wall {
146                              break;
147                          }
148                          if map[y][nx] == Tile::Empty {
149                              first_empty_row = Some(y);
150                              break;
151                          }
152                      }
153                      if let Some(free_y) = first_empty_row {
154                          map[free_y][nx] = Tile::Box;
155                          map[ny][nx] = Tile::Empty;
156                          robot.x += dx;
157                          robot.y += dy;
158                      }
159                  }
160                  Movement::Left => {
161                      if let Some((i, _)) = map[robot.y as usize]
162                          .iter()
163                          .enumerate()
164                          .rev()
165                          .find(|(i, &t)| *i < nx && t == Tile::Empty)
166                      {
167                          if !map[robot.y as usize][i..nx].contains(&Tile::Wall) {
168                              map[ny][nx] = Tile::Empty;
169                              map[ny][i] = Tile::Box;
170                              robot.x += dx;
171                              robot.y += dy;
172                          }
173                      }
174                  }
175                  Movement::Right => {
176                      if let Some((i, _)) = map[robot.y as usize]
177                          .iter()
178                          .enumerate()
179                          .find(|(i, &t)| *i > nx as usize && t == Tile::Empty)
180                      {
181                          if !map[robot.y as usize][nx..i].contains(&Tile::Wall) {
182                              map[ny][nx] = Tile::Empty;
183                              map[ny][i] = Tile::Box;
184                              robot.x += dx;
185                              robot.y += dy;
186                          }
187                      }
188                  }
189              },
190              Tile::Wall => (),
191          }
192      }
193      println!("Part 1 : {}", sum_gps(&map));
194      for mov in movements {
195          // print_map(&map, Some(&robot));
196          // println!("Moving: {:?}", &mov);
197          let (dx, dy) = Robot::get_offsets(mov);
198          let (nx, ny) = ((robot2.x + dx) as usize, (robot2.y + dy) as usize);
199          match map2[ny][nx] {
200              Tile2::Empty => {
201                  robot2.x += dx;
202                  robot2.y += dy;
203              }
204              Tile2::RightBox => match mov {
205                  Movement::Left => {
206                      if let Some((i, _)) = map2[robot2.y as usize]
207                          .iter()
208                          .enumerate()
209                          .rev()
210                          .find(|(i, &t)| *i < nx && t == Tile2::Empty)
211                      {
212                          if !map2[robot2.y as usize][i..nx].contains(&Tile2::Wall) {
213                              for x in i..nx {
214                                  map2[robot2.y as usize][x] = match map2[robot2.y as usize][x] {
215                                      Tile2::LeftBox => Tile2::RightBox,
216                                      Tile2::RightBox => Tile2::LeftBox,
217                                      Tile2::Empty => Tile2::LeftBox,
218                                      _ => todo!(),
219                                  };
220                              }
221                              map2[ny][nx] = Tile2::Empty;
222                              robot2.x += dx;
223                              robot2.y += dy;
224                          }
225                      }
226                  }
227                  Movement::Down | Movement::Up => {
228                      if let Some(to_move) = is_movable_wrapper((nx as i16 - 1, ny as i16), mov, &map2)
229                      {
230                          let reversed = match mov {
231                              Movement::Up => false,
232                              Movement::Down => true,
233                              _ => todo!("Unreachable"),
234                          };
235                          let mut sorted = to_move.iter().map(|a| *a).collect::<Vec<(i16, i16)>>();
236                          sorted.sort_by_key(|x| (x.1, x.0));
237                          if reversed {
238                              sorted.reverse();
239                          }
240                          for (_x, _y) in sorted {
241                              map2[_y as usize][_x as usize] = Tile2::Empty;
242                              map2[_y as usize][_x as usize + 1] = Tile2::Empty;
243                              map2[(_y + dy) as usize][_x as usize] = Tile2::LeftBox;
244                              map2[(_y + dy) as usize][_x as usize + 1] = Tile2::RightBox;
245                          }
246                          map2[ny as usize][nx as usize] = Tile2::Empty;
247                          map2[ny as usize][nx as usize - 1] = Tile2::Empty;
248                          robot2.x += dx;
249                          robot2.y += dy;
250                      }
251                  }
252                  _ => todo!(),
253              },
254              Tile2::LeftBox => match mov {
255                  Movement::Right => {
256                      if let Some((i, _)) = map2[robot2.y as usize]
257                          .iter()
258                          .enumerate()
259                          .find(|(i, &t)| *i > nx as usize && t == Tile2::Empty)
260                      {
261                          if !map2[robot2.y as usize][nx..i].contains(&Tile2::Wall) {
262                              for x in nx..=i {
263                                  map2[robot2.y as usize][x] = match map2[robot2.y as usize][x] {
264                                      Tile2::LeftBox => Tile2::RightBox,
265                                      Tile2::RightBox => Tile2::LeftBox,
266                                      Tile2::Empty => Tile2::RightBox,
267                                      _ => todo!(),
268                                  };
269                              }
270                              map2[ny][nx] = Tile2::Empty;
271                              robot2.x += dx;
272                              robot2.y += dy;
273                          }
274                      }
275                  }
276                  Movement::Down | Movement::Up => {
277                      if let Some(to_move) = is_movable_wrapper((nx as i16, ny as i16), mov, &map2) {
278                          let reversed = match mov {
279                              Movement::Up => false,
280                              Movement::Down => true,
281                              _ => todo!("Unreachable"),
282                          };
283                          let mut sorted = to_move.iter().map(|a| *a).collect::<Vec<(i16, i16)>>();
284                          sorted.sort_by_key(|x| (x.1, x.0));
285                          if reversed {
286                              sorted.reverse();
287                          }
288                          for (_x, _y) in sorted {
289                              map2[_y as usize][_x as usize] = Tile2::Empty;
290                              map2[_y as usize][_x as usize + 1] = Tile2::Empty;
291                              map2[(_y + dy) as usize][_x as usize] = Tile2::LeftBox;
292                              map2[(_y + dy) as usize][_x as usize + 1] = Tile2::RightBox;
293                          }
294                          map2[ny as usize][nx as usize] = Tile2::Empty;
295                          map2[ny as usize][nx as usize + 1] = Tile2::Empty;
296                          robot2.x += dx;
297                          robot2.y += dy;
298                      }
299                  }
300                  _ => todo!(),
301              },
302              Tile2::Wall => (),
303          }
304      }
305      println!("Part 2 : {}", sum_gps2(&map2));
306  }
307  
308  fn gps(x: usize, y: usize) -> usize {
309      return x + y * 100;
310  }
311  
312  fn sum_gps(map: &Vec<Vec<Tile>>) -> usize {
313      let mut sum: usize = 0;
314      for (y, line) in map.iter().enumerate() {
315          for (x, tile) in line.iter().enumerate() {
316              match tile {
317                  Tile::Box => {
318                      sum += gps(x, y);
319                  }
320                  _ => (),
321              }
322          }
323      }
324      sum
325  }
326  
327  fn sum_gps2(map: &Vec<Vec<Tile2>>) -> usize {
328      let mut sum: usize = 0;
329      for (y, line) in map.iter().enumerate() {
330          for (x, tile) in line.iter().enumerate() {
331              match tile {
332                  Tile2::LeftBox => {
333                      sum += gps(x, y);
334                  }
335                  _ => (),
336              }
337          }
338      }
339      sum
340  }
341  
342  fn is_movable(
343      left_part_coords: (i16, i16),
344      direction: Movement,
345      map: &Map2,
346      to_move: &mut HashSet<(i16, i16)>,
347  ) -> bool {
348      let (dx, dy) = Robot::get_offsets(direction);
349      let (nx, ny) = ((left_part_coords.0 + dx), (left_part_coords.1 + dy));
350      to_move.insert(left_part_coords);
351      (match map[ny as usize][nx as usize] {
352          // Check the left side of the box
353          Tile2::Empty => true,
354          Tile2::LeftBox => is_movable((nx, ny), direction, map, to_move),
355          Tile2::RightBox => is_movable((nx - 1, ny), direction, map, to_move),
356          Tile2::Wall => false,
357      } && match map[ny as usize][nx as usize + 1] {
358          // Check the right side of the box
359          Tile2::Empty => true,
360          Tile2::LeftBox => is_movable((nx + 1, ny), direction, map, to_move),
361          Tile2::RightBox => is_movable((nx, ny), direction, map, to_move),
362          Tile2::Wall => false,
363      })
364  }
365  
366  fn is_movable_wrapper(
367      left_part_coords: (i16, i16),
368      direction: Movement,
369      map: &Map2,
370  ) -> Option<HashSet<(i16, i16)>> {
371      let mut to_move = HashSet::new();
372  
373      if is_movable(left_part_coords, direction, map, &mut to_move) {
374          Some(to_move)
375      } else {
376          None
377      }
378  }