commit db0cddff1d0b71add22acede3da743b6083139f3
parent 84799e7071da85569c019594c977092b41c4979c
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 12 Dec 2021 12:30:17 -0600
Add 2021 day 12
Diffstat:
2 files changed, 189 insertions(+), 0 deletions(-)
diff --git a/2021/day12/input.txt b/2021/day12/input.txt
@@ -0,0 +1,22 @@
+end-MY
+MY-xc
+ho-NF
+start-ho
+NF-xc
+NF-yf
+end-yf
+xc-TP
+MY-qo
+yf-TP
+dc-NF
+dc-xc
+start-dc
+yf-MY
+MY-ho
+EM-uh
+xc-yf
+ho-dc
+uh-NF
+yf-ho
+end-uh
+start-NF
diff --git a/2021/day12/main.rs b/2021/day12/main.rs
@@ -0,0 +1,167 @@
+use std::collections::{HashMap, HashSet, VecDeque};
+
+#[derive(Debug, Copy, Clone)]
+enum CaveSize {
+ Big,
+ Small,
+}
+
+impl CaveSize {
+ fn check(s: &str) -> CaveSize {
+ if s.chars().all(char::is_lowercase) {
+ CaveSize::Small
+ } else {
+ CaveSize::Big
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct CaveSystem {
+ map: HashMap<String, HashSet<String>>,
+ cave_size: HashMap<String, CaveSize>,
+}
+
+impl CaveSystem {
+ fn new(input: &Vec<String>) -> Self {
+ let mut map = HashMap::<String, HashSet<String>>::new();
+ let mut cave_size = HashMap::<String, CaveSize>::new();
+ for s in input {
+ let mut tmp = s.split('-');
+ let a = tmp.next().unwrap().to_string();
+ let b = tmp.next().unwrap().to_string();
+ if let Some(connected) = map.get_mut(&a) {
+ connected.insert(b.clone());
+ } else {
+ map.insert(a.clone(), {
+ let mut tmp = HashSet::new();
+ tmp.insert(b.clone());
+ tmp
+ });
+ }
+ if !cave_size.contains_key(&a) {
+ cave_size.insert(a.clone(), CaveSize::check(&a));
+ }
+ if let Some(connected) = map.get_mut(&b) {
+ connected.insert(a.clone());
+ } else {
+ map.insert(b.clone(), {
+ let mut tmp = HashSet::new();
+ tmp.insert(a.clone());
+ tmp
+ });
+ }
+ if !cave_size.contains_key(&b) {
+ cave_size.insert(b.clone(), CaveSize::check(&b));
+ }
+ }
+ CaveSystem { map, cave_size }
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<_>>();
+ let cave_system = CaveSystem::new(&input);
+ // 5076
+ println!("Part 1: {}", part_1(&cave_system));
+ // 145643
+ println!("Part 2: {}", part_2(&cave_system));
+}
+
+fn part_1(cave_system: &CaveSystem) -> i32 {
+ let cave_system = cave_system.clone();
+ let mut queue = VecDeque::<(VecDeque<String>, HashSet<String>)>::new();
+ queue.push_back({
+ let mut path = VecDeque::<String>::new();
+ path.push_back("start".to_string());
+ (path, HashSet::<String>::new())
+ });
+ let mut path_count = 0;
+ while let Some((path, mut visited)) = queue.pop_front() {
+ if let Some(last_step) = path.back() {
+ visited.insert(last_step.clone());
+ if last_step == "end" {
+ path_count += 1;
+ } else {
+ for next_step in cave_system.map[last_step].iter() {
+ match (
+ cave_system.cave_size[next_step],
+ visited.contains(next_step),
+ ) {
+ (CaveSize::Big, _) | (CaveSize::Small, false) => {
+ queue.push_back((
+ {
+ let mut tmp = path.clone();
+ tmp.push_back(next_step.clone());
+ tmp
+ },
+ visited.clone(),
+ ));
+ }
+ _ => (),
+ }
+ }
+ }
+ }
+ }
+ path_count
+}
+
+fn part_2(cave_system: &CaveSystem) -> i32 {
+ let cave_system = cave_system.clone();
+ let mut queue = VecDeque::<(VecDeque<String>, HashSet<String>, Option<String>)>::new();
+ queue.push_back({
+ let mut path = VecDeque::<String>::new();
+ path.push_back("start".to_string());
+ (path, HashSet::<String>::new(), None)
+ });
+ let mut path_count = 0;
+ while let Some((path, mut visited, twice)) = queue.pop_front() {
+ if let Some(last_step) = path.back() {
+ visited.insert(last_step.clone());
+ if last_step == "end" {
+ path_count += 1;
+ } else {
+ for next_step in cave_system.map[last_step].iter() {
+ match (
+ cave_system.cave_size[next_step],
+ visited.contains(next_step),
+ twice.clone(),
+ ) {
+ (CaveSize::Big, _, twice) | (CaveSize::Small, false, twice) => {
+ queue.push_back((
+ {
+ let mut tmp = path.clone();
+ tmp.push_back(next_step.clone());
+ tmp
+ },
+ visited.clone(),
+ twice,
+ ));
+ }
+ (CaveSize::Small, true, None) => {
+ if next_step != "start" {
+ queue.push_back((
+ {
+ let mut tmp = path.clone();
+ tmp.push_back(next_step.clone());
+ tmp
+ },
+ visited.clone(),
+ Some(next_step.clone()),
+ ));
+ }
+ }
+ _ => (),
+ }
+ }
+ }
+ }
+ }
+ path_count
+}