horse_count.py

import sys
from collections import defaultdict, deque

INVALID = "Invalid"

class Record(object):
    SOUND = "neigh"

    def __init__(self):
        self._next = 0

    def expected(self):
        return Record.SOUND[self._next % len(Record.SOUND)]

    def update(self):
        self._next += 1
        return self

class RecordManager(object):
    def __init__(self):
        self.records = defaultdict(deque)

    def put(self, record):
        self.records[record.expected()].append(record)

    def pop(self, c):
        if self.records[c]:
            return self.records[c].popleft()
        elif c == Record.SOUND[0]:
            return Record()
        raise KeyError("Invalid sequence")

    def complete(self):
        return all([ len(v)==0 for k,v in self.records.iteritems() if k != Record.SOUND[0] ])

    def count(self):
        return len(self.records[Record.SOUND[0]])

if __name__ == '__main__':
    # example input: neneighigneighh
    # example output: 2
    line = sys.stdin.readline().strip()

    rm = RecordManager()
    for c in line:
        if c not in Record.SOUND:
            print(INVALID)
            exit(-1)
        try:
            rm.put(rm.pop(c).update())
        except KeyError as e:
            print("%s" % e)
            print(INVALID)
            exit(-1)

    if rm.complete():
        print(rm.count())
    else:
        print(INVALID)