diff options
author | alyx <alyx@aleteoryx.me> | 2023-12-08 01:27:18 -0500 |
---|---|---|
committer | alyx <alyx@aleteoryx.me> | 2023-12-08 01:27:18 -0500 |
commit | d593cd2cd5880ef5031759aa442fe792dec0034b (patch) | |
tree | f1a6ea37b6d2eb75ef13769c67feb6ee1e2d2294 /2023/rs/code/eight/src/main.rs | |
parent | 0258550017750d9fb15f5e28518c8711b6c0f580 (diff) | |
download | adventofcode-d593cd2cd5880ef5031759aa442fe792dec0034b.tar.gz adventofcode-d593cd2cd5880ef5031759aa442fe792dec0034b.tar.bz2 adventofcode-d593cd2cd5880ef5031759aa442fe792dec0034b.zip |
2023.8[0]
Diffstat (limited to '2023/rs/code/eight/src/main.rs')
-rw-r--r-- | 2023/rs/code/eight/src/main.rs | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/2023/rs/code/eight/src/main.rs b/2023/rs/code/eight/src/main.rs new file mode 100644 index 0000000..9e58f07 --- /dev/null +++ b/2023/rs/code/eight/src/main.rs @@ -0,0 +1,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; + } + } +} |