so much python

#Proj2.py
#Implementation of COSC 251 Project 2
#Spring 2012
#Last Revision - 2/21/2012
#Sean Allred and David Rice

############### QUESTION 1 ###############
def d(s):
    raw_input("----DEBUG----{0}".format(s))

class City:
    # parses the intersections from a string s
    def __init__(self, s):
        nums = s.split()
        self.juncs = set(map(int,nums))
        self.roads = dict()
        self.inf = list()

        # create the dictionary of outgoing roads from junctions
        for i in range(0, len(nums), 2):
            if int(nums[i]) in self.roads:
                self.roads[int(nums[i])].append(int(nums[i+1]))
            else:
                self.roads[int(nums[i])] = [int(nums[i+1])]

        # Determine two way streets (as tuples of junctions)
        for j in self.juncs:
            if self.roads.has_key(j):
                for out in self.roads[j]:
                    if self.roads.has_key(out):
                        if j in self.roads[out]:
                            self.inf.append((j,out))

        # remove duplicates
        for twoway in self.inf:
            if (twoway[1], twoway[0]) in self.inf:
                self.inf.remove(twoway)

        # convert tuples to sets
        for i in range(len(self.inf)):
            self.inf[i] = set([self.inf[i][0],self.inf[i][1]])

        #print "  inf = {i}\njuncs = {j}\nroads = {r}".format(i=self.inf,j=self.juncs,r=self.roads)

    def __str__(self):
        return str(self.roads)

    def isInf(self, paths):
    # Go through list of paths
    # if there is any junction that leads to a previous junction, it is infinite
        for path in paths:
            for start in path:
                for end in path:
                    # if we've gone through all previous junctions
                    if start == end or not self.roads.has_key(start):
                        break
                    if end in self.roads[start]:
                        return True
        return False

    def paths(self, a, b, current_path=[]):
        # IF
        #   the start point and end point are the same at the beginning,
        #   junction 'a' does not exist
        #   junction 'b' does not exist
        # return nothing
        if (current_path == [] and a == b) or not (a in self.juncs and b in self.juncs):
            return []

        # add the starting junction to the path
        current_path = current_path + [a]

        # If we've reached the endpoint, (because the endpoint need not any outgoing roads)
        if a == b:
            return [current_path]

        if not self.roads.has_key(a):
            return []

        # prepare the return
        thispath = []

        # for every junction reachable from a
        for junction in self.roads[a]:

            # if we haven't already visited this junction,
            if junction not in current_path:

                # send out a probe finding all paths from this junction to the ending point
                probe = self.paths(junction, b, current_path)

                # add all the paths found
                for potential_path in probe:
                    thispath.append(potential_path)

        # return the paths found from junction a to junction b
        return thispath

    def isCyclic(self, j):
        for pair in self.inf:
            if j in pair:
                return True
        return False

    # returns the number of paths from a to b, -1 if infinite
    def numPaths(self, a, b):
        if self.isCyclic(a):
            return -1
        p = self.paths(a, b)
        if self.isInf(p):
            return -1
        else:
            return len(p)

# takes an input list of characters and returns a list of Cities
def parse(s):
    nums = map(int, s)
    ret = list()

    i = 0
    while i < len(nums):
        citystring = ""
        for j in range(i + 1, i + 2*nums[i] + 1):
            citystring += " {}".format(nums[j])
        i += 2*nums[i] + 1

        ret.append(citystring)

    ret = map(City,ret)
    return ret

# recieves input and returns a list of characters
def problem1_input():
    print "Input:"
    out = list()
    while(True):
        _in = raw_input().split()
        for char in _in:
            if char != '-1':
                out.append(char)
            else:
                return out
    #return "7 0 1 0 2 0 4 2 4 2 3 3 1 4 3".split()

def Problem1():
    #tester = "7 0 1 0 2 0 4 2 4 2 3 3 1 4 3\n5\n0 2\n0 1 1 5 2 5 2 1\n9\n0 1 0 2 0 3\n0 4 1 4 2 1\n2 0\n3 0\n3 1 -1"

    cities = parse(problem1_input())
    for city in cities:
        print "matrix for city {}".format(cities.index(city))
        citymatrix = ""
        for r in range(max(city.juncs) + 1):
            for c in range(max(city.juncs) + 1):
                citymatrix += "{} ".format(city.numPaths(r,c))
            citymatrix += '\n'
        print citymatrix


############### QUESTION 2 ###############


#import string

alph = [' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

def clean(s):
    return s.rjust(5, ' ').lower()

def nxt(s):

    TERM = ['v','w','x','y','z']

    start = 4

    if(s[start] != TERM[start]): # If the index doesn't need to roll over,
        s[start] = alph[alph.index(s[start]) + 1] # Increment the last letter
    else: # We need to do le count!

        # find where we should start the count
        while(s[start] == TERM[start]):
            start = start - 1

        # count it! :D
        s[start] = alph[alph.index(s[start]) + 1]
        t = start + 1

        # make necessary trailing incrementations
        while(t < 5):
            s[t] = alph[alph.index(s[t-1])+1]
            t = t + 1

    return s

def brute_gen():
    l = list()

    e = ['v','w','x','y','z']
    s = [' ',' ',' ',' ','a']

    while(s != e):
        l.append(str(s))
        s = nxt(s)
    l.append(str(e))

    return l

def p2r(s):
    l = brute_gen()
    s = clean(s)
    m = [' ',' ',' ',' ',' ']
    for x in range(5):
        m[x] = s[x]
    m = str(m)

    if (l.count(m) != 0):
        return l.index(m) + 1
    else:
        return 0

def valid(s):
    if(len(s) != 5):
        return False

    for c in s:
        if(alph.count(c) == 0):
            return False

    for c in s:
        if(alph.index(c) == -1):
            return False

    for i in range(4):
        if(alph.index(s[i]) >= alph.index(s[i+1])):
            return False
    return True

def Problem2(s):
    for ans in map(p2r,s.split()):
        print ans


############### QUESTION 3 ###############


def pl(l):
    for n in l:
        d(n)

# Class Molecule:
#   elements: a dictionary of elements and their subscripts
#   count: the coefficient on the molecule
class Molecule:
    class Atomic: # Represents a {Element}_{Subscript} structure (no coefficient)
        def __init__(self, el, sub):
            self.element = el
            self.subscript = sub
        def getElement(self):
            return self.element
        def getSubscript(self):
            return self.subscript

    def __init__(self):
        self.elements = dict()
        self.count = 1

    def __str__(self):
        ret = "{"+str(self.count)+"}"
        for el in self.elements:
            ret += "[{0}_{1}]".format(el,self.elements[el])
        return ret

    def getElementTotals(self):
        ret = dict()
        for el in self.elements.keys():
            ret[el] = self.elements[el] * self.count
        return ret

    def add(self, atomic):
        self.add(atomic.getElement(), atomic.getSubscript())

    def add(self, element, subscript):
        # if the molecule already contains this element, just increase the subscript
        if element in self.elements:
            self.elements[element] += subscript
        else: # otherwise, add the element and its subscript
            self.elements[element] = subscript

    def fold(self, mol):
        self.elements = self.getElementTotals()
        self.count = 1
        for el in mol.elements.keys():
            self.add(el, mol.elements[el] * mol.count)

def getWord(s,i): # Returns a [isElem, token, lastIndex] list from a string s starting at index i
    if i >= len(s) or i < 0:
        return Nothing

    ret = s[i]
    isElem = ret.isalpha()
    i += 1
    while i < len(s):
        #d(str((isDigit, s[i], i, ret)))
        if not isElem:
            if s[i].isdigit():
                ret += s[i]
            else:
                return [isElem,ret,i]
        else:
            if s[i].isupper() or s[i].isdigit():
                return [isElem,ret,i]
            else:
                ret += s[i]
        i = i + 1
    return [isElem,ret,i]

def tokenize(s):
    l = list()
    i = 0
    while i < len(s):
        newi = getWord(s, i)
        i = newi[2]
        l.append(newi)
    return l

def standardize(tokens): # inserts implicit subscripts and puts them into ints
    if tokens[0][0]:
        tokens.insert(0,[False,1,0])
    i = 0
    while i < len(tokens):
        if tokens[i][0]: # if this is an element
            if i+1 == len(tokens):
                tokens.append([False,1,tokens[i][2]])
            elif tokens[i+1][0]: # if the next is also an element (ie not a subscript)
                tokens.insert(i+1,[False,1,tokens[i][2]])
        else: # if this was a subscript
            tokens[i][1] = int(tokens[i][1])
        i = i + 1

    return tokens

def molecularize(tokens):
    mol = Molecule()
    mol.count = tokens[0][1]
    for i in range(1,len(tokens),2):
        mol.add(tokens[i][1], tokens[i+1][1])
    return mol

def getmol(s): # returns a Molecule from a string
    tok = tokenize(s)
    standardize(tok)
    mol = molecularize(tok)
    return mol

def fission(s): # splits a string 'A=B' up into molecular components [[A1,A2,...],[B1,B2,...]
    lnr = s.split('=')
    if len(lnr) != 2:
        print 'error'
        return Nothing
    left = lnr[0].split('+')
    right = lnr[1].split('+')

    lmols = list()
    for m in left:
        lmols.append(getmol(m))

    rmols = list()
    for m in right:
        rmols.append(getmol(m))

    return [lmols,rmols]

def fusion(lnr): # takes the output of fission and folds them for balancing
    if len(lnr) != 2:
        print 'error'
        return Nothing

    for side in lnr:
        for i in range(1,len(side)):
            side[0].fold(side[i])

    return [lnr[0][0], lnr[1][0]]

def balance(s):
    # split up the string into lists of left and right molecules
    # add the sides together element-wise, taking coefficients into consideration
    f = fusion(fission(s))

    # get element totals
    l = f[0].getElementTotals()
    r = f[1].getElementTotals()

    if l == r:
        print "{} balances".format(s)
    else:
        print "{} does not balance".format(s)

def Problem3(s):
    map(balance, s.split())

#print ""
#print ""
#print ""

#Problem3("6H2O+6CO2=6O2+C6H12O6 \n2Na+2H2O=2NaOH+H2 C6H12O6=3C2H2+3O")

# EXTRA CREDIT:
# Balance the equation

# add the set-subtract from each to the other.


############### QUESTION 4 ###############


class Time:
    def __init__(self, h, m):
        self.hour = h
        self.minute = m

    def __str__(self):
        #return "{h}:{m}".format(h=self.hour, m=self.minute)
        return '%(hour)02d:%(minute)02d' % {"hour":self.hour, "minute":self.minute}

    def add(self, time):
        r = Time(self.hour, self.minute)
        r.hour += time.hour
        r.minute += time.minute

        if r.minute > 59:
            r.minute -= 60
            r.hour += 1

        # Do we need to roll over the hour to a day?
        # Is a concept of a day even necessary?

        return r

    def sub(self, time):
        r = Time(self.hour, self.minute)
        r.hour -= time.hour
        r.minute -= time.minute

        if r.minute < 0:
            r.minute += 60
            r.hour -= 1

        return r

    def isLaterThan(self, time):
        if self.hour > time.hour:
            return True
        elif self.hour == time.hour and self.minute > time.minute:
            return True
        return False

    def nextSec(self):
        return self.add(Time(0,1))

    def prevSec(self):
        return self.sub(Time(0,1))

    def nonNeg(self):
        return self.hour >= 0 and self.minute >= 0

    def hasLen(self):
        return self.hour > 0 or self.minute > 0

def eventCompare(event1,event2):
    deltah = event1.start.hour - event2.start.hour
    if deltah == 0:
        return event1.start.minute - event2.start.minute
    else:
        return deltah

#Class for Events
class Event:
    #intialization
    def __init__(self, timeStart, timeEnd):
        self.start = timeStart
        self.end = timeEnd

    #toString function
    def __str__(self):
        return "{}-{}".format(str(self.start), str(self.end))

    #finds out how long the event is
    def getLength(self):
        return self.end.sub(self.start)

    #checks to see if two events overlap at all
    def overlaps(self, event):
        return self.end.isLaterThan(event.start)

    def isOvernight(self):
        return self.start.isLaterThan(self.end)

    def isLongerThan(self, event):
        return self.getLength().sub(event.getLength()).nonNeg()

    def joinOvernight(self, other):
        if self.hour == 0 and self.minute == 0 and other.hour == 23 and other.minute == 59:
            return Event(other.start, self.end)
        if self.hour == 23 and self.minute == 59 or other.hour == 0 and other.minute == 0:
            return Event(self.start, other.end)
        return None

# returns a single Event from a string 'HH:MM-HH:MM'
def getEvent(s):
    times = s.split('-') # splits it up into [HH:MM,HH:MM]
    events = [times[0].split(':'),times[1].split(':')] # splits it up into [[HH,MM],[HH,MM]]

    # it seems to like the stupid way
    for i in range(2):
        for j in range(2):
            events[i][j] = int(events[i][j])

    return Event(Time(events[0][0],events[0][1]), Time(events[1][0],events[1][1]))

# returns a tuple of (minSleep, maxAwake, [Events])
# also does most of the work
def input():
    (minSleep, maxAwake) = inputMinMax()
    events = list()
    imp = raw_input()
    while len(imp) != 0:
        events.append(getEvent(imp))
        imp = raw_input()

    for e in events:
        print e


    events.sort(eventCompare)
    events = overnight(events)
    events.sort(eventCompare)
    print "overnight done"
    for e in events:
        print e
    freetime = complement(events)
    freetime.sort(eventCompare)
    print "freetime"
    for e in freetime:
        print e
    freetime = checkA(freetime, minSleep)
    freetime.sort(eventCompare)
    print "A checked"
    for e in freetime:
        print e

    events = complement(freetime)
    events.sort(eventCompare)


    return ((minSleep, maxAwake), "A", freetime, "B", events)


#checks for events that go over midnight
def overnight(events):
    x = events.pop()
    if x.isOvernight():
        y = Event(Time(x.start.hour, x.start.minute), Time(23, 59))
        z = Event(Time(00, 00), Time(x.end.hour, x.end.minute))
        events.append(y)
        events.append(z)
    else:
        events.append(x)
    return events


#Gets A and B
def inputMinMax():
    s = raw_input("'min max' := ")
    minmax = s.split()
    min = int(minmax[0])
    max = int(minmax[1])
    return (min,max)

#returns a maximized list of valid times for sleep
# takes the complement of events needed to attend
def checkA(events, A):
    A = Event(Time(0, 0), Time(A, 0))
    eventsA = list()
    for e in events:
        if e.isLongerThan(A) or e.getLength() == A.getLength():
            eventsA.append(e)

    if events[0].start.hour == 0 and events[0].start.minute == 0 and events[len(events)-1].end.hour == 23 and events[len(events)-1].end.minute == 59:
        # given overnight 23:00-01:00 (00:00-01:00 23:00-23-59)
        # create a new event from 23:00-25:00
        overn = Event(events[len(events)-1].start, events[0].end.add(Time(24,0)))
        if overn.isLongerThan(A):
            eventsA.append(events[0])
            eventsA.append(events[len(events)-1])
    return eventsA

#returns a list of events that force the cat to be awake too long
def checkB(events, B):
    for e in events:
        if e.getLength().sub(B).hasLen():
            events.remove(e)
    return events

def complement(events):
    comp = list()
    if events[0].start.hasLen():
        x = Event(Time(0,0), events[0].start.prevSec())
        if not x.start.isLaterThan(x.end):
            comp.append(x)
    for i in range(len(events)-1):
        y = Event(events[i].end.nextSec(), events[i+1].start.prevSec())
        if y.getLength().hasLen():
            comp.append(y)
    if  events[len(events)-1] != Time(23, 59):
        z = Event(events[len(events)-1].end.nextSec(), Time(23,59))
        if not z.start.isLaterThan(z.end):
            comp.append(z)
    return comp


#################################
t = input()
print "","input done"
#for e in t[1]:
#   print e
for m in t:
    for n in m:
        print n

# A = Event(Time(0,0),Time(2,0))
# B = Event(Time(0,0),Time(3,0))
#
# print A,B
# print B.isLongerThan(A)