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
|
use std::collections::BTreeMap;
static INPUT: &str = include_str!("input.txt");
fn gcd(mut a: u128, mut b: u128) -> u128 {
while b > 0 {
(a, b) = (b, a % b)
}
a
}
fn lcm(a: u128, b: u128) -> u128 {
a * b / gcd(a, b)
}
fn main() {
let (valueified_instr, valueified_triples) = {
let mut iter = INPUT.lines();
let instr = iter.next().unwrap().bytes().map(|c| c == b'R');
iter.next().unwrap();
let triples = iter.map(|s| (&s[0..3], (&s[7..10], &s[12..15]))).collect::<BTreeMap<_, _>>();
(instr, triples)
};
let mut last = "AAA";
for (n, instr) in valueified_instr.clone().cycle().enumerate() {
if last == "ZZZ" {
println!("Steps to reach `ZZZ`: {n}");
break;
}
let pair = valueified_triples[last];
last = if instr { pair.1 } else { pair.0 };
}
/*
let mut lasts = valueified_triples.keys().filter(|s| s.as_bytes()[2] == b'A').cloned().map(|a| (a, 0u128)).collect::<Vec<_>>();
for last in &mut lasts {
for (n, instr) in valueified_instr.clone().cycle().enumerate() {
let pair = valueified_triples[last.0];
last.0 = if instr { pair.1 } else { pair.0 };
if last.0.as_bytes()[2] == b'Z' {
last.1 = n as u128;
break;
}
}
}
dbg!(&lasts);
// yes, i could optimize the maths here, but i do not feel like it.
let total = lasts.into_iter().fold(1, |a, (_, n)| lcm(n, a));
println!("Steps for all to reach `Z`: {total}");
OK there's totally a way to do this cleverly like above but I can't think of it. This method overshoots, apparently.
It assumes the period here is the time it takes to reach Z. What I really need to do is like, find the LCM of the real periods but offset such that the final LCM is n below and blah blah ugh im gonna write the brute forcer and shit and hope it's done.
*/
let mut lasts = valueified_triples.keys().filter(|s| s.as_bytes()[2] == b'A').cloned().collect::<Vec<_>>();
for (n, instr) in valueified_instr.clone().cycle().enumerate() {
for last in &mut lasts {
let pair = valueified_triples[*last];
*last = if instr { pair.1 } else { pair.0 };
}
if lasts.iter().all(|a| a.as_bytes()[2] == b'Z') {
println!("Steps for all to reach `Z`: {n}");
break;
}
}
}
|