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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
use std::{cell::RefCell, collections::HashMap, io, rc::Rc};
#[derive(PartialEq, Eq, Hash, Debug)]
struct Node {
device: String,
dac: bool,
fft: bool,
}
fn main() {
let adj = io::stdin()
.lines()
.flatten()
.map(|line| {
let (k, v) = line.split_once(": ").unwrap();
(
String::from(k),
String::from(v)
.split_whitespace()
.map(String::from)
.collect(),
)
})
.collect::<HashMap<String, Vec<String>>>();
let cache = Rc::new(RefCell::new(HashMap::new()));
let silver = paths_from(
Node {
device: String::from("you"),
dac: true,
fft: true,
},
&adj,
Rc::clone(&cache),
);
let gold = paths_from(
Node {
device: String::from("svr"),
dac: false,
fft: false,
},
&adj,
Rc::clone(&cache),
);
println!("silver: {silver}");
println!("gold: {gold}");
}
fn paths_from(
curr: Node,
adj: &HashMap<String, Vec<String>>,
cache: Rc<RefCell<HashMap<Node, usize>>>,
) -> usize {
if curr.device == "out" {
if curr.dac && curr.fft {
return 1;
}
return 0;
}
let Some(&v) = cache.borrow().get(&curr) else {
let paths = adj
.get(&curr.device)
.unwrap()
.iter()
.map(|n| {
paths_from(
Node {
device: n.clone(),
dac: curr.dac || curr.device == "dac",
fft: curr.fft || curr.device == "fft",
},
adj,
Rc::clone(&cache),
)
})
.sum();
cache.borrow_mut().insert(curr, paths);
return paths;
};
return v;
}
|
