haunted wasteland

approach

the network is a dict from node to its left and right neighbours, and the instruction string is repeated with cycle. part 1 walks from AAA until it reaches ZZZ and counts the steps.

part 2 starts from every node ending in A. instead of moving them all together, find_cycle walks each one, remembering (instruction index, node) pairs, and returns the length of the loop it falls into. the answer is the lcm of those lengths. a comment notes this relies on a property of the input: each start only ever reaches one ending node.

the trick

each ghost loops on its own, so the time they all line up is the lcm of the loop lengths.

def find_cycle(graph, node, instrs):
    i = 0
    seen = {}
    for i, instr in enumerate(cycle(instrs)):
        mod = i % len(instrs)
        if (mod, node) in seen:
            return i - seen[(mod, node)]
        seen[(mod, node)] = i
        node = graph[node][instr]
        i += 1

def part2(instrs, graph):
    nodes = [k for k in graph if k[-1] == "A"]
    return lcm(*(find_cycle(graph, node, instrs) for node in nodes))