159 lines
3.8 KiB
Rust
159 lines
3.8 KiB
Rust
use std::collections::{HashMap, HashSet, VecDeque};
|
|
use std::fmt::Debug;
|
|
use std::fmt::Formatter;
|
|
|
|
pub fn day12() {
|
|
// 10 paths, 36
|
|
// let input = r#"
|
|
// start-A
|
|
// start-b
|
|
// A-c
|
|
// A-b
|
|
// b-d
|
|
// A-end
|
|
// b-end"#;
|
|
// 19 paths, 103
|
|
// let input = r#"
|
|
// dc-end
|
|
// HN-start
|
|
// start-kj
|
|
// dc-start
|
|
// dc-HN
|
|
// LN-dc
|
|
// HN-end
|
|
// kj-sa
|
|
// kj-HN
|
|
// kj-dc
|
|
// "#;
|
|
// 226 paths, 3059
|
|
// let input = r#"
|
|
// fs-end
|
|
// he-DX
|
|
// fs-he
|
|
// start-DX
|
|
// pj-DX
|
|
// end-zg
|
|
// zg-sl
|
|
// zg-pj
|
|
// pj-he
|
|
// RW-he
|
|
// fs-DX
|
|
// pj-RW
|
|
// zg-RW
|
|
// start-pj
|
|
// he-WI
|
|
// zg-he
|
|
// pj-fs
|
|
// start-RW
|
|
// "#;
|
|
let input = include_str!("../input/day12.txt");
|
|
|
|
let graph = parse_graph(&input);
|
|
println!("{:?}", graph);
|
|
|
|
println!("{:?}", count_paths(&graph, false));
|
|
println!("{:?}", count_paths(&graph, true));
|
|
}
|
|
|
|
fn parse_graph(input: &'static str) -> Graph {
|
|
let mut nodes = HashSet::new();
|
|
let mut connections: HashMap<Node, Vec<Node>> = HashMap::new();
|
|
for line in input.trim().lines() {
|
|
let (a, b) = line.trim().split_once("-").unwrap();
|
|
let first: Node = a.into();
|
|
let second: Node = b.into();
|
|
nodes.insert(first.clone());
|
|
nodes.insert(second.clone());
|
|
connections
|
|
.entry(first.clone())
|
|
.or_insert(vec![])
|
|
.push(second.clone());
|
|
connections.entry(second).or_insert(vec![]).push(first);
|
|
}
|
|
|
|
Graph { nodes, connections }
|
|
}
|
|
|
|
#[derive(PartialEq, Eq, Hash, Clone)]
|
|
enum Node {
|
|
Start,
|
|
End,
|
|
Small(&'static str),
|
|
Big(&'static str),
|
|
}
|
|
|
|
impl Node {
|
|
fn big(&self) -> bool {
|
|
match self {
|
|
Self::Big(_) => true,
|
|
_ => false,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Debug for Node {
|
|
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
|
|
match self {
|
|
Self::Start => write!(f, "start"),
|
|
Self::End => write!(f, "end"),
|
|
Self::Small(s) | Self::Big(s) => write!(f, "{}", s),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl From<&'static str> for Node {
|
|
fn from(s: &'static str) -> Self {
|
|
if s == "start" {
|
|
Self::Start
|
|
} else if s == "end" {
|
|
Self::End
|
|
} else if s.chars().all(|c| c.is_uppercase()) {
|
|
Self::Big(s)
|
|
} else {
|
|
Self::Small(s)
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct Graph {
|
|
nodes: HashSet<Node>,
|
|
connections: HashMap<Node, Vec<Node>>,
|
|
}
|
|
|
|
fn count_paths(g: &Graph, allow_visiting_small_twice: bool) -> usize {
|
|
let mut queue: VecDeque<(Vec<&Node>, bool)> = VecDeque::new();
|
|
queue.push_front((vec![&Node::Start], false));
|
|
let mut count = 0;
|
|
|
|
while let Some((path, mut seen_any_small_twice)) = queue.pop_front() {
|
|
let last = path.last().unwrap().clone();
|
|
|
|
if last == &Node::End {
|
|
// println!("{:?}", path);
|
|
count += 1;
|
|
continue;
|
|
}
|
|
|
|
// current is small and seen current before
|
|
if !last.big() && path.iter().rev().skip(1).any(|&n| n == last) {
|
|
// if visting small twice is always prohibited (part 1), or we're revisting the start,
|
|
// or visiting a _single_ small twice is allowed but we've already done it
|
|
if !allow_visiting_small_twice || last == &Node::Start || seen_any_small_twice {
|
|
continue;
|
|
}
|
|
// note that we've now seen a single small cave twice, so any paths descended from this
|
|
// one can't do so themselves
|
|
seen_any_small_twice = true;
|
|
}
|
|
|
|
for connected in &g.connections[last] {
|
|
let mut new_path = path.clone();
|
|
new_path.push(connected);
|
|
queue.push_back((new_path, seen_any_small_twice));
|
|
}
|
|
}
|
|
|
|
count
|
|
}
|