Protocol state transitions

Write codeEasy15 min

Your task

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.

Examples

first_illegal_transition(allowed: list[list[str]], observed: list[str]) -> int
Example 1
Inputfirst_illegal_transition([["closed", "syn_sent"], ["syn_sent", "established"], ["established", "fin_wait"], ["fin_wait", "closed"]], ["closed", "syn_sent", "established", "fin_wait", "closed"])
Output-1
Example 2
Inputfirst_illegal_transition([["closed", "syn_sent"], ["syn_sent", "established"], ["established", "fin_wait"], ["fin_wait", "closed"]], ["closed", "established"])
Output1
Example 3
Inputfirst_illegal_transition([["idle", "idle"], ["idle", "busy"]], ["idle", "idle", "busy", "idle"])
Output3