I can prove the opposite for you. The assumption that Gobbel2000 describes is wrong in general. For example, take

L

A -> B, X
B -> C, X
C -> Z, X
Z -> C, X
X -> X, X

the first Z is reached after 3 steps, but then every cycle only takes 2 steps.

The matches are still at consistent intervals, but you can easily find a counterexample for that as well:

L

A -> 1Z, X
1Z -> 2Z, X
2Z -> A, X
X -> X, X

now the intervals will be 2, 1, 2, 1, …

However, it is easy to prove that there will be a loop of finite length, and that the intervals will behave somewhat nicely:

Identify a “position” by a node you are at, and your current index in the LRL instruction sequence. If you ever repeat a position P, you will repeat the exact path away from the position you took the last time, and the last time you later reached P, so you will keep reaching P again and again. There are finitely many positions, so you can’t keep not repeating any forever, you will run out.

Walking in circles along this loop you eventually find yourself in, the intervals between Zs you see will definitely be a repeating sequence (as you will keep seeing not just same-length intervals, but in fact the exact same paths between Zs).

So in total, you will see some finite list of prefix-intervals, and then a repeating cycle of loop-intervals. I have no idea if this can be exploited to compute the answer efficiently, but see my solution-comment for something that only assumes that only one Z will be encountered each cycle.

This assumption doesn’t hold in general, however you can construct an efficient algorithm, even if it doesn’t hold.

First, let’s show that a cycle always exists. Let I be the size of the instruction string, and N be the number of nodes. Since the number of states for each ghost is at most I*N, after a finite number of steps, the ghost will go into one of the previous states and cycle forever. Let’s say that the cycle length is c, and after a+c steps the ghost has entered the same state it was after a steps.

Let’s assume[^1] that during the first a+c steps the ghost has only once encounter an end state (a node ending with ‘Z’), specifically after e states. If e >= a, this means that the ghost will encounter the end state also after e + c and e + 2c and so on, or for every number of steps s > e such that s = e (mod c). The assumption you formulated means e = 0 (mod c), or e = c.

Now, consider the K ghosts that are travelling simultaneously. If after n steps all ghosts have reached the end state, this means that n = e_i (mod c_i) for all ghosts i (1 <= i <= K). According to the Chinese remainder theorem, there is a solution if and only if e_1 = e_2 = ... = e_K (mod gcd(c_1, c_2, ... c_K)). If the assumption you formulated holds, then e_i = 0 (mod c_i), so lcm(c_1, ... c_K) works as a solution. If it doesn’t, you can still find n, but it will be a bit more tricky (which is probably why the authors of the challenge made e = c always).

[^1] – this is another assumption you’ve implicitly made, and that happens to hold for all the inputs. However, if this assumption doesn’t hold, we can check all possible combination of end state positions.

I crafted a simple counter-example (single letters for brevity). The way the sequence goes totally depends on the instructions, and we don’t have any guarantees on that. It could be anything. Of course, looking at the input data we could find what the instructions are, but the assumption doesn’t hold in general.

A = (B, X)
B = (C, X)
C = (X, Z)
Z = (A, C)
X = (X, X)

L L R L L L R R R -> A B C Z A B C Z C Z
L L R R R L L L R -> A B C Z C Z A B C Z

Here the distance of Z cycling back into itself could be 2 or 4, depending on what the instruction string is doing.