# Python test,  Spring 2013

# Problem #1 =========================================

def FibList(n):
    # Take care of the 3 beginning cases...
    FirstOnes = [ [], [1], [1, 1] ]
    if n <= 2:
        return FirstOnes[n]

    L = [1, 1]
    for i in range(3, n+1):
        L.append(L[-1]+L[-2])
    return L

# Problem #2 ============================================

def ReadData(filename):
    # we're guaranteed there's data in the file, so we don't need try/except
    fin = open(filename, 'r')
    lines = fin.read().split('\n')
    fin.close()

    TheList = []
    # skip the first line
    for line in lines[1:]:
        fields = line.split(',')
        # make sure there are enough fields, ignore line if not
        if len(fields) == 3:
            d={'name':fields[0], 'gender':fields[1], 'grade':int(fields[2])}
            TheList.append(d)

    return TheList

# Problem #3 ===========================================

def TableByTens(filename):
    # we might as well use the solution we just sweated to produce
    listdicts = ReadData(filename)
    print '<table><tr><td>Grade range</td>'
    print '<td>Number of people</td></tr>'

    for lownum in range(0, 100, 10):
        highnum = lownum + 9
        # let's use a helper function to count how many people
        # have grades between two values
        n = HowManyInRange(listdicts, lownum, highnum)
        print '<tr><td>'+str(lownum)+' - '+str(highnum)+'</td><td>'+str(n)+'</td></tr>'

    print '</table>'

def HowManyInRange(dlist,low,high):
    total = 0
    for d in dlist:
        grade = d['grade']
        if grade >= low and grade <= high:
            total += 1
    return total

# Extra credit: =============================================

def TopFolks(listdicts, gender, percent):
    # create a list of little lists.  Each little list containing a grade and a name
    master = []
    for d in listdicts:
        if d['gender'] == gender:
            name = d['name']
            grade = d['grade']
            little = [grade, name]
            master.append(little)

    # sort (it will sort by grade, just like the SAT data) and reverse it
    master.sort()
    master.reverse()

    # take just the given percent of names
    need = len(master)*percent / 100
    master = master[:need]
    
    for person in master:
        print person[1], person[0]