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!()
}
Thanks for the answer! What you're saying seems to be true, but it wasn't given in the instructions, so I guess you were supposed to figure out that this was the case. It seems this was true for everyone, so it wasn't just me that got lucky. I got confused by my assertion failing on the example, because the second path reaches the goal in three steps which is not a multiple of the instruction length (2). This never happens with the real data. The example wraps around neatly at 6 instead, so just removing the assertion makes my code work on the example too.