Canonicalize execution traces
A test harness replays a concurrent program many times and records each run as a log. A log entry is a thread name, a colon, then an event name, and both names are non empty and hold only lowercase letters and digits. Entries appear in the order the harness observed them, so two replays of one program differ only in how the threads were interleaved. Two runs are the same execution when every thread performed the same events in the same order in both, whatever order the threads took their turns in. A thread that acts in one run and not in the other makes the two runs different. Given the runs, return how many distinct executions were observed.
distinct_executions(runs: list[list[str]]) → int[[["t1:a","t2:x","t1:b"],["t1:a","t1:b","t2:x"]]]out1[[["t1:b","t1:a"],["t1:a","t1:b"]]]out2[[["t1:x","t2:y"],["t1:x","t1:y"]]]out2State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[["t1:a","t2:x","t1:b"],["t1:a","t1:b","t2:x"]]]1not run yetsample[[["t1:b","t1:a"],["t1:a","t1:b"]]]2not run yetsample[[["t1:x","t2:y"],["t1:x","t1:y"]]]2not run yetsample