#
# Question 1
#
# Part A
# 4 points
#
"""
a+b*c+
    abcba *
    babab
    bacca *
    baaab
    aacbb *

^[ab]+$
    abcba
    babab *
    bacca
    baaab *
    aacbb

b.?b
    abcba *
    babab *
    bacca
    baaab
    aacbb *

[ab]c[ab]
    abcba *
    babab
    bacca
    baaab
    aacbb *
"""


# Part B
# 1 point
#
"""
^d?[abc]*d$
^d?[a-c]*d$
# ALTERNATE SOLUTION (correct based on given examples)
^d?[abc]?[abc]?[abc]?d$
"""

#
# Question 2
#
# Part A
# 4 points
#
def compareDates (dateA, dateB):
    a = dateA[3:] + dateA[:2]
    b = dateB[3:] + dateB[:2]
    return cmp(a, b)

# ALTERNATE SOLUTION
def compareDates (dateA, dateB):
    (monthA,yearA) = dateA.split('/') 
    (monthB,yearB) = dateB.split('/')
    if yearA != yearB:
        return cmp(yearA, yearB)
    else:
        return cmp(monthA, monthB)

# ALTERNATE SOLUTION
def compareDates (dateA, dateB):
    (monthA,yearA) = [ int(x) for x in dateA.split('/') ]
    (monthB,yearB) = [ int(x) for x in dateB.split('/') ]
    if yearA - yearB == 0:
        return monthA - monthB
    else:
        return yearA - yearB


# Part B
# 5 points
#
def getSortedIndex (sortedDates, dateToInsert):
    idx = 0
    for d in sortedDates:
        if compareDates(dateToInsert, d) > 0:
            idx += 1
    return idx

# ALTERNATE SOLUTION
def getSortedIndex (sortedDates, dateToInsert):
    for (k,d) in enumerate(sortedDates):
        if compareDates(dateToInsert, d) <= 0:
            return k
    return len(sortedDates)

# ALTERNATE SOLUTION
def getSortedIndex (sortedDates, dateToInsert):
    sortedDates = sortedDates + [ dateToInsert ]
    return sorted(sortedDates, cmp=compareDates).index(dateToInsert)


# Part C
# 5 points
#
monthList = [ x.split('/')[0] for x in dates ]
months = set(monthList)

# ALTERNATE SOLUTION
months = []
for d in dates:
    m = d[:2]
    if m not in months:
        months += [ m ]


# Part D
# 7 points
#
monthList = [ x.split('/')[0] for x in dates ]
monthCounts = sorted([ (monthList.count(m), m) for m in months ])
monthMax = monthCounts[-1][1]


# Part E
# 9 points
#
yearList = [ x.split('/')[1] for x in dates ]
yearCounts = sorted([ (yearList.count(y), y) for y in set(yearList) ])
yearFreqs = [ year for (count,year) in yearCounts ]

# ALTERNATE SOLUTION
years = {}
for d in dates:
    (m,y) = d.split('/')
    years[y] = years.get(y, 0) + 1
yearFreqs = [ y for (y,c) in sorted(years.items(), key=operator.itemgetter(1, 0)) ]


#
# Question 3
#
# 5 points each
#

# #1    pass
# #2    fail    4
# #3    pass
# This code does not remove the friend's beaten card thus 
# allowing it to beaten multiple times.

# #1    pass
# #2    pass
# #3    fail    2
# This code does not sort the friend's cards thus
# it does not choose the best card to remove.

# #1    fail    3
# #2    fail    4
# #3    pass
# This code removes all the firend's cards your card can beat thus
# it does not reflect how each hand matches up overall.


#
# Question 4
#
# Part A
# 2 points each
#

# A movie with 10 elements is BOTH top grossing and top rated.

# The last element is the amount of money grossed by the movie.


# Part B
# 2 points each

# In this case, result is given as an empty dictionary and it is returned
# as a dictionary with each entry newly created such that its keys are
# (title, year) and its values are only [rank, rating].

# In this case, result is given as a dictionary already containing some data
# and it is returned as a dictionary with some of its entries updated such 
# that its value list is appended to include [ rank, rating ] 


# Part C
# 5 points
#
def directorAndCast (movies):
    return sorted(set(uniqueDirectors(movies)) & uniqueCastMembers(movies))

# ALTERNATE SOLUTION
def directorAndCast (movies):
    directors = uniqueDirectors(movies)
    return sorted([ cast for cast in uniqueCastMembers(movies) if cast in directors ])


# Part D
# 7 points
#
def mostMoviesPerDecades (movies): 
    movieDecades = {}
    for (title,year) in movies:
        key = year[:3]
        movieDecades[key] = movieDecades.get(key, 0) + 1
    return sorted([ (count, decade+'0s') for (decade,count) in movieDecades.items() ], reverse=True)

# ALTERNATE SOLUTION
def mostMoviesPerDecades (movies): 
    decades = [ k[1][:3]+'0s' for k in movies ]
    return sorted([ (decades.count(d), d) for d in set(decades) ], reverse=True)