I had 6 parallel paths, and for all of them, the goal node was found at the point where the directions string repeated. So I actually only had to search each of the paths for the point where I was on the goal position and the first direction. This worked on the input data, but not the example. See the assert in the code, and note that the statement println!("Found non-repeat at {node} step {step} (num dirs {num_directions})"); is never executed.
At the end there's also the first attempt of brute-forcing the solution which seems like it would have taken nearly forever.
use std::collections::HashMap;
use regex::Regex;
use crate::input::Source;
pub fn execute(source: Source) -> impl std::fmt::Debug {
let lines = source.lines();
let ([directions], [empty, nodes @ ..]) = lines.split_at(1) else {
panic!("Wrong format");
};
assert!(empty.is_empty());
let node_re = Regex::new(r"(...) = \((...), (...)\)").unwrap();
let nodes: HashMap = nodes
.iter()
.map(|line| {
let caps = node_re.captures(line).unwrap();
let name = caps[1].to_string();
let left = caps[2].to_string();
let right = caps[3].to_string();
(name, (left, right))
})
.collect();
let start_nodes: Vec = nodes.keys().filter(|n| n.ends_with('A')).cloned().collect();
let repeat_lengths: Vec = start_nodes
.iter()
.map(|node| {
let (repeat_length, goal_steps) = find_repeats(node, directions, &nodes);
assert!(goal_steps.is_empty()); // not a given, but that's what the input looks like
dbg!(node, repeat_length, goal_steps);
repeat_length
})
.collect();
repeat_lengths.iter().cloned().reduce(num::integer::lcm)
}
/// (repeat length, steps to goal node within repeat)
fn find_repeats(
starting_node: &str,
directions: &str,
nodes: &HashMap,
) -> (usize, Vec) {
let mut node = starting_node.to_string();
let num_directions = directions.chars().count();
let mut goals = Vec::new();
for (step, dir) in directions.chars().cycle().enumerate() {
if node.ends_with('Z') {
if step % num_directions == 0 {
println!("Found repeat at {node} step {step} (num dirs {num_directions})");
return (step, goals);
}
println!("Found non-repeat at {node} step {step} (num dirs {num_directions})");
goals.push(step);
}
let (left, right) = &nodes[&node];
node = match dir {
'L' => left.clone(),
'R' => right.clone(),
other => panic!("Unknown dir {other}"),
}
}
unreachable!()
}
// too slow
#[allow(dead_code)]
fn find_parallel(
start_nodes: &[String],
directions: &str,
nodes: &HashMap,
) -> usize {
let mut current_nodes = start_nodes.to_vec();
for (step, dir) in directions.chars().cycle().enumerate() {
if current_nodes.iter().all(|n| n.ends_with('Z')) {
return step;
}
for node in current_nodes.iter_mut() {
let (left, right) = nodes[node].clone();
*node = match dir {
'L' => left,
'R' => right,
other => panic!("Unknown dir {other}"),
}
}
}
unreachable!()
}