stream processing

approach

a hand-written scanner walks the stream with a two-state machine: NORMAL and GARBAGE. in normal mode { pushes a new list onto a stack and } pops it into its parent, so the groups come out as nested lists. < switches to garbage mode, where ! skips the next character, > switches back, and anything else bumps a garbage counter.

part 1 scores the nested lists recursively, each group worth its depth. part 2 is the garbage counter collected during the same scan.

the trick

a stack of lists turns the braces straight into a tree, and the cancelled characters are just i += 2.

if mode == NORMAL and c == "{":
    res.append([])
    i += 1
elif mode == NORMAL and c == "}":
    l = res.pop()
    res[-1].append(l)
    i += 1
elif mode == NORMAL and c == "<":
    mode = GARBAGE
    i += 1
elif mode == GARBAGE and c == "!":
    i += 2