Performance issue with Advent of Code Day 8 solution

Advent of code, 2023, day 8: Day 8 - Advent of Code 2023
I tried to solve the challenge using a graph, each node containing a slice of 3 chars and left and right indices of a vector. The code gathers all nodes starting with 'A' and follows the instructions found from the input file. On each iteration, the nodes are checked whether all end on 'Z', thus ending the loop and printing the amount of iterations, aka steps.

The issue is this solution takes too much time in comparison to a JS code I found online which does it practically instantly. Where could the performance bottleneck be?

I've provided snippets of the solution, so to focus on the main part rather the setup and mapping of nodes. If needed, I can share the whole project.

#[derive(Debug, Clone, Copy, Default)]
struct Node<'a> {
    value: &'a str, // 3 char slice
    left: usize, // index in the array
    right: usize, // index in the array
}

fn main()...

// Part 2
    let mut steps: u64 = 0;
    let default = Node::default();
    let mut buffer = [&default; 6]; // 6 is specific to input.txt; there are 6 nodes starting with 'A'
    let nodes = graph.iter().filter(|n| n.value.ends_with('A')).collect::<Vec<_>>();
    buffer[..nodes.len()].copy_from_slice(&nodes[..]);
    
    let instructions = content.lines().next().unwrap();

    for instruction in instructions.chars().cycle() {
        let mut ok = true;
        for i in 0..nodes.len() {
            match instruction {
                'L' => buffer[i] = &graph[buffer[i].left],
                'R' => buffer[i] = &graph[buffer[i].right],
                _ => panic!("Lol")
            }
            ok = ok && buffer[i].value.ends_with('Z');
        }
        steps += 1;
        if ok {
            println!("{buffer:?}");
            break;
        }
    }

Are you sure the JS code you mention doesn't implement some smart shortcut...?

My naive implementation that is a bit hacky / not optimized in any way is approx. this (times for laptop with intel 8250u):

parse input: () (190.2µs)
part 1: <censored/> (479µs)
part 2: <censored/> (2.9606ms)

There is no genius or extra careful performance handling, just one "logical trick" that your code excerpt above seems not to include...

Is it related to least common multiple & greatest common factor?

right, using only that is not 100% "correct"/clean in a math sense for this problem, but it works and gives correct results thanks to input being of specific pattern/format.
(i used it too)

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.