From efb6f73fdb7f512b419547c0baa7913e6b92d539 Mon Sep 17 00:00:00 2001 From: cos Date: Sun, 12 Dec 2021 08:41:41 +0100 Subject: Add day12, 2021 --- 2021/rust/Cargo.toml | 2 +- 2021/rust/day12/Cargo.toml | 9 ++ 2021/rust/day12/src/main.rs | 354 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 364 insertions(+), 1 deletion(-) create mode 100644 2021/rust/day12/Cargo.toml create mode 100644 2021/rust/day12/src/main.rs diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml index 9d8c085..06ea192 100644 --- a/2021/rust/Cargo.toml +++ b/2021/rust/Cargo.toml @@ -11,7 +11,7 @@ members = [ "day09", "day10", "day11", -# "day12", + "day12", # "day13", # "day14", # "day15", diff --git a/2021/rust/day12/Cargo.toml b/2021/rust/day12/Cargo.toml new file mode 100644 index 0000000..7b286ff --- /dev/null +++ b/2021/rust/day12/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "day12" +version = "0.1.0" +authors = ["cos "] +edition = "2021" + +[dependencies] +aoc = { path = "../../../common/rust/aoc" } +anyhow = "1.0" diff --git a/2021/rust/day12/src/main.rs b/2021/rust/day12/src/main.rs new file mode 100644 index 0000000..3d4b5e9 --- /dev/null +++ b/2021/rust/day12/src/main.rs @@ -0,0 +1,354 @@ +use { + anyhow::{ + anyhow, + Context, + Result, + }, + std::{ + cell::Cell, + collections::HashMap, + env::args, + fs::File, + io::{ + BufRead, + BufReader, + }, + path::Path, + }, +}; + +#[derive(Clone,Copy,Debug,PartialEq)] +enum NodeType { + Small, + Large, +} + +#[derive(Clone,Debug,PartialEq)] +struct Node { + name: String, + size: NodeType, +} + +impl Node { + fn new(name: S) -> Result { + let n = name.to_string(); + let size = if n.chars().filter(|c| c.is_lowercase()).count() == n.len() { + Ok(NodeType::Small) + } else if n.chars().filter(|c| c.is_uppercase()).count() == n.len() { + Ok(NodeType::Large) + } else { + Err(anyhow!(r#"Could not determine whether {} is a large or small cave"#, n)) + }?; + Ok(Self { + name: n, + size, + }) + } + + fn size(&self) -> NodeType { + self.size + } +} + +#[derive(Clone,Debug)] +struct NodeList { + inner: Vec, +} + +impl NodeList { + fn new(init: I) -> Result + where I: Clone + IntoIterator, S: ToString + { + let mut nodelist = NodeList { inner: vec![], }; + for (this, other) in init.into_iter() { + for name in [this.to_string(), other.to_string()].iter() { + if !nodelist.contains_key(name) { + let node = Node::new(name)?; + nodelist.push(node); + } + } + } + Ok(nodelist) + } + + fn names(&self) -> Vec<&str> { + (0..self.inner.len()).into_iter().map(|index| { + self.inner[index].name.as_ref() + }).collect() + } + + fn push(&mut self, node: Node) { + self.inner.push(node); + } + + fn contains_key(&self, name: &str) -> bool { + for index in 0..self.inner.len() { + if self.inner[index].name == name { + return true; + } + } + false + } + + fn get(&self, name: &str) -> Option<&Node> { + for index in 0..self.inner.len() { + if self.inner[index].name == name { + if let Some(node) = self.inner.get(index) { + return Some(node) + } + } + } + None + } +} + +#[derive(Clone,Debug)] +struct Edge<'a> { + nodes: Vec<&'a Node>, +} + +impl<'a> Edge<'a> { + fn new(nodes: Vec<&'a Node>) -> Self { + Self { + nodes, + } + } + + fn contains(&self, needle: &Node) -> bool { + for node in &self.nodes { + if **node == *needle { + return true; + } + } + false + } +} + +#[derive(Clone,Debug)] +struct EdgeList<'a> { + inner: Vec>, +} + +impl<'a> EdgeList<'a> { + fn new(init: I, nodelist: &'a NodeList) -> Result + where I: IntoIterator, S: ToString + { + let inner = init.into_iter().map(|(this, other)| { + let this_node = nodelist.get(&this.to_string()) + .ok_or(anyhow!("Failed creating EdgeList"))?; + let other_node = nodelist.get(&other.to_string()) + .ok_or(anyhow!("Failed creating EdgeList"))?; + Ok(Edge::new(vec![this_node, other_node])) + }).collect::>>()?; + Ok(Self { + inner, + }) + } + + fn neighbours(&self, this: &Node) -> Vec<&Node> { + let mut nodes = vec![]; + for edge in self.inner.iter() { + if edge.contains(this) { + for node in edge.nodes.iter().filter(|node| ***node != *this) { + nodes.push(*node); + } + } + } + + nodes + } +} + +#[derive(Clone,Copy,Debug,Eq,PartialEq)] +enum State { + Explorable, + Unexplored, + Visited, + Exhausted, +} + +#[derive(Clone,Debug)] +struct VisitList { + inner: HashMap>, +} + +impl VisitList { + fn new<'a, I>(init: I, state: State) -> Self + where I: IntoIterator + { + let inner = init.into_iter() + .map(|key| (String::from(key), Cell::new(state))).collect(); + + Self { + inner, + } + } + + fn state(&self, key: &str) -> Option { + self.inner.get(key).map(|cell| cell.get()) + } + + fn set_state(&self, key: &str, state: State) -> Result<()> { + self.inner.get(key) + .ok_or_else(|| anyhow!("Could not set state for non-existent: {}", key))?.set(state); + Ok(()) + } +} + +#[derive(Clone,Debug)] +struct Cave<'a> { + nodelist: &'a NodeList, + edgelist: EdgeList<'a>, +} + +impl<'a> Cave<'a> { + fn new(nodelist: &'a NodeList, edgelist: EdgeList<'a>) -> Result { + Ok(Self{ + nodelist, + edgelist, + }) + } + + fn explorable<'b, 'c: 'b>(&'b self, node: &'c Node) -> Explorable { + Explorable::new(&self.edgelist, node) + } + + fn recurse(&self, visited: VisitList, node: &Node) -> Result { + let mut paths = 0; + let node_state = visited.state(&node.name) + .ok_or_else(|| anyhow!("No state for {}", node.name))?; + match (node.name.as_str(), node.size(), node_state) { + ("start", _, _) => { + visited.set_state(&node.name, State::Exhausted)?; + }, + ("end", _, _) => { + return Ok(1); + }, + (_, _, State::Exhausted) => { + return Ok(0); + } + (_, NodeType::Small, State::Explorable) => { + visited.set_state(&node.name, State::Visited)?; + } + (_, NodeType::Small, State::Unexplored) => { + visited.set_state(&node.name, State::Exhausted)?; + } + (_, NodeType::Small, State::Visited) => { + for cave in self.nodelist.inner.iter() { + let cave_state = visited.state(&cave.name); + if cave.size() == NodeType::Small { + if cave_state == Some(State::Explorable) { + visited.set_state(&cave.name, State::Unexplored)?; + } else { + visited.set_state(&cave.name, State::Exhausted)?; + } + } + } + visited.set_state(&node.name, State::Exhausted)?; + } + (_, NodeType::Large, State::Explorable | State::Unexplored | State::Visited) => { + visited.set_state(&node.name, State::Visited)?; + } + } + + let explorable = self.explorable(node) + .collect::>(); + + for next_node in explorable { + visited.set_state("end", State::Unexplored)?; + let next_state = visited.state(&next_node.name) + .ok_or_else(|| anyhow!("Missing state for: {}", next_node.name))?; + + match (next_node.size(), next_state) { + (_, State::Exhausted) => { + continue; + }, + (NodeType::Small, State::Explorable | State::Unexplored | State::Visited) => { + paths += self.recurse(visited.clone(), next_node)?; + }, + (NodeType::Large, State::Explorable | State::Unexplored | State::Visited) => { + paths += self.recurse(visited.clone(), next_node)?; + }, + } + } + Ok(paths) + } + + fn walk_all(&self, state: State) -> Result { + let nodelist = &self.nodelist; + let node_names = nodelist.names(); + let start = nodelist.get("start").ok_or(anyhow!("Could not find start node"))?; + let visited = VisitList::new(node_names, state); + + self.recurse(visited, start) + } +} + +struct Explorable<'a, 'b> { + positition: usize, + edgelist: &'a EdgeList<'a>, + node: &'b Node, +} + +impl<'a, 'b> Explorable<'a, 'b> { + fn new(edgelist: &'a EdgeList, node: &'b Node) -> Self { + Self { + positition: 0, + edgelist, + node, + } + } +} + +impl<'a, 'b> Iterator for Explorable<'a, 'b> { + type Item = &'a Node; + + fn next(&mut self) -> Option { + let neighbours = self.edgelist.neighbours(self.node); + let next = neighbours.into_iter().nth(self.positition); + self.positition += 1; + next + } +} + +fn read_input>(filename: T) -> Result> { + let reader = BufReader::new(File::open(filename)?); + + reader.lines().map( + |v| { + let s = v?; + let (left, right) = s.split_once('-') + .ok_or_else(|| anyhow!("Unable to parse: {}", s))?; + Ok((String::from(left), String::from(right))) + } + ).collect() +} + +fn part1(cave: Cave) -> Result { + let paths = cave.walk_all(State::Unexplored)?; + Ok(paths) +} + +fn part2(cave: Cave) -> Result { + let paths = cave.walk_all(State::Explorable)?; + Ok(paths) +} + +fn main() -> Result<()> { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?; + let input = read_input(filename).context("Could not read input")?; + let nodelist = NodeList::new(input.clone())?; + let edgelist = EdgeList::new(input, &nodelist)?; + let cave = Cave::new(&nodelist, edgelist)?; + if do_part_1 { + let solution = part1(cave.clone()).context("No solution for part 1")?; + println!("Part1, solution found to be: {}", solution); + } + if do_part_2 { + let solution = part2(cave).context("No solution for part 2")?; + println!("Part2, solution found to be: {}", solution); + } + Ok(()) +} -- cgit v1.2.3