90 lines
2.3 KiB
Rust
90 lines
2.3 KiB
Rust
use std::collections::HashMap;
|
|
use std::collections::HashSet;
|
|
use std::error::Error;
|
|
use std::fs::File;
|
|
use std::io::{self, BufRead};
|
|
use std::vec::Vec;
|
|
|
|
fn enumerate_ways(
|
|
start: &str,
|
|
end: &str,
|
|
vertices: &HashMap<String, HashSet<String>>,
|
|
mut path: Vec<String>,
|
|
mut allow_twice: bool,
|
|
) -> u64 {
|
|
if start == end {
|
|
return 1;
|
|
}
|
|
|
|
if start.chars().all(|c| c.is_lowercase()) {
|
|
if path.iter().filter(|n| n == &&start).count() > 0 {
|
|
if !allow_twice {
|
|
return 0;
|
|
} else {
|
|
allow_twice = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
path.push(start.to_string());
|
|
|
|
let mut ways = 0;
|
|
|
|
for neighbor in vertices[start].iter() {
|
|
if neighbor != "start" {
|
|
ways += enumerate_ways(neighbor, end, vertices, path.clone(), allow_twice);
|
|
}
|
|
}
|
|
|
|
ways
|
|
}
|
|
|
|
fn main() -> Result<(), Box<dyn Error>> {
|
|
let file = File::open("inputs/day12.txt")?;
|
|
let links: Vec<(String, String)> = io::BufReader::new(file)
|
|
.lines()
|
|
.map(|l| l.unwrap())
|
|
.map(|l| {
|
|
let mut ends = l.split('-');
|
|
(
|
|
ends.next().unwrap().to_string(),
|
|
ends.next().unwrap().to_string(),
|
|
)
|
|
})
|
|
.collect();
|
|
|
|
let mut vertices: HashMap<String, HashSet<String>> = HashMap::new();
|
|
for link in links.iter() {
|
|
if vertices.contains_key(&link.0) {
|
|
let mut set = vertices[&link.0].clone();
|
|
set.insert(link.1.clone());
|
|
vertices.insert(link.0.clone(), set);
|
|
} else {
|
|
let mut set: HashSet<String> = HashSet::new();
|
|
set.insert(link.1.clone());
|
|
vertices.insert(link.0.clone(), set);
|
|
}
|
|
|
|
if vertices.contains_key(&link.1) {
|
|
let mut set = vertices[&link.1].clone();
|
|
set.insert(link.0.clone());
|
|
vertices.insert(link.1.clone(), set);
|
|
} else {
|
|
let mut set: HashSet<String> = HashSet::new();
|
|
set.insert(link.0.clone());
|
|
vertices.insert(link.1.clone(), set);
|
|
}
|
|
}
|
|
|
|
let ways1 = enumerate_ways("start", "end", &vertices, Vec::new(), false);
|
|
|
|
println!("Answer1: {}", ways1);
|
|
println!("");
|
|
|
|
let ways2 = enumerate_ways("start", "end", &vertices, Vec::new(), true);
|
|
|
|
println!("Answer2: {}", ways2);
|
|
|
|
Ok(())
|
|
}
|