Automatons, or Finite State Machines (FSM), are extremely useful to programmers when it comes to software design. You will be given a simplistic version of an FSM to code for a basic TCP session.

The outcome of this exercise will be to return the correct state of the TCP FSM based on the array of events given.

---------------------------------

The input array of events will consist of one or more of the following strings:

```
APP_PASSIVE_OPEN, APP_ACTIVE_OPEN, APP_SEND, APP_CLOSE, APP_TIMEOUT, RCV_SYN, RCV_ACK, RCV_SYN_ACK, RCV_FIN, RCV_FIN_ACK
```

---------------------------------

The states are as follows and should be returned in all capital letters as shown:

```
CLOSED, LISTEN, SYN_SENT, SYN_RCVD, ESTABLISHED, CLOSE_WAIT, LAST_ACK, FIN_WAIT_1, FIN_WAIT_2, CLOSING, TIME_WAIT
```

---------------------------------

The input will be an array of events. Your job is to traverse the FSM as determined by the events, and return the proper state as a string, all caps, as shown above.

If an event is not applicable to the current state, your code will return `"ERROR"`.

### Action of each event upon each state:
(the format is `INITIAL_STATE: EVENT -> NEW_STATE`)

```
CLOSED: APP_PASSIVE_OPEN -> LISTEN
CLOSED: APP_ACTIVE_OPEN  -> SYN_SENT
LISTEN: RCV_SYN          -> SYN_RCVD
LISTEN: APP_SEND         -> SYN_SENT
LISTEN: APP_CLOSE        -> CLOSED
SYN_RCVD: APP_CLOSE      -> FIN_WAIT_1
SYN_RCVD: RCV_ACK        -> ESTABLISHED
SYN_SENT: RCV_SYN        -> SYN_RCVD
SYN_SENT: RCV_SYN_ACK    -> ESTABLISHED
SYN_SENT: APP_CLOSE      -> CLOSED
ESTABLISHED: APP_CLOSE   -> FIN_WAIT_1
ESTABLISHED: RCV_FIN     -> CLOSE_WAIT
FIN_WAIT_1: RCV_FIN      -> CLOSING
FIN_WAIT_1: RCV_FIN_ACK  -> TIME_WAIT
FIN_WAIT_1: RCV_ACK      -> FIN_WAIT_2
CLOSING: RCV_ACK         -> TIME_WAIT
FIN_WAIT_2: RCV_FIN      -> TIME_WAIT
TIME_WAIT: APP_TIMEOUT   -> CLOSED
CLOSE_WAIT: APP_CLOSE    -> LAST_ACK
LAST_ACK: RCV_ACK        -> CLOSED
```

!["EFSM TCP" ](http://theangelfallseries.com/img/EFSM_TCP.png)

## Examples

```
["APP_PASSIVE_OPEN", "APP_SEND", "RCV_SYN_ACK"] =>  "ESTABLISHED"

["APP_ACTIVE_OPEN"] =>  "SYN_SENT"

["APP_ACTIVE_OPEN", "RCV_SYN_ACK", "APP_CLOSE", "RCV_FIN_ACK", "RCV_ACK"] =>  "ERROR"
```

 

This kata is similar to [Design a Simple Automaton (Finite State Machine)](https://www.codewars.com/kata/design-a-simple-automaton-finite-state-machine), and you may wish to try that kata before tackling this one.

See wikipedia page [Transmission Control Protocol]( http://en.wikipedia.org/wiki/Transmission_Control_Protocol)
for further details.

See http://www.medianet.kent.edu/techreports/TR2005-07-22-tcp-EFSM.pdf page 4, for the FSM diagram used for this kata.

Difficulty: interview

Starter code:

def traverse_TCP_states(events):
	

Solutions:
STATE_TO_COMMANDS = {
  'CLOSED': {
    'APP_PASSIVE_OPEN': 'LISTEN',
    'APP_ACTIVE_OPEN': 'SYN_SENT'
  },
  'LISTEN': {
    'RCV_SYN': 'SYN_RCVD',
    'APP_SEND': 'SYN_SENT',
    'APP_CLOSE': 'CLOSED'
  },
  'SYN_RCVD': {
    'APP_CLOSE': 'FIN_WAIT_1',
    'RCV_ACK': 'ESTABLISHED'
  },
  'SYN_SENT': {
    'RCV_SYN': 'SYN_RCVD',
    'RCV_SYN_ACK': 'ESTABLISHED',
    'APP_CLOSE': 'CLOSED'
  },
  'ESTABLISHED': {
    'APP_CLOSE': 'FIN_WAIT_1',
    'RCV_FIN': 'CLOSE_WAIT'
  },
  'FIN_WAIT_1': {
    'RCV_FIN': 'CLOSING',
    'RCV_FIN_ACK': 'TIME_WAIT',
    'RCV_ACK': 'FIN_WAIT_2'
  },
  'CLOSING': {
    'RCV_ACK': 'TIME_WAIT'
  },
  'FIN_WAIT_2': {
    'RCV_FIN': 'TIME_WAIT'
  },
  'TIME_WAIT': {
    'APP_TIMEOUT': 'CLOSED'
  },
  'CLOSE_WAIT': {
    'APP_CLOSE': 'LAST_ACK'
  },
  'LAST_ACK': {
    'RCV_ACK': 'CLOSED'
  }
}


def traverse_TCP_states(events):
  state = "CLOSED"  # initial state, always
  for event in events:
    if event not in STATE_TO_COMMANDS[state]:
      return 'ERROR'
    state = STATE_TO_COMMANDS[state][event]
  return state

import re

FSM_STR = """
CLOSED: APP_PASSIVE_OPEN -> LISTEN
CLOSED: APP_ACTIVE_OPEN  -> SYN_SENT
LISTEN: RCV_SYN          -> SYN_RCVD
LISTEN: APP_SEND         -> SYN_SENT
LISTEN: APP_CLOSE        -> CLOSED
SYN_RCVD: APP_CLOSE      -> FIN_WAIT_1
SYN_RCVD: RCV_ACK        -> ESTABLISHED
SYN_SENT: RCV_SYN        -> SYN_RCVD
SYN_SENT: RCV_SYN_ACK    -> ESTABLISHED
SYN_SENT: APP_CLOSE      -> CLOSED
ESTABLISHED: APP_CLOSE   -> FIN_WAIT_1
ESTABLISHED: RCV_FIN     -> CLOSE_WAIT
FIN_WAIT_1: RCV_FIN      -> CLOSING
FIN_WAIT_1: RCV_FIN_ACK  -> TIME_WAIT
FIN_WAIT_1: RCV_ACK      -> FIN_WAIT_2
CLOSING: RCV_ACK         -> TIME_WAIT
FIN_WAIT_2: RCV_FIN      -> TIME_WAIT
TIME_WAIT: APP_TIMEOUT   -> CLOSED
CLOSE_WAIT: APP_CLOSE    -> LAST_ACK
LAST_ACK: RCV_ACK        -> CLOSED
""".strip()

FSM = {(m.group(1), m.group(2)) : m.group(3) for m in (re.fullmatch('(\w+):\s+(\w+)\s+->\s+(\w+)', a) for a in FSM_STR.split('\n'))}

def traverse_TCP_states(events):
    state = "CLOSED"  # initial state, always
    for e in events:
        state = FSM.get((state, e), 'ERROR')
    return state


d = {"CLOSED": {"APP_PASSIVE_OPEN": "LISTEN",
                "APP_ACTIVE_OPEN": "SYN_SENT"},
     "LISTEN": {"RCV_SYN": "SYN_RCVD",
                "APP_SEND": "SYN_SENT",
                "APP_CLOSE": "CLOSED"},
     "SYN_RCVD": {"APP_CLOSE": "FIN_WAIT_1",
                  "RCV_ACK": "ESTABLISHED"},
     "SYN_SENT": {"RCV_SYN": "SYN_RCVD",
                  "RCV_SYN_ACK": "ESTABLISHED",
                  "APP_CLOSE": "CLOSED"},
     "ESTABLISHED": {"APP_CLOSE": "FIN_WAIT_1",
                     "RCV_FIN": "CLOSE_WAIT"},
     "FIN_WAIT_1": {"RCV_FIN": "CLOSING",
                    "RCV_FIN_ACK": "TIME_WAIT",
                    "RCV_ACK": "FIN_WAIT_2"},
     "CLOSING": {"RCV_ACK": "TIME_WAIT"},
     "FIN_WAIT_2": {"RCV_FIN": "TIME_WAIT"},
     "TIME_WAIT": {"APP_TIMEOUT": "CLOSED"},
     "CLOSE_WAIT": {"APP_CLOSE": "LAST_ACK"},
     "LAST_ACK": {"RCV_ACK": "CLOSED"}}

def traverse_TCP_states(events):
    state = "CLOSED"  # initial state, always
    for event in events:
        if event not in d[state]:
            return "ERROR"
        state = d[state][event]
    return state

STATES = {"CLOSED":     {"APP_PASSIVE_OPEN": "LISTEN", "APP_ACTIVE_OPEN": "SYN_SENT"},
          "LISTEN":     {"RCV_SYN": "SYN_RCVD", "APP_SEND": "SYN_SENT", "APP_CLOSE": "CLOSED"},
          "SYN_RCVD":   {"APP_CLOSE": "FIN_WAIT_1", "RCV_ACK": "ESTABLISHED"},
          "SYN_SENT":   {"RCV_SYN": "SYN_RCVD", "RCV_SYN_ACK": "ESTABLISHED", "APP_CLOSE": "CLOSED"},
          "ESTABLISHED":{"APP_CLOSE": "FIN_WAIT_1", "RCV_FIN": "CLOSE_WAIT"},
          "FIN_WAIT_1": {"RCV_FIN": "CLOSING", "RCV_FIN_ACK": "TIME_WAIT", "RCV_ACK": "FIN_WAIT_2"},
          "CLOSING":    {"RCV_ACK": "TIME_WAIT"},
          "FIN_WAIT_2": {"RCV_FIN": "TIME_WAIT"},
          "TIME_WAIT":  {"APP_TIMEOUT": "CLOSED"},
          "CLOSE_WAIT": {"APP_CLOSE": "LAST_ACK"},
          "LAST_ACK":   {"RCV_ACK": "CLOSED"},
         }


def traverse_TCP_states(events):
    state = "CLOSED"
    try:
        for e in events:
            state = STATES[state][e]
        return state
    except KeyError:
        return "ERROR"


def traverse_TCP_states(events, state='CLOSED'):

    for event in events:
        state = {('CLOSED', 'APP_PASSIVE_OPEN'):'LISTEN',
                 ('CLOSED', 'APP_ACTIVE_OPEN'): 'SYN_SENT',
                 ('LISTEN', 'RCV_SYN'):'SYN_RCVD',
                 ('LISTEN', 'APP_SEND'):'SYN_SENT',
                 ('LISTEN', 'APP_CLOSE'):'CLOSED', 
                 ('SYN_RCVD', 'APP_CLOSE'):'FIN_WAIT_1',
                 ('SYN_RCVD', 'RCV_ACK'):'ESTABLISHED',
                 ('SYN_SENT', 'RCV_SYN'):'SYN_RCVD',
                 ('SYN_SENT', 'RCV_SYN_ACK'):'ESTABLISHED',
                 ('SYN_SENT', 'APP_CLOSE'):'CLOSED',
                 ('ESTABLISHED', 'APP_CLOSE'):'FIN_WAIT_1',
                 ('ESTABLISHED', 'RCV_FIN'):'CLOSE_WAIT',
                 ('FIN_WAIT_1', 'RCV_FIN'):'CLOSING',
                 ('FIN_WAIT_1', 'RCV_FIN_ACK'):'TIME_WAIT',
                 ('FIN_WAIT_1', 'RCV_ACK'):'FIN_WAIT_2',
                 ('CLOSING', 'RCV_ACK'):'TIME_WAIT',
                 ('FIN_WAIT_2', 'RCV_FIN'):'TIME_WAIT',
                 ('TIME_WAIT', 'APP_TIMEOUT'):'CLOSED',
                 ('CLOSE_WAIT', 'APP_CLOSE'):'LAST_ACK',
                 ('LAST_ACK', 'RCV_ACK'):'CLOSED'}.get((state, event), 'ERROR')
    return state

NEW_STATE = {
"CLOSED__APP_PASSIVE_OPEN" : "LISTEN",
"CLOSED__APP_ACTIVE_OPEN"  : "SYN_SENT",
"LISTEN__RCV_SYN"          : "SYN_RCVD",
"LISTEN__APP_SEND"         : "SYN_SENT",
"LISTEN__APP_CLOSE"        : "CLOSED",
"SYN_RCVD__APP_CLOSE"      : "FIN_WAIT_1",
"SYN_RCVD__RCV_ACK"        : "ESTABLISHED",
"SYN_SENT__RCV_SYN"        : "SYN_RCVD",
"SYN_SENT__RCV_SYN_ACK"    : "ESTABLISHED",
"SYN_SENT__APP_CLOSE"      : "CLOSED",
"ESTABLISHED__APP_CLOSE"   : "FIN_WAIT_1",
"ESTABLISHED__RCV_FIN"     : "CLOSE_WAIT",
"FIN_WAIT_1__RCV_FIN"      : "CLOSING",
"FIN_WAIT_1__RCV_FIN_ACK"  : "TIME_WAIT",
"FIN_WAIT_1__RCV_ACK"      : "FIN_WAIT_2",
"CLOSING__RCV_ACK"         : "TIME_WAIT",
"FIN_WAIT_2__RCV_FIN"      : "TIME_WAIT",
"TIME_WAIT__APP_TIMEOUT"   : "CLOSED",
"CLOSE_WAIT__APP_CLOSE"    : "LAST_ACK",
"LAST_ACK__RCV_ACK"        : "CLOSED" }


def traverse_TCP_states(events, state="CLOSED"):
    for event in events:
        QUERY = "%s__%s" % (state, event)
        if QUERY in NEW_STATE:
            state = NEW_STATE[QUERY]
        else:
            return "ERROR"
    
    return state

def traverse_TCP_states(events):
    state = 'CLOSED'
    ACTION = {("CLOSED","APP_PASSIVE_OPEN"):"LISTEN",
             ("CLOSED","APP_ACTIVE_OPEN"):"SYN_SENT",
             ("LISTEN","RCV_SYN"):"SYN_RCVD",
             ("LISTEN","APP_SEND"):"SYN_SENT",
             ("LISTEN","APP_CLOSE"):"CLOSED",
             ("SYN_RCVD","APP_CLOSE"):"FIN_WAIT_1",
             ("SYN_RCVD","RCV_ACK"):"ESTABLISHED",
             ("SYN_SENT","RCV_SYN"):"SYN_RCVD",
             ("SYN_SENT","RCV_SYN_ACK"):"ESTABLISHED",
             ("SYN_SENT","APP_CLOSE"):"CLOSED",
             ("ESTABLISHED","APP_CLOSE"):"FIN_WAIT_1",
             ("ESTABLISHED","RCV_FIN"):"CLOSE_WAIT",
             ("FIN_WAIT_1","RCV_FIN"):"CLOSING",
             ("FIN_WAIT_1","RCV_FIN_ACK"):"TIME_WAIT",
             ("FIN_WAIT_1","RCV_ACK"):"FIN_WAIT_2",
             ("CLOSING","RCV_ACK"):"TIME_WAIT",
             ("FIN_WAIT_2","RCV_FIN"):"TIME_WAIT",
             ("TIME_WAIT","APP_TIMEOUT"):"CLOSED",
             ("CLOSE_WAIT","APP_CLOSE"):"LAST_ACK",
             ("LAST_ACK","RCV_ACK"):"CLOSED"}
    for event in events:
        state = ACTION[state,event] if (state,event) in ACTION else 'ERROR'
    return state



def traverse_TCP_states(events):
    lib = {
    ("CLOSED", "APP_PASSIVE_OPEN") : "LISTEN",
    ("CLOSED", "APP_ACTIVE_OPEN")  : "SYN_SENT",
    ("LISTEN", "RCV_SYN")          : "SYN_RCVD",
    ("LISTEN", "APP_SEND")         : "SYN_SENT",
    ("LISTEN", "APP_CLOSE")        : "CLOSED",
    ("SYN_RCVD", "APP_CLOSE")      : "FIN_WAIT_1",
    ("SYN_RCVD", "RCV_ACK")        : "ESTABLISHED",
    ("SYN_SENT", "RCV_SYN")        : "SYN_RCVD",
    ("SYN_SENT", "RCV_SYN_ACK")    : "ESTABLISHED",
    ("SYN_SENT", "APP_CLOSE")      : "CLOSED",
    ("ESTABLISHED", "APP_CLOSE")   : "FIN_WAIT_1",
    ("ESTABLISHED", "RCV_FIN")     : "CLOSE_WAIT",
    ("FIN_WAIT_1", "RCV_FIN")      : "CLOSING",
    ("FIN_WAIT_1", "RCV_FIN_ACK")  : "TIME_WAIT",
    ("FIN_WAIT_1", "RCV_ACK")      : "FIN_WAIT_2",
    ("CLOSING", "RCV_ACK")         : "TIME_WAIT",
    ("FIN_WAIT_2", "RCV_FIN")      : "TIME_WAIT",
    ("TIME_WAIT", "APP_TIMEOUT")   : "CLOSED",
    ("CLOSE_WAIT", "APP_CLOSE")    : "LAST_ACK",
    ("LAST_ACK", "RCV_ACK")        : "CLOSED"
    }
    state = "CLOSED"
    for command in events:
        state = lib.get((state, command), "ERROR")
    return state
            


import abc

class Condition(abc.ABC):
    @abc.abstractmethod
    def check_condition(self, params):
        pass

class ConditionEvent(Condition):
    def __init__(self, event_name):
        self.event_name = event_name

    def check_condition(self, params):
        event_name = params
        return self.event_name == event_name

class Transition:
    def __init__(self, fsm, to):
        self.fsm = fsm
        self.to = to
        self.conditions = []

    def check_conditions(self, params):
        return all(cond.check_condition(params) for cond in self.conditions)


class State:
    def __init__(self, fsm, name):
        self.name = name
        self.transitions = []

    def next_state(self, params):
        next_state = next((trans.to for trans in self.transitions
                          if trans.check_conditions(params)), None)
        return next_state

class FSM:
    def __init__(self):
        self.cur_state_name = None
        self.states = {}

    def next_state(self, params):
        cur_state = self.states[self.cur_state_name]
        next_state = cur_state.next_state(params)
        if next_state is None:
            raise RuntimeError("Error")
        self.cur_state_name = next_state

def create_scheme():
    scheme_str = """
CLOSED: APP_PASSIVE_OPEN -> LISTEN
CLOSED: APP_ACTIVE_OPEN  -> SYN_SENT
LISTEN: RCV_SYN          -> SYN_RCVD
LISTEN: APP_SEND         -> SYN_SENT
LISTEN: APP_CLOSE        -> CLOSED
SYN_RCVD: APP_CLOSE      -> FIN_WAIT_1
SYN_RCVD: RCV_ACK        -> ESTABLISHED
SYN_SENT: RCV_SYN        -> SYN_RCVD
SYN_SENT: RCV_SYN_ACK    -> ESTABLISHED
SYN_SENT: APP_CLOSE      -> CLOSED
ESTABLISHED: APP_CLOSE   -> FIN_WAIT_1
ESTABLISHED: RCV_FIN     -> CLOSE_WAIT
FIN_WAIT_1: RCV_FIN      -> CLOSING
FIN_WAIT_1: RCV_FIN_ACK  -> TIME_WAIT
FIN_WAIT_1: RCV_ACK      -> FIN_WAIT_2
CLOSING: RCV_ACK         -> TIME_WAIT
FIN_WAIT_2: RCV_FIN      -> TIME_WAIT
TIME_WAIT: APP_TIMEOUT   -> CLOSED
CLOSE_WAIT: APP_CLOSE    -> LAST_ACK
LAST_ACK: RCV_ACK        -> CLOSED
"""

    scheme = []
    for line in scheme_str.splitlines():
        if not line:
            continue
    
        from_state, rest = line.split(":")
        event, to_state = rest.split("->")
        scheme.append((from_state.strip(), to_state.strip(), event.strip()))

    return scheme

def create_fsm(scheme):
    fsm = FSM()
    for from_state_name, to_state_name, event in scheme:
        try:
            state = fsm.states[from_state_name]
        except KeyError:
            state = fsm.states[from_state_name] = State(fsm, from_state_name)
    
        transtion = Transition(fsm, to=to_state_name)
        transtion.conditions.append(ConditionEvent(event))
        state.transitions.append(transtion)

    return fsm

def traverse_TCP_states(events):
    scheme = create_scheme()
    fsm = create_fsm(scheme)
    fsm.cur_state_name = "CLOSED"

    try:
        for event in events:
            fsm.next_state(event)
    except:
        return "ERROR"
    else:
        return fsm.cur_state_name

def traverse_TCP_states(events):
    state = "CLOSED"  # initial state, always
    transitiontable = {
        'CLOSED':{'APP_PASSIVE_OPEN':'LISTEN', 'APP_ACTIVE_OPEN':'SYN_SENT'},
        'LISTEN':{'RCV_SYN':'SYN_RCVD', 'APP_SEND':'SYN_SENT', 'APP_CLOSE':'CLOSED'},
        'SYN_RCVD':{'APP_CLOSE':'FIN_WAIT_1', 'RCV_ACK':'ESTABLISHED'},
        'SYN_SENT':{'RCV_SYN':'SYN_RCVD', 'RCV_SYN_ACK':'ESTABLISHED', 'APP_CLOSE':'CLOSED'},
        'ESTABLISHED':{'APP_CLOSE':'FIN_WAIT_1', 'RCV_FIN':'CLOSE_WAIT'},
        'FIN_WAIT_1':{'RCV_FIN':'CLOSING', 'RCV_FIN_ACK':'TIME_WAIT', 'RCV_ACK':'FIN_WAIT_2'},
        'CLOSING':{'RCV_ACK':'TIME_WAIT'},
        'FIN_WAIT_2':{'RCV_FIN':'TIME_WAIT'},
        'TIME_WAIT':{'APP_TIMEOUT':'CLOSED'},
        'CLOSE_WAIT':{'APP_CLOSE':'LAST_ACK'},
        'LAST_ACK':{'RCV_ACK':'CLOSED'}
    }
    for i in events:
        try:
            state = transitiontable[state][i]
        except:
            return 'ERROR'
    return state