12

6 files changed, 216 insertions, 0 deletions

diff --git a/12/Cargo.toml b/12/Cargo.toml
new file mode 100644
index 0000000..441770e
--- /dev/null
+++ b/12/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "advent_12"
+version = "0.1.0"
+authors = ["Irene Knapp <ireneista@gmail.com>"]
+edition = "2018"
+
+[dependencies]
+advent_lib = { path = "../lib" }
+
+[dev-dependencies]
+assert_cmd = "0.10"
diff --git a/12/input b/12/input
new file mode 100644
index 0000000..6a77547
--- /dev/null
+++ b/12/input
@@ -0,0 +1,23 @@
+QR-da
+QR-end
+QR-al
+start-op
+zh-iw
+zh-start
+da-PF
+op-bj
+iw-QR
+end-HR
+bj-PF
+da-LY
+op-PF
+bj-iw
+end-da
+bj-zh
+HR-iw
+zh-op
+zh-PF
+HR-bj
+start-PF
+HR-da
+QR-bj
diff --git a/12/src/main.rs b/12/src/main.rs
new file mode 100644
index 0000000..b6ca4f1
--- /dev/null
+++ b/12/src/main.rs
@@ -0,0 +1,156 @@
+use advent_lib::prelude::*;
+
+use std::collections::HashMap;
+use std::collections::HashSet;
+
+
+#[derive(PartialEq, Eq, Hash, Debug, Clone)]
+enum Cave {
+  Start,
+  End,
+  Small(String),
+  Large(String),
+}
+
+
+fn main() -> Result<()> {
+  let mut args = std::env::args();
+  if args.len() != 2 {
+    eprintln!("Usage: advent input");
+  }
+  let _ = args.next();
+  let filename = args.next().unwrap();
+
+  let input = advent_lib::read_lines_file(&filename)?;
+
+  let mut connections: HashMap<Cave,Vec<Cave>> = HashMap::new();
+  for line in &input {
+    let words: Vec<&str> = line.split('-').collect();
+    let a = parse_cave(words[0]);
+    let b = parse_cave(words[1]);
+
+    match connections.get_mut(&a) {
+      None => {
+        let mut destinations = Vec::new();
+        destinations.push(b.clone());
+        connections.insert(a.clone(), destinations);
+      }
+      Some(destinations) => {
+        destinations.push(b.clone());
+      }
+    }
+
+    match connections.get_mut(&b) {
+      None => {
+        let mut destinations = Vec::new();
+        destinations.push(a.clone());
+        connections.insert(b.clone(), destinations);
+      }
+      Some(destinations) => {
+        destinations.push(a.clone());
+      }
+    }
+  }
+
+  let path_count = tour_caves(Cave::Start, &connections, HashSet::new());
+  println!("{}", path_count);
+
+  let longer_path_count = longer_tour_caves(Cave::Start, &connections,
+    HashMap::new(), false);
+  println!("{}", longer_path_count);
+
+  Ok(())
+}
+
+
+fn parse_cave(name: &str) -> Cave {
+  if name == "start" {
+    Cave::Start
+  } else if name == "end" {
+    Cave::End
+  } else if name.chars().nth(0).unwrap().is_uppercase() {
+    Cave::Large(name.to_string())
+  } else {
+    Cave::Small(name.to_string())
+  }
+}
+
+
+fn tour_caves(here: Cave, map: &HashMap<Cave,Vec<Cave>>,
+    visited: HashSet<Cave>)
+  -> i64
+{
+  if here == Cave::End {
+    return 1;
+  }
+
+  let mut path_count = 0;
+
+  for destination in map.get(&here).unwrap() {
+    if !visited.contains(destination) {
+      let mut new_visited = visited.clone();
+      match here {
+        Cave::Large(_) => { },
+        _ => {
+          new_visited.insert(here.clone());
+        }
+      }
+      path_count += tour_caves(destination.clone(), map, new_visited);
+    }
+  }
+
+  path_count
+}
+
+
+fn longer_tour_caves(here: Cave, map: &HashMap<Cave,Vec<Cave>>,
+    visited: HashMap<Cave,usize>, have_double_visited: bool)
+  -> i64
+{
+  if here == Cave::End {
+    return 1;
+  }
+
+  let mut path_count = 0;
+
+  for destination in map.get(&here).unwrap() {
+    let (should_go, new_have_double_visited) = match visited.get(destination)
+    {
+      None => (true, have_double_visited),
+      Some(1) => {
+        if have_double_visited {
+          (false, true)
+        } else {
+          (true, true)
+        }
+      }
+      _ => (false, have_double_visited),
+    };
+
+    if should_go {
+      let mut new_visited = visited.clone();
+      let here_visit_count = visited.get(&here);
+      match here {
+        Cave::Large(_) => { },
+        Cave::Small(_) => {
+          new_visited.insert(here.clone(), match here_visit_count {
+            None => 1,
+            Some(n) => n + 1,
+          });
+        }
+        Cave::Start => {
+          new_visited.insert(here.clone(), 2);
+        }
+        Cave::End => {
+          new_visited.insert(here.clone(), 2);
+        }
+      }
+
+      path_count += longer_tour_caves(destination.clone(), map, new_visited,
+        new_have_double_visited);
+    }
+  }
+
+  path_count
+}
+
diff --git a/12/tests/main.rs b/12/tests/main.rs
new file mode 100644
index 0000000..962bfa0
--- /dev/null
+++ b/12/tests/main.rs
@@ -0,0 +1,17 @@
+use assert_cmd::prelude::*;
+//use predicates::prelude::*;
+use std::process::Command;
+
+
+#[test]
+fn personal_input() -> Result<(), Box<dyn std::error::Error>> {
+  let mut command = Command::cargo_bin("advent_12")?;
+
+  command.arg("input");
+  command.assert().success().stdout(
+      "5576\n\
+      152837\n");
+
+  Ok(())
+}
+
diff --git a/Cargo.lock b/Cargo.lock
index 27fd18a..91ae245 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -89,6 +89,14 @@ dependencies = [
 ]
 
 [[package]]
+name = "advent_12"
+version = "0.1.0"
+dependencies = [
+ "advent_lib",
+ "assert_cmd",
+]
+
+[[package]]
 name = "advent_lib"
 version = "0.1.0"
 dependencies = [
diff --git a/Cargo.toml b/Cargo.toml
index abc26f4..4eac77e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,4 +12,5 @@ members = [
   "09",
   "10",
   "11",
+  "12",
 ]