Protocol state transitions
A protocol analyzer replays the state trace a connection recorded and checks it against the protocol's transition table. Each entry of allowed is a two element list holding a from state and a to state, naming one legal move. observed lists the states the connection passed through in order, beginning with the state it opened in. The move from observed[i-1] to observed[i] is legal only when that exact pair appears in allowed, so a state that repeats itself is legal only when the table lists that self move. State names use letters, digits and underscores, and are compared exactly, upper and lower case included. Return the index in observed of the first state that was entered by a move the table does not list, or -1 when every move is legal. The opening state is never an error by itself, and a trace of fewer than two states has no move to check.
first_illegal_transition(allowed: list[list[str]], observed: list[str]) → int[[["closed","syn_sent"],["syn_sent","established"],["established","fin_wait"],["fin_wait","closed"]],["closed","syn_sent","established","fin_wait","closed"]]out-1[[["closed","syn_sent"],["syn_sent","established"],["established","fin_wait"],["fin_wait","closed"]],["closed","established"]]out1[[["idle","idle"],["idle","busy"]],["idle","idle","busy","idle"]]out3State 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.
[[["closed","syn_sent"],["syn_sent","established"],["established","fin_wait"],["fin_wait","closed"]],["closed","syn_sent","established","fin_wait","closed"]]-1not run yetsample[[["closed","syn_sent"],["syn_sent","established"],["established","fin_wait"],["fin_wait","closed"]],["closed","established"]]1not run yetsample[[["idle","idle"],["idle","busy"]],["idle","idle","busy","idle"]]3not run yetsample