mercutio22

1.1) False.
1.2) True, so long as they contain optimal substructure and overlapping sub problems
1.3) False, dynamic programming *can* find an optimal solution
1.4) False, classes themselves are objects in addition to class instances
1.5) True
1.6) False, can have more than one branch.

2) 

def findMedian(L):
    """ Finds median of L.
    L: a non-empty list of floats
    Returns:
    If L has an odd number of elements, returns the median
    element of L. For example, if L is the list
    [15.0, 5.3, 18.2], returns 15.0.
    If L has an even number of elements, returns the average
    of the two median elements. For example, if L is the
    list [1.0, 2.0, 3.0, 4.0], returns 2.5.
    If the list is empty, raises a ValueError exception.
    Side effects: none.
    """
    
    if type(L) != list:
        message = '%s is not a list' %L
        raise TypeError(message)
    else:
        if len(L) > 0:         
            ##print len(L)%2
            if len(L)%2 != 0: #i.e if the list has an odd number of elements
                middle = len(L)/2
                L.sort()
                print 'The median of %s is' %L, L[middle]
                return L[middle]
            else:
                total = 0
                for item in L:
                    total += item
                mean = float(total)/len(L)
                print 'The median of %s is' %L, mean
                return mean
        raise ValueError('Received an empty list to analyse. No can do.')

3)

    16
    Circle with radius 4
    Circle with radius 8

4)
    4.1)
    n: number of items to choose from
    p_i: Value of ith item
    x_i: 0 for taken, 1 for discarded
    C: knapsack weight capacity
    
    4.2)
    Formula 2 is a weight constraint on the maximization of formula 1.

5)
    Return the list if it has only one item. Otherwise, divide it in two equal lenght halves 
    and order each of these recursively rerunning the method just described. Finally, merge the 
    returned sublists.

6)

    def cmpGuess(guess):    
    """Assumes that guess is an integer in range(maxVal). returns -1 if guess is < than the magic
    number, 0 if it is equal to the magic number and 1 if it is greater than the magic number."""
    magicnum = 891
    if guess == magicnum:
        return 0
    if guess > magicnum:
        return 1
    if guess <magicnum:
        return -1

      
    def findNumber(maxVal):
        """Assumes that maxVal is a positive integer. Returns a number, num, such that
        cmpGuess(num) == 0."""
        
        ordered_integers = range(maxVal)
        
        low = 0
        high = maxVal
        guess = (low + high)/2
        
        while cmpGuess(guess) != 0:
            #print 'low:', low, 'high:', high ,'guess:', guess
            if cmpGuess(guess) == -1:
                low = guess
            else: 
                high = guess
            guess = (low + high)/2
        return guess
    

# 6.00 Problem Set 9
#
# Name: Hugo A. M. Torres
# Collaborators:
# Time: From 11:02 wed march 23,2011 to ...

from string import *
import csv # this module should allow me to treat each value in the lines of the
           # input datafile independently
           
class Shape(object):
    def area(self):
        raise AttributeException("Subclasses should override this method.")

class Square(Shape):
    def __init__(self, h):
        """
        h: length of side of the square
        """
        self.side = float(h)
    def area(self):
        """
        Returns area of the square
        """
        return self.side**2
    def __str__(self):
        return 'Square with side ' + str(self.side)
    def __eq__(self, other):
        """
        Two squares are equal if they have the same dimension.
        other: object to check for equality
        """
        return type(other) == Square and self.side == other.side

class Circle(Shape):
    def __init__(self, radius):
        """
        radius: radius of the circle
        """
        self.radius = float(radius)
    def area(self):
        """
        Returns approximate area of the circle
        """
        return 3.14159*(self.radius**2)
    def __str__(self):
        return 'Circle with radius ' + str(self.radius)
    def __eq__(self, other):
        """
        Two circles are equal if they have the same radius.
        other: object to check for equality
        """
        return type(other) == Circle and self.radius == other.radius

#
# Problem 1: Create the Triangle class
#
## TO DO: Implement the `Triangle` class, which also extends `Shape`.

class RightTriangle(Shape):        
        def __init__(self,b, h):
            """
            b = base of the right triangle
            h = height of the right triangle
            Two right angle triangles are equal when their heights are the same
            and their bases are the same. 
            """
        
            self.b = float(b)
            self.h = float(h)
        
        def area(self):
            """Returns the area of the right angle triangle"""
            return (self.b * self.h)/2  
        
        def __str__(self):
            return 'Right-Angle Triangle with base: %s and height: %s' %(str(self.b), str(self.h))
            
        def __eq__(self, other):
            ##if type(other) == RightTriangle:
                ##if self.b == other.b and self.h ==other.h:
                    ##return True
                ##if self.b == other.h and self.h ==other.b:
                    ##return True
                ##else: 
                    ##return False
            ##else:    
                ##return False
             
            return (type(other) == type(self)) and self.h in (other.b, other.h) and self.b in (other.b, other.h)
                
        



#   
# Problem 2: Create the ShapeSet class
#
## TO DO: Fill in the following code skeleton according to the
##    specifications.

class ShapeSet(object):
    def __init__(self):
        """
        Initialize any needed variables
        """
        self.items = [] 
        self.CategorizedItems = { Circle: [], Square:[], RightTriangle:[] }
        self.place = None
        
        ## TO DO
    def addShape(self, sh):
        """
        Add shape sh to the set; no two shapes in the set may be
        identical
        sh: shape to be added
        """
        #aux = True
        if type(sh) not in self.CategorizedItems:
            raise ValueError('Object is not a shape')
             
        for item in self.items:
            if item == sh:
                raise ValueError('sh is alredy inside Shapeset')
        self.items.append(sh)
        self.CategorizedItems[type(sh)].append(sh)
    
    def __iter__(self):
        """
        Return an iterator that allows you to iterate over the set of
        shapes, one shape at a time
        """
        self.place = 0
        return self
        
    def next(self):
        if self.place >= len(self.items):
            raise StopIteration
        self.place += 1
        return self.items[self.place - 1]
        ## TO DO
        
    def __str__(self):
        """
        Return the string representation for a set, which consists of
        the string representation of each shape, categorized by type
        (circles, then squares, then triangles)
        """
        representation = ''
        sorted = [Circle,Square,RightTriangle] #I don't like this. It breaks modularity. I see no other way.
        for shType in sorted:
            for item in self.CategorizedItems[shType]:
                 representation += str(item) + '; \n'
        return representation
     
        ## TO DO
        
#######testing:##############
##Tales = RightTriangle(2,3)
##circulo = Circle(5)
##Conjunto = ShapeSet()
##Conjunto.addShape(Tales)
##quadrado = Square(5)
##quadrado2= Square(3)
##Conjunto.addShape(circulo)
##Conjunto.addShape(quadrado)
##Conjunto.addShape(quadrado2)
##print 'Conjunto, ', Conjunto
##Maiores = findLargest(Conjunto)
##for e in Maiores: print e    
#############################

#
# Problem 3: Find the largest shapes in a ShapeSet
#
def findLargest(shapes):
    """
    Returns a tuple containing the elements of ShapeSet with the
       largest area.
    shapes: ShapeSet
    """
    
    areaDict = {} #{area_value1: (object1, object2, ...), area_value2: (object5,)} and so on
    for item in shapes:
        try: areaDict[item.area()] += (item,)
        except KeyError: 
            areaDict[item.area()] = (item,)
    Biggest = max(areaDict.keys())
    return areaDict[Biggest]

###testing
##ss = ShapeSet()
##ss.addShape(RightTriangle(1.2,2.5))
##ss.addShape(Circle(4))
##ss.addShape(Square(3.6))
##ss.addShape(RightTriangle(1.6,6.4))
##ss.addShape(Circle(2.2))
##print 'ss :', ss
##largest = findLargest(ss)
##for e in largest: print e  

### Testing for multiple shapes with maximum area
##ss = ShapeSet()
##ss.addShape(RightTriangle(3,8))
##ss.addShape(Circle(1))
##ss.addShape(RightTriangle(4,6))
##largest = findLargest(ss)
##for e in largest: print e


#
# Problem 4: Read shapes from a file into a ShapeSet
#

def readShapesFromFile(filename):
    """
    Retrieves shape information from the given file.
    Creates and returns a ShapeSet with the shapes found.
    filename: string
    This works.'eval' is regarded as a dirty hack -- It makes code insecure.
    We should try and get rid of it. The cool thing about this code is 
    that it does not rely on The shape types already defined (Circle, RightTriangle, Square).
    It should work even if we define more shape types.
    I try a different implementation below.
    """
    conjunto = ShapeSet()
    with open(filename) as arquivo:
        for line in csv.reader(arquivo):
            shapeType = line[0]
            shapeData = line[1:] #This is a list of strings. I need tuple of floats.
            ShapeData = str(tuple(shapeData))
            shape = eval(shapeType+ShapeData)
            conjunto.addShape(shape)
        return conjunto

#testing
##sim = readShapesFromFile('shapes.txt')
##print sim



def SaferReadShapesFromFile(filename):
    """
    This one is supposedly safer but relies on a statically defined dictionary 
    to circumvent the problem of instantiating objects with strings.
    """
    
    conjunto = ShapeSet()
    with open(filename) as arquivo:
        array = { 'Circle':Circle,
                'RightTriangle':RightTriangle,
                'Square':Square } # { shapetype : object_to_instantiate}
        for line in csv.reader(arquivo):
            shapeType = line[0]
            shapeData = tuple(line[1:]) #This is a list of strings. I need tuple of floats.
            if len(shapeData) == 1:
                shape = array[line[0]](shapeData[0])
            else: 
                shape = array[line[0]](shapeData[0],shapeData[1])
            print shape
            conjunto.addShape(shape)
        return conjunto
    
#testing
##vai = SaferReadShapesFromFile('shapes.txt')
##print vai

# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name: Hugo Arruda de Moura Torres
# Collaborators:
# Time: Sun Dec5 2010 03:01 AM to...
#

import time
import csv # this module should allow me to treat each value in the lines of the
           # input data file independently 


SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1

#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
    """
    Returns a dictionary mapping subject name to (value, work), where the name
    is a string and the value and work are integers. The subject information is
    read from the file named by the string filename. Each line of the file
    contains a string of the form "name,value,work".

    returns: dictionary mapping subject name to (value, work)
    """

    # The following sample code reads lines from the specified file and prints
    # each one.
    work_value = {}
    with open(filename) as arquivo:
        for linha in csv.reader(arquivo):
            work_value[linha[0]] = int(linha[1]), int(linha[2])
    return work_value
        
        
    # TODO: Instead of printing each line, modify the above to parse the name,
    # value, and work of each subject and create a dictionary mapping the name
    # to the (value, work).

def printSubjects(subjects):
    """
    Prints a string containing name, value, and work of each subject in
    the dictionary of subjects and total value and work of all subjects
    """
    totalVal, totalWork = 0,0
    if len(subjects) == 0:
        return 'Empty SubjectList'
    res = 'Course\tValue\tWork\n======\t====\t=====\n'
    subNames = subjects.keys()
    subNames.sort()
    for s in subNames:
        val = subjects[s][VALUE]
        work = subjects[s][WORK]
        res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
        totalVal += val
        totalWork += work
    res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
    res = res + 'Total Work:\t' + str(totalWork) + '\n'
    print res

def cmpValue(subInfo1, subInfo2):
    """
    Returns True if value in (value, work) tuple subInfo1 is GREATER than
    value in (value, work) tuple in subInfo2
    """
    val1 = subInfo1[VALUE]
    val2 = subInfo2[VALUE]
    return  val1 > val2

def cmpWork(subInfo1, subInfo2):
    """
    Returns True if work in (value, work) tuple subInfo1 is LESS than than work
    in (value, work) tuple in subInfo2
    """
    work1 = subInfo1[WORK]
    work2 = subInfo2[WORK]
    return  work1 < work2

def cmpRatio(subInfo1, subInfo2):
    """
    Returns True if value/work in (value, work) tuple subInfo1 is 
    GREATER than value/work in (value, work) tuple in subInfo2
    """
    val1 = subInfo1[VALUE]
    val2 = subInfo2[VALUE]
    work1 = subInfo1[WORK]
    work2 = subInfo2[WORK]
    return float(val1) / work1 > float(val2) / work2

#
# Problem 2: Subject Selection By Greedy Optimization
#
def sel_sort(subject_dictionary, comparator):
    """Returns a new comparator-sorted list  with the same elements as subject_dictionary keys.
    A selection sort algorithm is used."""
    lista = subject_dictionary.keys()
    for i in range(len(lista)-1):
        #print lista
        maxIndx = i 
        maxVal = lista[i]
        j = i + 1 #this will walk the lenght of the list
        while j < len(lista):
            if comparator(subject_dictionary[lista[j]],subject_dictionary[maxVal]):
                maxIndx = j 
                maxVal = lista[j]
            j += 1
        temp = lista[i]
        lista[i] = lista[maxIndx]
        lista[maxIndx] = temp
    return lista
    

def quick_sort(subjects, comparator) :
    """
    Sorts the list of subjects' names in descendig order
    acording to the comparator. It uses a "merge sort" algorithm
    """
    lista = subjects.keys()
    
    def merge(left,right, comparator,subjects):
        """Assumes left and right are lists sorted according to 'comparator'.
        Returns a new sorted list containing the same elements
        as (left + right) would contain."""
        #print 'left:', left
        #print 'right', right 
        result = []
        i,j = 0, 0
        while i < len(left) and j < len(right):
            if comparator(subjects[left[i]], subjects[right[j]]):
                result.append(left[i])
                i = i + 1
            else:
                result.append(right[j])
                j = j + 1
        while (i < len(left)):
            result.append(left[i])
            i = i + 1
        while (j < len(right)):
            result.append(right[j])
            j = j + 1
        return result
        
    def mergesort(lista):
        """Returns a new sorted list with the same elements as lista"""
        #print lista
        if len(lista) < 2:
            return lista[:]
        else:
            middle = len(lista) / 2
            left = mergesort(lista[:middle])
            right = mergesort(lista[middle:])
            together = merge(left,right,comparator,subjects)
            #print 'merged', together
            return together
            
    return mergesort(lista)
    
def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """
    
    #A greedy algorythm always gets the most valuable item up until the 
    #limit is reached.
    # - First, sort a list of subjects acording to the comparator function in 
    #   question.
    # - Add the values from the sorted list of subjetcs to the results dictionary until
    # - the work limit is reached. 
    
    #materias = sel_sort(subjects, comparator)
    materias = quick_sort(subjects, comparator)
    #print 'sorted:', materias

    GreedyCombo = {}
    sumWork = 0
    count = 0 #trick: this will count the times we take the next 'else' branch
    while sumWork < maxWork:
        for item in materias:
            if  sumWork + subjects[item][WORK] <= maxWork and subjects[item] not in GreedyCombo: # if work of item does not reach or  surpass threshold then I can add subject
                sumWork += subjects[item][WORK]
                GreedyCombo[item] = subjects[item]
            else: #if adding next subject surpasses maxWork do not add the subject
                count +=1
                if count >= len(materias):
                    sumWork = maxWork + 1 # this is a trick to break out of the while loop
                                         ###because all subjects were already tried in this condition
    return GreedyCombo


def bruteForceAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work), which
    represents the globally optimal selection of subjects using a brute force
    algorithm.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    """
    nameList = subjects.keys()
    tupleList = subjects.values()
    bestSubset, bestSubsetValue = \
            bruteForceAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0)
    outputSubjects = {}
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects

def bruteForceAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
                            subset, subsetValue, subsetWork):
    # Hit the end of the list.
    if i >= len(subjects):
        if bestSubset == None or subsetValue > bestSubsetValue:
            # Found a new best.
            return subset[:], subsetValue
        else:
            # Keep the current best.
            return bestSubset, bestSubsetValue
    else:
        s = subjects[i]
        # Try including subjects[i] in the current working subset.
        if subsetWork + s[WORK] <= maxWork:
            subset.append(i)
            bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
                    maxWork, i+1, bestSubset, bestSubsetValue, subset,
                    subsetValue + s[VALUE], subsetWork + s[WORK])
            subset.pop()
        bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
                maxWork, i+1, bestSubset, bestSubsetValue, subset,
                subsetValue, subsetWork)
        return bestSubset, bestSubsetValue

#
# Problem 3: Subject Selection By Brute Force
#
def bruteForceTime(subjects, maxwork, k):
    """
    Runs tests on bruteForceAdvisor and measures the time required to compute
    an answer.
    """
    start_time = time.time()
    # Do some computation. The only purpose of the computation is so we can
    # figure out how long your computer takes to perform a known task.
    result = bruteForceAdvisor(subjects,maxwork)
    end_time = time.time()
    totalTime = end_time - start_time
    print 'It took the brute force algorythm %s seconds to compute' %totalTime
    #printSubjects(result)
    return int(end_time - start_time) * k
    # TODO...

# Problem 3 Observations
# ======================
#
# TODO: write here your observations regarding bruteForceTime's performance
# For maxwork > 10 bruteForceAdvisor seems to take an unreasonable amount of time
# to halt on my PC.


#
# Problem 4: Subject Selection By Dynamic Programming
#

def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjects that provides the maximum value without exceeding maxWork.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)

    Essentially, like the example used in class we are implementing a decision-
    tree comprising two vectors containing work and value entries and a
    maximum work restraint(e.g. available knapsack capacity).
    """
    #this dictionary will hold the best combination of classes to take
    result = {}
    
    #a list of subject names
    #subjectlist = subjects.keys()
    
    #a list of tuples containing subjects's (value, workload)
    tuple_list= subjects.values()
    #print 'tuplas:', tuple_list
    
    #the number of items to be analysed by dynamic programming
    item = len(tuple_list)-1
    magisteria = subjects.keys()
    
    #-memo = memoization dictionary containing precomputed values of the 
    #form item, maxWork: (value).
    memo= {}
    
    selectedSubjects=dpAdvisorHelper(subjects, magisteria, maxWork, item, memo)[1]
    
    for magisteria in selectedSubjects:
        #print magisteria
        result[magisteria]=subjects[magisteria]
    return result
    # this function is ok do not mess with it
        
def dpAdvisorHelper(subjects, magisteria, maxWork, item, memo):
    """ 
    -memo = memoization dictionary containing precomputed values of the 
     form item, maxWork: [value, (selected_subjects,)].
    - index = index of the first undecided object to include in the knapsack
    - reuturns a dictionary mapping (item, maxwork to optimal value and included subjects)
    24:26http://www.youtube.com/watch?v=6h6Fi6AQiRM&feature=related
    """
    
    memoIndex = (item, maxWork)
    
    #try and use pre-computed values:
    try: return memo[memoIndex]
    except KeyError: #if  not there, compute it and store for future use.
        # item 0 means we are at the last subject
        if item == 0:
            # We are considering the first item to include: if we have room, include it, if not, do not
            if subjects[magisteria[item]][WORK] <= maxWork:
                memo[memoIndex] = subjects[magisteria[item]][VALUE], (magisteria[item],) 
            else:
            #withoutItem = dpAdvisorHelper(subjects, tuple_list, item - 1, maxWork, selected_subjects, memo)
                memo[memoIndex] = 0, () # The empty lists represents no item included.
            return memo[memoIndex]
        
        #If we are NOT in the last item we have to consider 3 options
    
        #first, if the class exceeds maxWork, we can't take the class. Over.
        withoutItem = dpAdvisorHelper(subjects, magisteria, maxWork, item-1, memo)
        if subjects[magisteria[item]][WORK] > maxWork:
            memo[memoIndex] = withoutItem
            return memo[memoIndex]
    
        #Now if it doesn't we can either take it or not depending on the Knapsak value:
        
        #Case 1: Including the item: 
        #Get the value for the previous knapsack..
        PreviousValue, PreviousSelection = dpAdvisorHelper(subjects, magisteria,\
        maxWork - subjects[magisteria[item]][WORK], item - 1, memo)
        
        #And add the Item and its value to 
        ValueWithItem = PreviousValue + subjects[magisteria[item]][VALUE] 
        SelectionWithItem = PreviousSelection + (magisteria[item],)
        #=========================================================
        
        #Case 2 Excluding it:
        ValueWithoutItem, SelectionWithoutItem = dpAdvisorHelper(subjects, \
        magisteria, maxWork, item - 1, memo)
        #=========================================================
        
        # Compare case 1 and 2: choose whichever is more valuable:
        if ValueWithItem > ValueWithoutItem:
            memo[memoIndex] = ValueWithItem, SelectionWithItem
        else:
            memo[memoIndex] = ValueWithoutItem, SelectionWithoutItem
        return memo[memoIndex]
    


def dpTime(subjects,MaxWork):
    """
    Runs tests on dpAdvisor and measures the time required to compute an
    answer.
    """
    start=time.time()
    selection = dpAdvisor(subjects,MaxWork)
    end=time.time()
    totalTime = end - start
    print 'It took %s seconds for the dynamic programming algorythm to \
complete its job' %totalTime
    #printSubjects(selection)
    # TODO...
    

    
smallCatalog = {'teste2':(5,3),'6.00':(16,8),'1.00':(7,7),'6.01':(5,45),'15.01':(9,6), 'teste':(7,7)} #smaller dictionary for debugging purposes

subjects = loadSubjects(SUBJECT_FILENAME) #dictionary containing subjects 
                                          # mapped to work and value         
                                          
##print subjects                                                                                                     
##print 'Triar:'
##printSubjects(smallCatalog)
##selection = dpAdvisor(smallCatalog,15)
##print '==========='
##print 'Dynamic Programming selection: (MaxWork = 15)'
##printSubjects(selection)
##
##
##print 'Triar:'
##printSubjects(smallCatalog)
##selection = greedyAdvisor(smallCatalog, 15, cmpValue)
##print '==========='
##print 'Greedy selection: (MaxWork = 15)'
##printSubjects(selection)


#print subjects                                                                                                     
#print 'Triar:'
##printSubjects(subjects)
##selection = dpAdvisor(subjects,30)
##print '==========='
##print 'Dynamic Programming selection: (MaxWork = 30)'
##printSubjects(selection)

#dpTime(smallCatalog,15)
#bruteForceTime(subjects,30,1)
#bruteForceTime(smallCatalog,15,1)

dpTime(subjects,30)
bruteForceTime(subjects,30,1)


# Problem 5 Observations
# ======================
#
# TODO: write here your observations regarding dpAdvisor's performance and
# how its performance compares to that of bruteForceAdvisor.
#
#Well... it seems that for small datasets the bruteforce algorythm can be pretty quick 
#and finishes at comparable timespan as the dp algorythm
#But it is much slower and even fails to complete when using larger datasets as input,
#it fails to comply and the dp algorythm still is able to finish at relatively short time.
#For instance, calling:
#dpTime(smallCatalog,15)
#bruteForceTime(smallCatalog,15,1) :
#
#It took 7.48634338379e-05 seconds for the dynamic programming algorythm to complete its job
#It took the brute force algorythm 4.29153442383e-05 seconds to compute
#
#When calling:
#dpTime(subjects,30)
#bruteForceTime(subjects,30,1)
#It took 0.0338768959045 seconds for the dynamic programming algorythm to complete its job
#Bruteforce never halts.
#

# Problem Set 5: 6.00 Word Game
# Name: 
# Collaborators: 
# Time: 
#

import random
import string
import time

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    print
    
    return wordlist

def get_frequency_dict(word):
    """
    Returns a dictionary where the keys are letters of the word
    and the values are integer counts, for the number of times that
    a letter is repeated in the word.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in word:
        freq[x] = freq.get(x,0) + 1#adds one to the value of the key:value pair each time the letter 'key' is found in 'sequence'
    return freq


# (end of helper code)
# -----------------------------------

#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    # TO DO ...
    score = 0
    for letter in word:
        #print letter, 'adds to score:', SCRABBLE_LETTER_VALUES[letter]
        score += SCRABBLE_LETTER_VALUES[letter]
    if n == len(word):
        return score + 50
    else:        
        return score
    #######################       

#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
    """
    Displays the letters currently in the prin.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """

    
    for letter in hand.keys():
        for j in range(hand[letter]):
            print letter,              # print all on the same line
    print                              # print an empty line

#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """

    
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]#chooses a random vowel from the 'VOWELS' list
        hand[x] = hand.get(x, 0) + 1#adds key-value pair of 'ramdonly chosen vowel':number of previously present said vowel plus one.
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    # TO DO ...
    remaining_hand=hand.copy()
    for letter in word:
        remaining_hand[letter]=remaining_hand.get(letter,0) - 1
    for letter in remaining_hand.keys():
        if remaining_hand[letter] == 0:
            del remaining_hand[letter]
    return remaining_hand
            

#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, points_dict):
    """
    Returns True if word is in the points_dict and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or points_dict.
    
    word: string
    hand: dictionary (string -> int)
    points_dict: list of lowercase strings
    """
    # TO DO ...
    frequency = get_frequency_dict(word)#gets the frequency of letters ocurring in 'word'
    for letter in word:
        if letter not in hand or hand[letter]<frequency[letter]:
            return False
    if word in points_dict:
        return True
    else: return False
    
#
# Problem #4: Playing a hand
#
def get_words_to_points(word_list,n):
    """
    Return a dict that maps every word in word_list to its point value.
    word_list = list of words
    n = maximum size of hand
    """
    points_dict={}
    print 'Computing word scores...'
    for word in word_list:
        points_dict[word] =  get_word_score (word,n)
    return points_dict
    

##def get_sorted_words_to_points(rearrange_dict,n):
    ##"""
    ##Return a dict that maps every word in rearrange_dict to its point value.
    ##rearrange_dict = list of words in sorted characters
    ##n = maximum size of hand
    ##"""
    ##
    ##points_dict={}
    ##print 'Computing word scores...'
    ##for word in rearrange_dict.values():
        ##points_dict[word] =  get_word_score (word,n)
    ##return points_dict
        
##def reverse_lookup(dict,value):
    ##""" Gets the first key of value: 'value' in dict.
    ##
    ##If no such key is in it, return'.'
    ##"""
    ##for key in dict:
        ##if value == dict[key]:
            ##return key
    ##else:
        ##return '.'
        
def pick_best_word(hand, points_dict):
    """
    Return the highest scoring word from points_dict that can be made with the
    given hand.
    Return '.' if no words can be made with the given hand.
    """
    best_score = 0#will store the best possible score
    best_word = 'which_is_it' #will hold best scoring word
    for word in points_dict.keys():
        frequencies = get_frequency_dict(word)
        for letter in word:  #dismisses words which contain
            if letter not in hand: # leters not in hand
                break
            elif frequencies[letter] > hand[letter]:#dismisses word if it has more of letter then hand has.
                break
            else:
                continue
        else:
            if points_dict[word] > best_score:
                best_score = points_dict[word]
                best_word = word
    if best_score == 0: #means no word in points_dict(the word list) could be made with letters in hand
        print 'It is not possible to form a word with the letters in this hand.'
        return '.'
    else:
        print 'The best word in',
        display_hand(hand),
        print 'is:', best_word
        return best_word

#pick_best_word(deal_hand(7), get_words_to_points(load_words(), 7)) #test pick_best_word function
def get_word_arrangements(word_list):
    """Creates a dictionary word-->sorted letters"""
    rearrange_dict = {}
    for word in word_list:
        letter_list=list(word)#a list of letters in word
        letter_list.sort()
        newword=''.join(letter_list)
        rearrange_dict[newword]=word
    #print rearrange_dict
    return rearrange_dict
    
def get_substrings_of(string):
    """Retrieves a list of all possible substrings in a string.
    
    Works on the premisse that the substrings subset of a string with 
    one more character is the formed by taking all the substrings in the
    current subset and adding this character to every element.
    """
    
    result = []
    if len(string) == 1: #the base case
        result.append(string)
        pass
    else:
        for item in get_substrings_of(string[:-1]):
            result.append(item)
            substring = item + string[-1]
            result.append(substring)
        result.append(string[-1])
    result = list(set( result )) #remove dupes
    return result
    
    
def pick_best_word_faster(hand, rearrange_dict): #currently its not returning the best word!!
    """Well, it should pick the highest-scoring word faster!
    
    Return the highest scoring word from points_dict that can be made with the
    given hand.
    Return '.' if no words can be made with the given hand.
    """
    
    #this part gets the hand dictionary and outputs a list of 
    #its letters 
    letter_list = []
    for letter in hand.keys():
        for j in range(hand[letter]):
            letter_list.append(letter)
    letter_list.sort() 
    
    #display_hand(hand)
    #print letter_list
    
    sortedhandstring = ''
    for letter in letter_list:
        sortedhandstring += letter
    #print word 
    
    #this part takes a list of substrings an gives a list of sorted sub-
    #strings
    sorted_substring_list=[]
    for substring in get_substrings_of(sortedhandstring):
        substring_letters=[]
        for letter in substring:
            substring_letters.append(letter)
        substring_letters.sort()
        sorted_substring = ''
        for letter in substring_letters:
            sorted_substring += letter
        else:
            sorted_substring_list.append(sorted_substring)
    #print sorted_substring_list
    
    #this parts filters substrings which cannot form words:
    for substring in sorted_substring_list[:]:
        if substring not in rearrange_dict:
            sorted_substring_list.remove(substring)
    
    hand_points = get_words_to_points(sorted_substring_list,HAND_SIZE)
    
    if hand_points:
        high_scoring = max(hand_points, key=hand_points.get)
        return rearrange_dict[high_scoring]
    else:
        print 'No english words in this hand'
        return '.'
  
        
def play_hand(hand, word_list,points_dict):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
    the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word and the total
    score so far are displayed, the remaining letters in the hand 
    are displayed, and the user is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
    The user can also finish playing the hand by inputing a single
    period (the string '.') instead of a word.

    * The final score is displayed.

    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    
    # TO DO ...
    #print "play_hand not implemented." # replace this with your code...
    totalscore = 0 #starting score
    #time_limit=input('Enter a time limit, in seconds, for players: ')
    #if type(time_limit) != type(1):
    #    time_limit=input('Enter a time limit, in seconds, for players: ')
    #else:
    choice = input("Who should play, CPU(1), faster CPU(2) or you(3)? Input number: ")
    
    if choice == 1 or choice ==2:
        time_limit= get_time_limit(points_dict, 1)
        beggining = time.time()
    elif choice == 3:
        while True:
            try:
                time_limit= int(input('What should the time limit be?: '))
                break
            except (NameError, TypeError):
                print 'Plase enter the amount of time in seconds: '
                continue
    beggining = time.time()
    while len(hand)>0:
        if choice == 1:
            print 'Your hand is: '
            display_hand(hand)
            word = pick_best_word(hand, points_dict)
        elif choice == 2:
            print 'Your hand is: '
            display_hand(hand)
            word = pick_best_word_faster(hand, rearrange_dict)
        elif choice == 3:
            print
            print 'Your hand is: '
            display_hand(hand)
            beggining = time.time()
            word = raw_input('Enter a word composed of letters from your hand or a . to indicate that you are finished: ')
        else: 
            print 'Invalid Input!'
        print
        if word == '.':
            ending = time.time()
            timetaken = ending - beggining
            print 'It took %0.2f seconds to provide an answer' % timetaken
            print 'Totalscore: %0.2f' % totalscore
            return
        elif not is_valid_word(word, hand, word_list):
            print word, "either isn't a proper english word or contains letters which are not in your hand!"
            print
            print 'Current hand:',
            display_hand(hand)  
        else:
            ending = time.time()
            timetaken = ending - beggining
            remaining_time = time_limit - timetaken
            if remaining_time >= 0: 
                print 'It took %0.2f seconds to provide a proper answer' % timetaken
                score = get_word_score(word, HAND_SIZE)
                scoreadjusted = score/timetaken
                totalscore += scoreadjusted
                print word, 'earned you %0.2f points' %scoreadjusted
                hand = update_hand(hand, word)#the word uses up letters in the hand
                print 'Current hand:', 
                display_hand(hand)
                print 'remaining time: %0.2f' % remaining_time
            else: 
                print "You've run out of time!"
                totalscoreadjusted = totalscore/timetaken
                print 'Totalscore: %0.2f' % totalscoreadjusted
                break
    else:
        ending = time.time()
        timetaken = ending - beggining
        print 'Total score: %0.2f' % totalscore
        return
      
        
        
       
#play_hand(deal_hand(HAND_SIZE), load_words())



#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """
    # TO DO ...
    ## uncomment the following block of code once you've completed Problem #4
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list,points_dict)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list,points_dict)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

def get_time_limit(points_dict, k):
    """
    Return the time limit for the computer player as a function of the
    multiplier k.
    points_dict should be the same dictionary that is created by
    get_words_to_points.
    """
    start_time = time.time()
    # Do some computation. The only purpose of the computation is so we can
    # figure out how long your computer takes to perform a known task.
    for word in points_dict:
        get_frequency_dict(word)
        get_word_score(word, HAND_SIZE)
    end_time = time.time()
    return (end_time - start_time) * k

# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    points_dict = get_words_to_points(word_list, HAND_SIZE)
    rearrange_dict = get_word_arrangements(word_list)
    #points_dict = get_sorted_words_to_points(rearrange_dict, HAND_SIZE)
    ##pick_best_word_faster(deal_hand(7), rearrange_dict)
    play_game(word_list)
    
    
    
    
    

# Problem Set 5: Ghost
# Name: Hugo A M Torres 
# Collaborators: solo
# Time: about 2 friggin days (with plenty of interruptions - can't concentrate quite well)
#

import random

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import string

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence): #I never had to use this - must we use dictionaries? simple strings seem apropriate.
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


# (end of helper code)
# -----------------------------------

# Actually load the dictionary of words and point to it with 
# the wordlist variable so that it can be accessed from anywhere
# in the program.
wordlist = load_words()
print #empty line for aesthetics

# TO DO: your code begins here!
def is_contained(seq,wordlist):
    """Tests wether 'seq' is contained in a word from our list
    'seq' must be ascii letters in lowercase"""
    for word in wordlist:
        if seq.lower() in word[:len(seq)]:
            #print 'ta ae'
            return True
        else:
            continue
    #print 'nao tem'
    return False
#is_contained('f', wordlist)

def turn(player, seq,  wordlist):
    """lets player choose a letter. 
    Returns 'False' in case it completes a word or if its addition makes
    impossible the completion of a proper english word.
    Returns word fragment if it does not complete but contributes to the
    completion of the word 
    
    player = current player
    
    seq = current word fragment
    
    wordlist = a list of words in english
    """
    
    print 'Current word fragment: ', "'"+seq+"'"
    print player+',', 
    letter = raw_input("enter a letter: ")
    while letter not in string.ascii_letters:#checks if input in composed of letters
        print letter,'is not a letter in the english alphabet!'
        print
        letter = raw_input("Enter a letter: ")
    else:
        seq += letter.lower()
        if seq in wordlist and len(seq)>3:
            print player, 'loses because', seq, 'is a word!'
            return False
        else:
            if is_contained(seq, wordlist):
                print 'Cool!', seq, 'is part of a word! You get to survive.'
                return seq#print word.lower()    
            else:
                print  'no word begins with', seq +'! YOU LOOSE!!'
                return False
   
#turn('Hugo', 'qui', wordlist)
#word=''
def ghost():
    """ 
    Ghost is an inanely popular two-player wordgame. Our goal in
    this problem is to implement an interactive Python program that
    allows two humans to play a game of Ghost against each other. 
    For those of you who are unfamiliar with the rules, you may read
     all about it at Wikipedia. 
    """
    print "Welcome to Ghost:"
    print
    print "Each turn one player guesses a letter trying to avoid forming a full word."
    print "One looses when creating a fragment which cannot be turned into a word by "
    print "adding further letters OR by completing a valid english word:"
    print


    Player1 = raw_input("Who's player 1?: ")
    Player2 = raw_input("Who's player 2?: ")
    CurrentPlayer = Player1 #this variable keeps switching between player1 and 2 each turn.
    WaitingPlayer = Player2
    word = ""
    word = turn(CurrentPlayer, word, wordlist)
    print#empty line for aesthetics
    CurrentPlayer = Player2
    WaitingPlayer = Player1
    while word != False:
        word = turn(CurrentPlayer, word, wordlist)
        if CurrentPlayer == Player1:#This block will exachange players.
            CurrentPlayer = Player2
            WaitingPlayer = Player1
            print #empty line before next iteration
        else:
            CurrentPlayer = Player1
            WaitingPlayer = Player2
            print #empty line before next iteration
    else:
        if CurrentPlayer == Player1:#This block will exachange players.
            CurrentPlayer = Player2
            WaitingPlayer = Player1
            print WaitingPlayer, 'wins!!!'
        else:
            CurrentPlayer = Player1
            WaitingPlayer = Player2
            print WaitingPlayer, 'wins!!!'
ghost()

# Problem Set 5: 6.00 Word Game
# Name: 
# Collaborators: 
# Time: 
#

import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1#adds one to the value of the key:value pair each time the letter 'key' is found in 'sequence'
    return freq


# (end of helper code)
# -----------------------------------

#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    # TO DO ...
    score = 0
    for letter in word:
        #print letter, 'adds to score:', SCRABBLE_LETTER_VALUES[letter]
        score += SCRABBLE_LETTER_VALUES[letter]
    if n == len(word):
        return score + 50
    else:        
        return score
    #######################       

#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
    """
    Displays the letters currently in the prin.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
            print letter,              # print all on the same line
    print                              # print an empty line

#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]#chooses a random vowel from the 'VOWELS' list
        hand[x] = hand.get(x, 0) + 1#adds key-value pair of 'ramdonly chosen vowel':number of previously present said vowel plus one.
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    # TO DO ...
    remaining_hand=hand.copy()
    for letter in word:
        remaining_hand[letter]=remaining_hand.get(letter,0) - 1
    for letter in remaining_hand.keys():
        if remaining_hand[letter] == 0:
            del remaining_hand[letter]
    return remaining_hand
            

#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    # TO DO ...
    frequency = get_frequency_dict(word)#gets the frequency of letters ocurring in 'word'
    for letter in word:
        if letter not in hand or hand[letter]<frequency[letter]:
            return False
    if word in word_list:
        return True
    else: return False
    
#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
      the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word and the total
      score so far are displayed, the remaining letters in the hand 
      are displayed, and the user is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

    * The final score is displayed.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """
    # TO DO ...
    #print "play_hand not implemented." # replace this with your code...
    totalscore = 0 #starting score
    print 'Your hand is: '
    display_hand(hand)
    while len(hand)>0:
        word = raw_input('Enter a word composed of letters from your hand or a . to indicate that you are finished: ')
        if word == '.':
            print 'Totalscore:', totalscore
            return
        elif not is_valid_word(word, hand, word_list):
            print word, "either isn't a proper english word or contains letters which are not in your hand!"
            print 'Current hand:',
            display_hand(hand)  
        else:
            score = get_word_score(word, HAND_SIZE)
            totalscore += score
            print word, 'earned you', score, 'points.'
            hand = update_hand(hand, word)#the word uses up letters in the hand
            print 'Current hand:', 
            display_hand(hand)
    else:
            print 'Total score:', totalscore
            return
        
       
#play_hand(deal_hand(HAND_SIZE), load_words())



#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """
    # TO DO ...
    ## uncomment the following block of code once you've completed Problem #4
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."


# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

#####################PS2a.py############
#!/usr/bin/env python
#encoding=utf-8

#6a+9b+20c=n n=50 to 55
def solve(n):
    """finds one solution for the dioohantine equation 6a+9b+20c=n"""
    for a in range (0,n/6+1):#upper limit is set so you don't extrapolate the upper value of n+5 when multiplying a, b, or c.
            for b in range(0,n/9+1):#same here
                for c in range (0,n/20+1):#same here
                    randomcombo = 6*a + 9*b + 20*c
                    if n == randomcombo: 
                        #print "Solução para n = " + str(n) + ":", "("+str(a)+","+str(b)+","+str(c)+")"
                        return [randomcombo,a,b,c]
                    else:
                        pass
    return False
                        
def FindSolutions(x):
    """tries to find 5 consecutive solutions for the McNuggets problem, this is for problem 1 of problem set 2 when x = 50"""
    solutionslist = []
    L = range(x,x+6)
    for numberNuggets in L: #try combinations of a, b and c till one solution is found
        if solve(numberNuggets) != False:       
            solutionslist.append(solve(numberNuggets))    
    return solutionslist


#def verify(x):
#    """checks if there exists solutions for all elements in range x,x+5"""
#    x=raw_input("input x: ")
#    FindSolutions(x)
#    if len(solutionslist) < 5:
#        return False 
#    else:   
#        return True
#see if verify(x) is true then there exists solutions for every number > x+5 because we can write any of them in terms of previous solution plus packages of 6, 9 and 20.

## Agora para a segunda parte do problema:

def nope():
    """Encontra o maior número de McNuggets que não pode ser comprado em quantidade exata"""
    unbuyable=[]
    x = 0
    while len(FindSolutions(x)) < 6:#we know from the theorem that once 6 consecutive solutions are found, there are endless solutions.
        x+=1
        if solve(x) == False:
            unbuyable.append(x)#saves an unbuyable value everytime one is found.           
    else:
        print "Largest number of McNuggets that cannot be bought in exact quantity:", unbuyable[-1]
        
print solve(52)
nope()
#print len(FindSolutions(50))

######ps2b.py##############################
#!/usr/bin/env python
#encoding=utf-8


###
### template of code for Problem 4 of Problem Set 2, Fall 2008
####x.a+y.b+z.c=n 

#bestSoFar = 0     # variable that keeps track of largest number
                  # of McNuggets that cannot be bought in exact quantity
packages = (9,12,23)   # variable that contains package sizes
maxn=150
#for n in range(1, 150):   # only search for solutions up to size 150
    ## complete code here to find largest size that cannot be bought
    ## when done, your answer should be bound to bestSoFar

def solve(n):
    """finds one solution for the dioohantine equation 6a+9b+20c=n"""
    for a in range (0,n/packages[0]+1):#upper limit is set so you don't extrapolate the upper value of n+5 when multiplying a, b, or c.
            for b in range(0,n/packages[1]+1):#same here
                for c in range (0,n/packages[2]+1):#same here
                    randomcombo = packages[0]*a + packages[1]*b + packages[2]*c
                    if n == randomcombo: 
                        #print "Solução para n = " + str(n) + ":", "("+str(a)+","+str(b)+","+str(c)+")"
                        return [randomcombo,a,b,c]
                    else:
                        pass
    #print 'There is no solution' 
    return False

def FindSolutions(x):
    """tries to find 5 consecutive solutions for the McNuggets problem, this is for problem 1 of problem set 2 when x = 50"""
    solutionslist = []
    L = range(x,x+packages[0])
    for numberNuggets in L: #try combinations of a, b and c till one solution is found
        if solve(numberNuggets) != False:       
            solutionslist.append(solve(numberNuggets))    
    return solutionslist


def nope():
    """Encontra o maior número de McNuggets que não pode ser comprado em quantidade exata"""
    unbuyable=[]
    x = 0
    while len(FindSolutions(x)) < packages[0]:#we know from the theorem that once 6 consecutive solutions are found, there are endless solutions.
        x+=1
        if solve(x) == False:
            unbuyable.append(x)#saves an unbuyable value everytime one is found.
        elif x > maxn:
            print 'não existe n<', maxn, 'que funciona nessa esquação.'
            return            
    else:
        print "Largest number of McNuggets that cannot be bought in exact quantity:", unbuyable[-1]

nope()

#!/usr/bin/env python
#encoding=utf-8

# Problem Set 4
# Name: Hugo A. M. Torres
# Collaborators: friendless ;-(
# Time: Sun Oct 24 00:50:11 BRST 2010

#
# Problem 1
#

def nestEggFixed(salary, save, growthRate, years):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: the annual percent increase in your investment account (an
      integer between 0 and 100).
    - years: the number of years to work.
    - return: a list whose values are the size of your retirement account at
      the end of each year.
    """
 
    GreeniesYearZero = salary * save * 0.01  
    TotalGreenies=[GreeniesYearZero]#Essa lista irá guardar os valores do meu fundo de aposentadoria ao final de cada ano
    span = range(years)  
    for year in span[1:]:
        GreeniesNow = TotalGreenies[year-1]* (1 + 0.01 * growthRate) + salary * save * 0.01 
        TotalGreenies.append(GreeniesNow)
    return TotalGreenies


def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # TODO: Add more test cases here.

#testNestEggFixed()

#
# Problem 2
#

def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    GreeniesYearZero = salary * save * 0.01  
    TotalGreenies=[GreeniesYearZero]#Essa lista irá guardar os valores do meu fundo de aposentadoria ao final de cada ano
    span = range(len(growthRates))  
    for year in span[1:]:
        GreeniesNow = TotalGreenies[year-1]* (1 + 0.01 * growthRates[year]) + salary * save * 0.01 
        TotalGreenies.append(GreeniesNow)
    return TotalGreenies

def testNestEggVariable():
    salary      = 10000
    save        = 10
    growthRates = [3, 4, 5, 0, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]

    # TODO: Add more test cases here.
#testNestEggVariable()
#
# Problem 3
#

def postRetirement(savings, growthRates, expenses):
    """
    - savings: the initial amount of money in your savings account.
    - growthRate: a list of the annual percent increases in your investment
      account (an integer between 0 and 100).
    - expenses: the amount of money you plan to spend each year during
      retirement.
    - return: a list of your retirement account value at the end of each year.
    """
    # TODO: Your code here.
    GreeniesYearZero = savings * (1 + 0.01 * growthRates[0]) - expenses 
    TotalGreenies=[GreeniesYearZero]#Essa lista irá guardar os valores do meu fundo de aposentadoria ao final de cada ano
    span = range(len(growthRates))  
    for year in span[1:]:
        GreeniesNow = TotalGreenies[year-1]* (1 + 0.01 * growthRates[year]) -expenses 
        TotalGreenies.append(GreeniesNow)
    return TotalGreenies


def testPostRetirement():
    savings     = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]

    # TODO: Add more test cases here.

#
# Problem 4
#

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - preRetireGrowthRates: a list of annual growth percentages on investments
      while you are still working.
    - postRetireGrowthRates: a list of annual growth percentages on investments
      while you are retired.
    - epsilon: an upper bound on the absolute value of the amount remaining in
      the investment fund at the end of retirement.
    """
    assert epsilon > 0

    savings = nestEggVariable(salary,save,preRetireGrowthRates)# gets the list of retirement fund value per year during the working epoch
    
    #============ This block guesses the amount of expenses per year and calculates Retirement fund values per year while retired such that nothing is left by time of death
    high = savings[-1] + epsilon
    low = 0
    ctr = 1 #keeps track of the number of iterations the binary search takes untill finding the answer
    expending = [savings[-1]]
    print 'first attemp:', expending
    while abs(expending[-1]) > epsilon and ctr < 1000:
        guess = (high + low) / 2
        expending = postRetirement(savings[-1], postRetireGrowthRates, guess)# gets the list of retirement fund value per year during the retirement epoch
        if expending[-1] > 0:
            low = guess
        else:
            high = guess
        guess = (high + low) / 2
        ctr += 1
        print 'n-th attempt', expending
    assert ctr <= 1000, 'Iteration count exceeded'
    print 'Bi method. Num. iterations:', ctr, 'Estimate:', guess
    return expending[-1]

def testFindMaxExpenses():
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
testFindMaxExpenses()
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

#!/usr/bin/env python
#encoding=utf-8

from string import *

# this is a code file that you can use as a template for submitting your
# solutions


# these are some example strings for use in testing your code

#  target strings

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'



def countSubStringMatch(targetstring,substring):
    """count ocurrences of substring in targetstring iteratively"""
        
    if type(targetstring) != type(str()) or type(substring) != type(str()) :# type checking (both arguments should be strings)
        return -1 # this indicates an error
    
    count = 0
    primeiro = find(targetstring, substring)
    if primeiro == -1:
        print targetstring, "não tem", substring
        return -1
    else: 
        while primeiro != -1:
            count += 1
            proximo = primeiro + 1   
            primeiro = find(targetstring, substring, proximo)
    print targetstring, "contém", count, substring

def countSubstringMatchRecursive(targetstring, keystring, count=0):
    """count ocurrences of substring in targetstring recursively.
    The count variable serves to keep track of the instances of the
    string through the recursion, and is essentially intialized externally by
    setting it to 0 above.
    This function should be called with 'print'    """  

    #if type(targetstring) != type(str()) or type(keystring) != type(str()) :# type checking (both arguments should be strings)
       # return -1 # this indicates an error  

    primeiro = find(targetstring, keystring)
    if primeiro != -1:
        proximo  = primeiro + 1
        resultado = 1 + countSubstringMatchRecursive(targetstring[proximo:], keystring)
        print resultado        
        return resultado              
    else:
        print 'não há', keystring, 'em', targetstring 
        return 0 #Base case (targetstring==keystring).

#=====================end of ps3a.py============

#  target strings

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

def subStringMatchExact(targetstring, substring):
    """returns a tuple of the starting points of matches of the key string in the target
    string, when indexing starts at 0"""

    if type(targetstring) != type(str()) or type(substring) != type(str()) :# type checking (both arguments should be strings)
        return -1 # this indicates an error
    posicao = ()
    count = 0
    primeiro = find(targetstring, substring)
    if primeiro == -1:
        print targetstring, "não tem", substring
        return -1
    else: 
        while primeiro != -1:
            count += 1
            proximo = primeiro + 1
            posicao = posicao + (primeiro,)   
            primeiro = find(targetstring, substring, proximo)
    print targetstring, "contém", count, substring, 'nas posições: ', posicao


subStringMatchExact(target2, key10)
subStringMatchExact(target2, key11)
subStringMatchExact(target2, key12)
subStringMatchExact(target2, key13)
subStringMatchExact(target1, key10)
subStringMatchExact(target1, key11)
subStringMatchExact(target1, key12)
subStringMatchExact(target1, key13)

#===========================end of ps3b.py==============


target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'


def subStringMatchExact(targetstring, substring):
    """returns a tuple of the starting points of matches of the key string in the target
    string, when indexing starts at 0"""

    if type(targetstring) != type(str()) or type(substring) != type(str()) :# type checking (both arguments should be strings)
        return -1 # this indicates an error
    posicao = ()
    count = 0
    primeiro = find(targetstring, substring)
    if primeiro == -1:
        print targetstring, "não tem", substring
        return -1
    else: 
        while primeiro != -1:
            count += 1
            proximo = primeiro + 1
            posicao = posicao + (primeiro,)   
            primeiro = find(targetstring, substring, proximo)
    return posicao
        
def constrainedMatchPair(FirstMatch, SecondMatch, Length):
    """filters which combinations of subkeys are possible near-matches in targetstring"""
    NearMatch = ()
    for n in FirstMatch:
        for k in SecondMatch: 
            if n + Length+ 1 == k:
                NearMatch += (n,)
            else:
                pass
    return NearMatch
    
### the following procedure you will use in Problem 3

def subStringMatchOneSub(key,target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key',key,'into',key1,'&', key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))#fc que preciso escrever - na verdade é só o filtro!!
        allAnswers = allAnswers + filtered
        print 'match1',match1
        print 'match2',match2
        print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers


subStringMatchOneSub(key10, target2)
subStringMatchOneSub(key11, target2)
subStringMatchOneSub(key12, target2)
subStringMatchOneSub(key13, target2)
subStringMatchOneSub(key10, target1)
subStringMatchOneSub(key11, target1)
subStringMatchOneSub(key12, target1)
subStringMatchOneSub(key13, target1)
#match1 = 0, 4, 8, 12, 18
#match2 = 7, 21
#print constrainedMatchPair(match1, match2, len('a'))

#=================end of ps3c.py==============


target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

def subStringMatchExact(targetstring, substring):
    """returns a tuple of the starting points of matches of the key string in the target
    string, when indexing starts at 0"""

    posicao = ()
    count = 0
    primeiro = find(targetstring, substring)
    if primeiro == -1:
        #print targetstring, "não tem", substring
        return ()
    else: 
        while primeiro != -1:
            count += 1
            proximo = primeiro + 1
            posicao = posicao + (primeiro,)   
            primeiro = find(targetstring, substring, proximo)
    #print posicao
    return posicao

def constrainedMatchPair(FirstMatch, SecondMatch, Length):
    """filters which combinations of subkeys are possible near-matches in targetstring"""
    NearMatch = ()
    for n in FirstMatch:
        for k in SecondMatch: 
            if n + Length+ 1 == k:
                NearMatch += (n,)
            else:
                pass
    return NearMatch

def subStringMatchOneSub(target,key):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        #print 'breaking key',key,'into',key1,'&', key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))#fc que preciso escrever - na verdade é só o filtro!!
        allAnswers = allAnswers + filtered
        #print 'match1',match1
        #print 'match2',match2
        #print 'possible matches for','"',key1,'"', '&', '"',str(key2),'"','start at',filtered
    #print allAnswers
    return allAnswers

def subStringMatchExactlyOneSub(target,key):
    """returns a tuple of all starting points of matches of the key to target
     with exactly one substitution"""
    PerfectMatches = subStringMatchExact(target, key)
    NearMatches = subStringMatchOneSub(target, key)
    results = ()
    all = PerfectMatches + NearMatches
    for member in set(all):
        results += (member,)
    print results 
    return results


#subStringMatchExactlyOneSub(target2, key13)
#subStringMatchOneSub(target2, key13)

#subStringMatchExactlyOneSub(target2, key11)
#subStringMatchOneSub(target2, key11)


#subStringMatchOneSub(target2, key12)
#subStringMatchExact(target2, key12)
#subStringMatchExactlyOneSub(target2, key12)

#print subStringMatchExact(target2, key13)
#subStringMatchOneSub(target2, key13)
#subStringMatchExact(target2, key13)
subStringMatchExactlyOneSub(target2, key13)

#subStringMatchExactlyOneSub(target2, key13)

#subStringMatchExactlyOneSub(target1, key10)

#subStringMatchExactlyOneSub(target1, key11)

#subStringMatchExactlyOneSub(target1, key12)

#subStringMatchExactlyOneSub(target1, key13)
     
#=========================end of ps3d.py==============



           

#!/usr/bin/env python
#encoding=utf-8

from math import *


##===============================PROBLEM 1==========================
def cprimo(x):
    """testa se n é um número primo
    (Tests if n is a prime number )
    """
    if x == 1:
        return False
    elif x == 2:
        return True
    elif x%2 == 0:
        return False    
    else:
        for i in range(3, int(floor(sqrt(x)))+1 , 2):#só é preciso checar os ímpares até raiz de x. +1 para incluir a raiz de quadrados perfeitos.
        #(We only need to verify odd integers up to the sqrt of x! +1 is a trick to account for perfect squares) 
            if x%i != 0:
                pass
            else: 
                #print n, "não é primo."
                return False
        #print n, "é primo."
        return True

def enesimop(n):
    """mostra quem é o n-ésimo número primo
    (Shows who is the n_th prime number)"""
    countprime = 0
    rodada=0
    while countprime < n:
        rodada = rodada + 1
        if cprimo(rodada) == True: 
            countprime = countprime + 1            
        else: 
            pass
    if n == countprime:
        return rodada

print str(1000)+'-th prime number is:', enesimop(1000)
        
##========================================PROBLEM 2===============

def listadeprimos(n):
    """lista todos os números primos menores ou iguais a ao n-ésimo primo.
    (Lists all prime numbers less or equal to the nth prime.)"""
    countprime = 0
    rodada=0
    lista=[]
    while countprime < n:
        rodada = rodada + 1
        if cprimo(rodada) == True:
            lista.append(rodada)
            countprime = countprime + 1            
        else: 
            pass #I don't know when to use pass or continue. Please comment.
    if n == countprime:
        return lista

def sumlog(n):
    """Computa a soma dos lagarítmos de todos os números
        primos de 2 ao n-ésimo primo e também a taxa entre essa soma e o n-ésimo primo"""
    #primomax = enesimop(n) 
    soma = 0
    lista = listadeprimos(n)
    for i in lista:
        #if cprimo(i) == True:
            #print "log of", i, "is", log(i)
            #print soma
            soma = soma + log(i,e) #Here I am using the natural logarithm instead of the common log_10
            #python uses this by default it seems.
            
    #uncomment for portuguese:
    #~ print str(n)+"-ésimo primo:", lista[n-1]
    #~ print "Soma dos logs dos números primos menores que o", n, "-ésimo primo (", lista[n-1], "):", soma 
    #~ print "Relação de", n, "-ésimo primo (", lista[n-1], ") sobre a soma dos logarítmos dos primos menores que ele:", lista[n-1]/soma
    #~ print "============================================================================="
    #uncomment for english:
    print str(n)+'-th prime number is', lista[n-1]
    print 'The sum of the natural logarithms of prime numbers smaller then the', str(n)+'th prime is:', soma
    print 'Ratio of the', str(n)+'-th prime number to that sum:', lista[n-1]/soma
    print "============================================================================="

print 'Observe how the ratio aproximates 1 the bigger the number is:'
sumlog(10**3)
sumlog(10**4)
sumlog(10**5)
sumlog(10**6)

#!/usr/bin/env python
#encoding=utf-8

last_name = raw_input("What's your last name? ")
first_name = raw_input("What's your first name? ")

print "Your name is", first_name, last_name