Python

# pairwise helps picking consecutive values easier
#   [A,B,C,D] -> [AB, BC, CD]
from itertools import pairwise

# returns names and dict[str, set[str]] of allowed transitions
def parse_data(data: str):
    transition_map = {}
    lines = data.splitlines()

    for rule_str in lines[2:]:
        before, after = rule_str.split(" > ")
        transition_map[before] = set(after.split(','))

    names = lines[0].split(',')
    return names, transition_map

# checks if name is valid according to transition_map
def is_name_valid(transition_map: dict[str, set[str]], name: str) -> bool:
    for a, b in pairwise(name):
        if a not in transition_map or b not in transition_map[a]:
            return False
    return True


def part1(data: str):
    names, transition_map = parse_data(data)
    for name in names:
        if is_name_valid(transition_map, name):
            return name

# <assert snipped>

def part2(data: str):
    ans = 0
    names, transition_map = parse_data(data)
    for i, name in enumerate(names):
        if is_name_valid(transition_map, name):
            ans += i + 1
    return ans

# <assert snipped>

def part3(data: str):
    prefixes, transition_map = parse_data(data)

    # remove prefixes that are sub-prefixes of others
    #   to avoid double counting
    superset_prefixes = []
    for i, p1 in enumerate(prefixes):
        for j, p2 in enumerate(prefixes):
            if i != j and p1.startswith(p2):
                break
        else:
            # no break -> p1 is not a sub-prefix
            superset_prefixes.append(p1)

    variants = 0
    for prefix in superset_prefixes:
        if not is_name_valid(transition_map, prefix):
            continue
        
        # DFS to count all valid name extensions
        stack = [(prefix[-1], len(prefix))]
        while stack:
            prev, name_len = stack.pop()
            if name_len >= 7:
                variants += 1
            if name_len == 11:
                continue

            for next_letter in transition_map.get(prev, []):
                stack.append((next_letter, name_len + 1))
        
    return variants

# <assert snipped>