import re
from collections import defaultdict, Counter, deque
from functools import cache

Chemical = tuple  # [int, ...]

def part1(reactions: dict[int, set[Chemical]], target: Chemical) -> int:
    outputs: set[Chemical] = set()
    counts: Counter[int] = Counter(target)
    for chemical, results in reactions.items():
        for result in results:
            for i in range(counts[chemical]):
                output: list[int] = list()
                n: int = 0
                for c in target:
                    if c == chemical:
                        if n == i:
                            output.extend(result)
                        else:
                            output.append(c)
                        n += 1
                    else:
                        output.append(c)
                outputs.add(tuple(output))
    return len(outputs)

# def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int:
#     unreactions: dict[Chemical, Chemical] = dict()
#     for chemical, results in reactions.items():
#         for result in results:
#             unreactions[result] = chemical
#     @cache
#     def path_len(c: Chemical) -> int:
#         if c == (0,):
#             print('found e')
#             return 0
#         depth = float('inf')
#         for search, replace in unreactions.items():
#             for i in range(len(c)):
#                 for j, comp in enumerate(search):
#                     if i + j >= len(c):
#                         break
#                     if c[i + j] != comp:
#                         break
#                 else:
#                     new = c[:i] + (replace,) + c[i + len(search):]
#                     depth = min(depth, path_len(new))
#         if depth == float('inf'):
#             return depth
#         return depth + 1
#     l = path_len(target)
#     print(path_len.cache_info())
#     return l

# def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int:
#     unreactions: dict[Chemical, Chemical] = dict()
#     for chemical, results in reactions.items():
#         for result in results:
#             unreactions[result] = chemical
#     queue: deque[tuple[Chemical, int]] = deque([(target, 0)])
#     while queue:
#         c, depth = queue.popleft()
#         if c == (0,):
#             return depth
#         for search, replace in unreactions.items():
#             for i in range(len(c) - len(search) + 1):
#                 for j, comp in enumerate(search):
#                     if c[i + j] != comp:
#                         break
#                 else:
#                     new = c[:i] + (replace,) + c[i + len(search):]
#                     print(f'{c} -> {new}')
#                     queue.append((new, depth + 1))
#         #print(queue)

def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int:
    unreactions: dict[Chemical, Chemical] = dict()
    for chemical, results in reactions.items():
        for result in results:
            unreactions[result] = chemical
    def path_len(c: Chemical) -> int:
        if c == (0,):
            return 0
        for search, replace in unreactions.items():
            for i in range(len(c)):
                for j, comp in enumerate(search):
                    if i + j >= len(c):
                        break
                    if c[i + j] != comp:
                        break
                else:
                    new = c[:i] + (replace,) + c[i + len(search):]
                    l = path_len(new)
                    if l is not None:
                        return l + 1
        return None
    return path_len(target)

if __name__ == '__main__':
    chem_id: dict[str, int] = dict(e=0)
    next_chem_id: int = 1
    reactions: defaultdict[int, set[Chemical]] = defaultdict(set)
    chempattern: re.Pattern = re.compile(r'e|[A-Z][a-z]?')

    def add_chem(chem: str) -> int:
        global next_chem_id
        if chem not in chem_id:
            chem_id[chem] = next_chem_id
            next_chem_id += 1
        return chem_id[chem]
    with open('input_reddit') as f:
        for line in f:
            if line == '\n':
                break
            chem, expansion = line.strip().split(' => ')
            reactions[add_chem(chem)].add(tuple(add_chem(c) for c in chempattern.findall(expansion)))

        target = tuple(add_chem(c)
                       for c in chempattern.findall(next(f).strip()))
    test_reactions: dict[int, set[Chemical]] = {
        0: set([(1,), (2,)]),
        1: set([(1, 2), (2, 1)]),
        2: set([(1, 1)]),
        # 0: set([(0, 1), (1, 0)]),
        # 1: set([(0, 0)]),
    }
    test_target: Chemical = (1, 2, 1, 2, 1, 2)
    # test_target: Chemical = (0, 1, 0)
    print(part1(reactions, target))
    print(part2(reactions, target))