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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#![allow(dead_code)]
#![allow(unused_variables)]
use advent_of_code::prelude::*;
#[derive(Clone, Copy)]
enum Direction {
Left,
Right,
}
pub struct Network {
directions: Vec<Direction>,
graph: HashMap<String, (String, String)>,
}
fn gcd(mut a: usize, mut b: usize) -> usize {
loop {
let r = a % b;
if r == 0 {
return b;
}
a = b;
b = r;
}
}
pub fn parse(fh: File) -> Result<Network> {
let mut lines = parse::raw_lines(fh);
let directions = lines.next().unwrap();
lines.next().unwrap();
Ok(Network {
directions: directions
.chars()
.map(|c| {
if c == 'L' {
Direction::Left
} else {
Direction::Right
}
})
.collect(),
graph: lines
.map(|line| {
let cap = regex_captures!(r"(\w+) = \((\w+), (\w+)\)", &line)
.unwrap();
(cap[1].to_string(), (cap[2].to_string(), cap[3].to_string()))
})
.collect(),
})
}
pub fn part1(network: Network) -> Result<i64> {
let mut vertex = "AAA".to_string();
let mut distance = 0;
while vertex != "ZZZ" {
let next = network.graph[&vertex].clone();
vertex = match network.directions[distance % network.directions.len()]
{
Direction::Left => next.0,
Direction::Right => next.1,
};
distance += 1;
}
Ok(distance.try_into().unwrap())
}
pub fn part2(network: Network) -> Result<i64> {
let vertices: Vec<String> = network
.graph
.keys()
.filter(|v| v.ends_with('A'))
.cloned()
.collect();
let mut cycles: HashMap<_, HashMap<(String, usize), Vec<usize>>> =
HashMap::new();
for start_vertex in vertices {
let mut seen = HashMap::new();
let mut vertex = start_vertex.clone();
let mut distance = 0;
loop {
if vertex.ends_with('Z') {
let entry: &mut Vec<_> = seen
.entry((
vertex.clone(),
distance % network.directions.len(),
))
.or_default();
if entry.len() >= 2 {
break;
}
entry.push(distance);
}
let next = network.graph[&vertex].clone();
vertex = match network.directions
[distance % network.directions.len()]
{
Direction::Left => next.0,
Direction::Right => next.1,
};
distance += 1;
}
cycles.insert(
start_vertex,
seen.into_iter()
.filter(|(_, distances)| distances.len() == 2)
.collect(),
);
}
// this is pretty dumb but it looks like we're supposed to notice that
// the input data is very specifically shaped to make this easy
let cycles: Vec<_> = cycles
.values()
.map(|cycle| cycle.values().next().unwrap()[0])
.collect();
let gcd = cycles.iter().copied().reduce(gcd).unwrap();
Ok(i64::try_from(
gcd * cycles.iter().copied().map(|n| n / gcd).product::<usize>(),
)
.unwrap())
}
#[test]
fn test() {
assert_eq!(
part1(parse(parse::data(2023, 8).unwrap()).unwrap()).unwrap(),
11309
);
assert_eq!(
part2(parse(parse::data(2023, 8).unwrap()).unwrap()).unwrap(),
0
);
}
|
