blob: 504a97a655c583cdfdba9514adfca9dc0f05033c (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
use std::fs;
use std::path::Path;
use std::collections::HashMap;
/* AOC21 Day 12: https://adventofcode.com/2021/day/12 */
fn main() {
let input = Path::new("resources").join("input.txt");
let content = fs::read_to_string(input).expect("Unable to read input file");
let mut adj = HashMap::<&str,Vec<&str>>::new();
content.lines()
.map(|l| l.split_once('-').expect("Malformed input"))
.for_each(|(from,to)| {
adj.entry(from).or_default().push(to);
adj.entry(to).or_default().push(from);
});
println!("Ex1: the result is {}", genpath(&mut vec!["start"], &adj));
println!("Ex2: the result is {}", genpath_rep(&mut vec!["start"], &adj));
}
fn genpath<'a>(path: &mut Vec<&'a str>, adj: &HashMap<&str,Vec<&'a str>>) -> u32 {
let last = path.last().unwrap();
if *last == "end" { 1 } else {
let mut paths = 0;
if let Some(vec) = adj.get(last) {
let next: Vec<&str> = vec.iter().filter(|n| n.chars().all(|c| c.is_uppercase()) || !path.contains(&n)).cloned().collect();
for n in next {
path.push(n);
paths += genpath(path, adj);
path.pop();
}
}
paths
}
}
fn genpath_rep<'a>(path: &mut Vec<&'a str>, adj: &HashMap<&str,Vec<&'a str>>) -> u32 {
let last = path.last().unwrap();
if *last == "end" { 1 } else {
let mut paths = 0;
if let Some(vec) = adj.get(last) {
for n in vec.iter().filter(|&n| *n != "start") {
if n.chars().all(|c| c.is_lowercase()) && path.contains(n) {
path.push(n);
paths += genpath(path, adj);
} else {
path.push(n);
paths += genpath_rep(path, adj);
}
path.pop();
}
}
paths
}
}
|
