commit 87e5fe549f53d56d70763009fd4551dc697925ac
parent a0e6a902eb4a9a8eb23e7a258667dc852d00fe6b
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Thu, 23 Dec 2021 18:45:09 -0600
Add 2021 day 23
Diffstat:
2 files changed, 472 insertions(+), 0 deletions(-)
diff --git a/2021/day23/input.txt b/2021/day23/input.txt
@@ -0,0 +1,5 @@
+#############
+#...........#
+###D#C#B#C###
+ #D#A#A#B#
+ #########
diff --git a/2021/day23/main.rs b/2021/day23/main.rs
@@ -0,0 +1,467 @@
+use std::collections::{HashMap, HashSet, VecDeque};
+
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+enum Amphipod {
+ A,
+ B,
+ C,
+ D,
+}
+impl Amphipod {
+ fn new(c: char) -> Self {
+ match c {
+ 'A' => Self::A,
+ 'B' => Self::B,
+ 'C' => Self::C,
+ 'D' => Self::D,
+ _ => unreachable!(),
+ }
+ }
+ fn cost(&self) -> usize {
+ match self {
+ Self::A => 1,
+ Self::B => 10,
+ Self::C => 100,
+ Self::D => 1000,
+ }
+ }
+}
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .skip(2)
+ .take(2)
+ .map(|s| {
+ s.chars()
+ .filter(|c| c.is_alphabetic())
+ .map(Amphipod::new)
+ .collect::<Vec<_>>()
+ })
+ .collect::<Vec<_>>();
+ // 19059
+ println!("Part 1: {}", part_1(&input));
+ // 48541
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn map_routes(
+ map_size: usize,
+ mut step_count: HashMap<(usize, usize), usize>,
+) -> HashMap<(usize, usize), usize> {
+ loop {
+ let mut step_count_new = HashMap::new();
+ for start in 0..map_size {
+ for end in 0..map_size {
+ for mid in 0..map_size {
+ if start != end && start != mid && mid != end {
+ match (
+ step_count.get(&(start, mid)),
+ step_count.get(&(mid, end)),
+ step_count.get(&(start, end)),
+ ) {
+ (Some(a), Some(b), None) => {
+ step_count_new.insert((start, end), a + b);
+ }
+ (Some(a), Some(b), Some(c)) => {
+ if a + b < *c {
+ step_count_new.insert((start, end), a + b);
+ }
+ }
+ _ => (),
+ }
+ }
+ }
+ }
+ }
+ if step_count_new.is_empty() {
+ break;
+ }
+ for ((a, b), cost) in step_count_new.into_iter() {
+ step_count.insert((a, b), cost);
+ }
+ }
+ step_count
+}
+
+fn part_1(input: &Vec<Vec<Amphipod>>) -> usize {
+ // #############
+ // #01.4.7.a.de#
+ // ###2#5#8#b###
+ // #3#6#9#c#
+ // #########
+ let map_size = 15;
+ let corridor_pos = [0, 1, 4, 7, 10, 13, 14]
+ .iter()
+ .map(|&x| x as usize)
+ .collect::<HashSet<usize>>();
+ let room_pos = [2, 3, 5, 6, 8, 9, 11, 12]
+ .iter()
+ .map(|&x| x as usize)
+ .collect::<HashSet<usize>>();
+ let entrance_map = {
+ let mut tmp = HashMap::<usize, usize>::new();
+ for &(a, b) in [(2, 3), (5, 6), (8, 9), (11, 12)].iter() {
+ tmp.insert(a, a);
+ tmp.insert(b, a);
+ }
+ tmp
+ };
+ let is_reachable = |pos: &[Option<Amphipod>], curr_pos: usize, dest_pos: usize| -> bool {
+ // assumes dest_pos is reachable if inside a room
+ let corridor_clear = corridor_pos
+ .iter()
+ .filter(|&p| (*p > curr_pos && *p < dest_pos) || (*p > dest_pos && *p < curr_pos))
+ .all(|&p| pos[p].is_none());
+ let entrance_clear = if let Some(&entrance_pos) = entrance_map.get(&curr_pos) {
+ (entrance_pos..curr_pos).all(|p| pos[p].is_none())
+ } else {
+ true
+ };
+ corridor_clear && entrance_clear
+ };
+ let step_count = {
+ let mut step_count = HashMap::new();
+ // build up dist 1 step counts
+ // intersections
+ for &(a, b, c) in [(1, 2, 4), (4, 5, 7), (7, 8, 10), (10, 11, 13)].iter() {
+ step_count.insert((a, b), 2);
+ step_count.insert((b, a), 2);
+ step_count.insert((a, c), 2);
+ step_count.insert((c, a), 2);
+ step_count.insert((c, b), 2);
+ step_count.insert((b, c), 2);
+ }
+ // room
+ for &(a, b) in [(2, 3), (5, 6), (8, 9), (11, 12)].iter() {
+ step_count.insert((a, b), 1);
+ step_count.insert((b, a), 1);
+ }
+ // corridor ends
+ for &(a, b) in [(0, 1), (13, 14)].iter() {
+ step_count.insert((a, b), 1);
+ step_count.insert((b, a), 1);
+ }
+ map_routes(map_size, step_count)
+ };
+ let init_pos = {
+ let mut tmp = vec![None; map_size];
+ tmp[2] = Some(input[0][0]);
+ tmp[3] = Some(input[1][0]);
+ tmp[5] = Some(input[0][1]);
+ tmp[6] = Some(input[1][1]);
+ tmp[8] = Some(input[0][2]);
+ tmp[9] = Some(input[1][2]);
+ tmp[11] = Some(input[0][3]);
+ tmp[12] = Some(input[1][3]);
+ tmp
+ };
+ let final_pos = {
+ let mut tmp = vec![None; map_size];
+ tmp[2] = Some(Amphipod::A);
+ tmp[3] = Some(Amphipod::A);
+ tmp[5] = Some(Amphipod::B);
+ tmp[6] = Some(Amphipod::B);
+ tmp[8] = Some(Amphipod::C);
+ tmp[9] = Some(Amphipod::C);
+ tmp[11] = Some(Amphipod::D);
+ tmp[12] = Some(Amphipod::D);
+ tmp
+ };
+ let mut min_cost = None;
+ let mut queue = VecDeque::new();
+ queue.push_back((0usize, init_pos));
+ while let Some((cost, pos)) = queue.pop_front() {
+ // check if we've reached destination
+ if (0..pos.len()).all(|i| pos[i] == final_pos[i]) {
+ min_cost = match min_cost {
+ None => Some(cost),
+ Some(min_cost) => Some(min_cost.min(cost)),
+ };
+ continue;
+ }
+ // check possible moves for each amphipod, perform one of the following:
+ // 1. from room pos to corridor pos + from corridor pos to dest room pos
+ // 2. from room pos directly to dest room pos
+ for curr_pos in 0..map_size {
+ if let Some(x) = pos[curr_pos] {
+ let dest_room = match x {
+ Amphipod::A => (2, 3),
+ Amphipod::B => (5, 6),
+ Amphipod::C => (8, 9),
+ Amphipod::D => (11, 12),
+ };
+ // no need to move if already at destination room
+ if curr_pos == dest_room.1
+ || (curr_pos == dest_room.0 && pos[dest_room.1] == Some(x))
+ {
+ continue;
+ }
+ // pick dest
+ if let Some(dest_pos) = match (pos[dest_room.0], pos[dest_room.1]) {
+ (None, None) => Some(dest_room.1),
+ (None, Some(y)) => {
+ if y == x {
+ Some(dest_room.0)
+ } else {
+ None
+ }
+ }
+ _ => None,
+ } {
+ // move to dest room if available
+ if is_reachable(&pos, curr_pos, dest_pos) {
+ let next_cost =
+ cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
+ if let Some(min_cost) = min_cost {
+ if min_cost < next_cost {
+ continue;
+ }
+ }
+ let mut next_pos = pos.clone();
+ next_pos[curr_pos] = None;
+ next_pos[dest_pos] = Some(x);
+ queue.push_back((next_cost, next_pos));
+ }
+ } else if room_pos.contains(&curr_pos) {
+ // try one of the corridor positions if starting from room pos
+ for &dest_pos in corridor_pos.iter() {
+ if pos[dest_pos].is_none() && is_reachable(&pos, curr_pos, dest_pos) {
+ let next_cost =
+ cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
+ if let Some(min_cost) = min_cost {
+ if min_cost < next_cost {
+ continue;
+ }
+ }
+ let mut next_pos = pos.clone();
+ next_pos[curr_pos] = None;
+ next_pos[dest_pos] = Some(x);
+ queue.push_back((next_cost, next_pos));
+ }
+ }
+ }
+ }
+ }
+ }
+ min_cost.unwrap()
+}
+fn part_2(input: &Vec<Vec<Amphipod>>) -> usize {
+ // #################
+ // #01.6.11.16.2122#
+ // ###2# 7#12#17####
+ // #3# 8#13#18#
+ // #4# 9#14#19#
+ // #5#10#15#20#
+ // ############
+ let map_size = 23;
+ let corridor_pos = [0, 1, 6, 11, 16, 21, 22]
+ .iter()
+ .map(|&x| x as usize)
+ .collect::<HashSet<usize>>();
+ let room_pos = [2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20]
+ .iter()
+ .map(|&x| x as usize)
+ .collect::<HashSet<usize>>();
+ let entrance_map = {
+ let mut tmp = HashMap::<usize, usize>::new();
+ for &(a, b, c, d) in [
+ (2, 3, 4, 5),
+ (7, 8, 9, 10),
+ (12, 13, 14, 15),
+ (17, 18, 19, 20),
+ ]
+ .iter()
+ {
+ tmp.insert(a, a);
+ tmp.insert(b, a);
+ tmp.insert(c, a);
+ tmp.insert(d, a);
+ }
+ tmp
+ };
+ let is_reachable = |pos: &[Option<Amphipod>], curr_pos: usize, dest_pos: usize| -> bool {
+ // assumes dest_pos is reachable if inside a room
+ let corridor_clear = corridor_pos
+ .iter()
+ .filter(|&p| (*p > curr_pos && *p < dest_pos) || (*p > dest_pos && *p < curr_pos))
+ .all(|&p| pos[p].is_none());
+ let entrance_clear = if let Some(&entrance_pos) = entrance_map.get(&curr_pos) {
+ (entrance_pos..curr_pos).all(|p| pos[p].is_none())
+ } else {
+ true
+ };
+ corridor_clear && entrance_clear
+ };
+ let step_count = {
+ let mut step_count = HashMap::new();
+ // build up dist 1 step counts
+ // intersections
+ for &(a, b, c) in [(1, 2, 6), (6, 7, 11), (11, 12, 16), (16, 17, 21)].iter() {
+ step_count.insert((a, b), 2);
+ step_count.insert((b, a), 2);
+ step_count.insert((a, c), 2);
+ step_count.insert((c, a), 2);
+ step_count.insert((c, b), 2);
+ step_count.insert((b, c), 2);
+ }
+ // room
+ for &(a, b) in [(2, 5), (7, 10), (12, 15), (17, 20)].iter() {
+ for start in a..=b {
+ for end in (start + 1)..=b {
+ if start != end {
+ step_count.insert((start, end), end - start);
+ step_count.insert((end, start), end - start);
+ }
+ }
+ }
+ }
+ // corridor ends
+ for &(a, b) in [(0, 1), (21, 22)].iter() {
+ step_count.insert((a, b), 1);
+ step_count.insert((b, a), 1);
+ }
+ map_routes(map_size, step_count)
+ };
+ let init_pos = {
+ let mut tmp = vec![None; map_size];
+ tmp[2] = Some(input[0][0]);
+ tmp[3] = Some(Amphipod::D);
+ tmp[4] = Some(Amphipod::D);
+ tmp[5] = Some(input[1][0]);
+ tmp[7] = Some(input[0][1]);
+ tmp[8] = Some(Amphipod::C);
+ tmp[9] = Some(Amphipod::B);
+ tmp[10] = Some(input[1][1]);
+ tmp[12] = Some(input[0][2]);
+ tmp[13] = Some(Amphipod::B);
+ tmp[14] = Some(Amphipod::A);
+ tmp[15] = Some(input[1][2]);
+ tmp[17] = Some(input[0][3]);
+ tmp[18] = Some(Amphipod::A);
+ tmp[19] = Some(Amphipod::C);
+ tmp[20] = Some(input[1][3]);
+ tmp
+ };
+ let final_pos = {
+ let mut tmp = vec![None; map_size];
+ for a in 2..=5 {
+ tmp[a] = Some(Amphipod::A);
+ }
+ for b in 7..=10 {
+ tmp[b] = Some(Amphipod::B);
+ }
+ for c in 12..=15 {
+ tmp[c] = Some(Amphipod::C);
+ }
+ for d in 17..=20 {
+ tmp[d] = Some(Amphipod::D);
+ }
+ tmp
+ };
+ let mut min_cost = None;
+ let mut queue = VecDeque::new();
+ queue.push_back((0usize, init_pos));
+ while let Some((cost, pos)) = queue.pop_front() {
+ // check if we've reached destination
+ if (0..pos.len()).all(|i| pos[i] == final_pos[i]) {
+ min_cost = match min_cost {
+ None => Some(cost),
+ Some(min_cost) => Some(min_cost.min(cost)),
+ };
+ continue;
+ }
+ // check possible moves for each amphipod, perform one of the following:
+ // 1. from room pos to corridor pos + from corridor pos to dest room pos
+ // 2. from room pos directly to dest room pos
+ for curr_pos in 0..map_size {
+ if let Some(x) = pos[curr_pos] {
+ // check if it can/need to move to destination room
+ let dest_room = match x {
+ Amphipod::A => (2, 3, 4, 5),
+ Amphipod::B => (7, 8, 9, 10),
+ Amphipod::C => (12, 13, 14, 15),
+ Amphipod::D => (17, 18, 19, 20),
+ };
+ // no need to move if already at destination room
+ if curr_pos == dest_room.3
+ || (curr_pos == dest_room.2 && pos[dest_room.3] == Some(x))
+ || (curr_pos == dest_room.1
+ && pos[dest_room.2] == Some(x)
+ && pos[dest_room.3] == Some(x))
+ || (curr_pos == dest_room.0
+ && pos[dest_room.1] == Some(x)
+ && pos[dest_room.2] == Some(x)
+ && pos[dest_room.3] == Some(x))
+ {
+ continue;
+ }
+ // pick dest
+ if let Some(dest_pos) = match (
+ pos[dest_room.0],
+ pos[dest_room.1],
+ pos[dest_room.2],
+ pos[dest_room.3],
+ ) {
+ (None, None, None, None) => Some(dest_room.3),
+ (None, None, None, Some(y3)) => {
+ if y3 == x {
+ Some(dest_room.2)
+ } else {
+ None
+ }
+ }
+ (None, None, Some(y2), Some(y3)) => {
+ if y3 == x && y2 == x {
+ Some(dest_room.1)
+ } else {
+ None
+ }
+ }
+ (None, Some(y1), Some(y2), Some(y3)) => {
+ if y3 == x && y2 == x && y1 == x {
+ Some(dest_room.0)
+ } else {
+ None
+ }
+ }
+ _ => None,
+ } {
+ // move to dest room if available
+ if is_reachable(&pos, curr_pos, dest_pos) {
+ let next_cost =
+ cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
+ if let Some(min_cost) = min_cost {
+ if min_cost < next_cost {
+ continue;
+ }
+ }
+ let mut next_pos = pos.clone();
+ next_pos[curr_pos] = None;
+ next_pos[dest_pos] = Some(x);
+ queue.push_back((next_cost, next_pos));
+ }
+ } else if room_pos.contains(&curr_pos) {
+ // try one of the corridor positions if starting from room pos
+ for &dest_pos in corridor_pos.iter() {
+ if pos[dest_pos].is_none() && is_reachable(&pos, curr_pos, dest_pos) {
+ let next_cost =
+ cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
+ if let Some(min_cost) = min_cost {
+ if min_cost < next_cost {
+ continue;
+ }
+ }
+ let mut next_pos = pos.clone();
+ next_pos[curr_pos] = None;
+ next_pos[dest_pos] = Some(x);
+ queue.push_back((next_cost, next_pos));
+ }
+ }
+ }
+ }
+ }
+ }
+ min_cost.unwrap()
+}