summaryrefslogtreecommitdiffstats
path: root/2023/rs/code/eight
diff options
context:
space:
mode:
authoralyx <alyx@aleteoryx.me>2023-12-09 15:13:58 -0500
committeralyx <alyx@aleteoryx.me>2023-12-09 15:13:58 -0500
commitda56199bf47557114a167877301d1ea28010448d (patch)
treea0025f0bc2461db370e8979e085a7804dab544cd /2023/rs/code/eight
parentd593cd2cd5880ef5031759aa442fe792dec0034b (diff)
downloadadventofcode-master.tar.gz
adventofcode-master.tar.bz2
adventofcode-master.zip
2023.8[1]HEADmaster
Diffstat (limited to '2023/rs/code/eight')
-rw-r--r--2023/rs/code/eight/src/main.rs72
1 files changed, 30 insertions, 42 deletions
diff --git a/2023/rs/code/eight/src/main.rs b/2023/rs/code/eight/src/main.rs
index 9e58f07..5ca6420 100644
--- a/2023/rs/code/eight/src/main.rs
+++ b/2023/rs/code/eight/src/main.rs
@@ -1,11 +1,10 @@
use std::collections::BTreeMap;
+use std::iter::Iterator;
static INPUT: &str = include_str!("input.txt");
fn gcd(mut a: u128, mut b: u128) -> u128 {
- while b > 0 {
- (a, b) = (b, a % b)
- }
+ while b > 0 { (a, b) = (b, a % b) }
a
}
@@ -13,6 +12,17 @@ fn lcm(a: u128, b: u128) -> u128 {
a * b / gcd(a, b)
}
+fn steps<'a, I: Iterator<Item = bool> + Clone>(mut last: &'a str, instructions: &I, triples: &BTreeMap<&'a str, (&'a str, &'a str)>, goal: &str) -> u128 {
+ for (n, instr) in instructions.clone().cycle().enumerate() {
+ if last.ends_with(goal) {
+ return n as u128;
+ }
+ let pair = triples[last];
+ last = if instr { pair.1 } else { pair.0 };
+ }
+ unreachable!()
+}
+
fn main() {
let (valueified_instr, valueified_triples) = {
let mut iter = INPUT.lines();
@@ -22,45 +32,23 @@ fn main() {
(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 part1 = steps("AAA", &valueified_instr, &valueified_triples, "ZZZ");
+ println!("Steps to reach `ZZZ`: {part1}");
-/*
- 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}");
+ let mut part2 = valueified_triples
+ .keys()
+ .filter(|s| s.as_bytes()[2] == b'A')
+ .cloned()
+ .map(|k| steps(k, &valueified_instr, &valueified_triples, "Z"))
+ .fold(1, lcm);
- 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;
- }
- }
+ println!("Steps to reach unanimous 'Z': {part2}");
+
+ // dude what the fuck was this.
+ // i genuinely don't get why this was right.
+ // i also don't get why my earlier, near-identical impl, was wrong.
+ // i've seen other solutions that use the phase of the actual loop through the map and i feel like that should come in here
+ // this shouldn't be right, and if it is, i don't know why my earlier, logically identical, implementation was broken.
+ // ...
+ // fucking hell
}