Introduction to Python

Homework #4

Due Tuesday Oct 20 , 11:50pm

Problem 1 - Longest Ordered Substring(los)

argument: a string
returns: the longest substring such that the characters strictly increase(in the < sense) from left to right
if there is more than one longest string, return any one of them



In [13]:

    
# usual ordering
['a' < 'b', 'b' < 'a', 'a' < 'a']









    Out[13]:





[True, False, False]



In [141]:

    
def los(word):
    wordlist = list()
    Word = word[0]
    for i in range(len(word)-1):
        if word[i] < word[i+1]:
            b = word[i+1]
            Word += b
        else:
            wordlist.append(Word)
            Word = word[i+1]
            
            
    wordlist.append(Word)
    return wordlist



In [142]:

    
los('abcd')









    Out[142]:





['abcd']



In [143]:

    
los('xabcyz')









    Out[143]:





['x', 'abcyz']



In [144]:

    
los('cba')









    Out[144]:





['c', 'b', 'a']



In [145]:

    
los('larry')









    Out[145]:





['l', 'ar', 'ry']



In [146]:

    
los('xabcxabcdexuvwxyz')









    Out[146]:





['x', 'abcx', 'abcdex', 'uvwxyz']



In [147]:

    
los('xabcxabcdexpuvwxyz')









    Out[147]:





['x', 'abcx', 'abcdex', 'puvwxyz']

Problem 2

suppose we want to convert between C(Celsius) and F(Fahrenheit), using the equation 9C = 5(F-32)
write functions 'c2f' and 'f2c'
do all computation in floating point for this problem



In [130]:

    
def c2f(n):
    f = 1.8*n+32
    return f
def f2c(n):
    c = 5.0*(n-32)/9
    return c



In [131]:

    
[c2f(0), c2f(100), f2c(32), f2c(212)]









    Out[131]:





[32.0, 212.0, 0.0, 100.0]

to write f2c, you solved the equation for C, and made a function out of the other side of the equation
to write c2f, you solved for F, ...
there is another way to think about this
rearrange the equation into a symmetric form

9*C - 5*F = -32*5

you can think of the equation above as a "constraint" between F and C. if you specify one variable, the other's value is determined by the equation. in general, if we have

c0*x0 + c1*x1 + ... cN*xN = total

cI are fixed coefficients
specifying any N of the (N+1) x's will determine the remaining x variable
define a class, 'Constaint' that will do 'constraint satisfaction'



In [186]:

    
class Constraint:
    def __init__(self,name,interval,total):
        self.name = name
        self.interval = interval
        self.total = total
        self.b = self.name.split(' ',) 
        self.Null = [None] * (len(self.interval))
        self.Sum = 0
    def setvar(self,n,m):
        if isinstance(n,str):
            if n in self.b:
                self.Null[self.b.index(n)] = m
                self.Sum = self.Sum + m * self.interval[self.b.index(n)]
        else:
            self.Null[n] = m
            self.Sum = self.Sum + m * self.interval[n]
        if sum(x is None for x in self.Null) == 1: 
            self.Null[self.Null.index(None)] = (self.total - self.Sum) / float(self.interval[self.Null.index(None)])
            return self.Null
            
            self.Null = [None] * (len(self.interval))
        else:
            return self.Null



In [188]:

    
# setup constraint btw C and F
# 1st arg is var names, 
# 2nd arg is coefficients
# 3rd arg is total
c = Constraint('C F', [9,-5], -5*32)

# 1st arg - variable index or name
# 2nd arg - variable value
# setvar will fire when there is only one unset variable remaining
# it will print the variable values, and returns them in a list, and
# clear all variable values
c.setvar(0,100)









    Out[188]:





[100, 212.0]



In [189]:

    
# can set var by index or name
c.setvar('C', 0)









    Out[189]:





[0, 212.0]



In [190]:

    
c.setvar('F', 212)









    Out[190]:





[0, 212]



In [173]:

    
# more complex example
c2 = Constraint('x0 x1 x2 x3 x4', range(5), 1)



In [174]:

    
c2.setvar('x0', 0)









    



0






    Out[174]:





[0, None, None, None, None]



In [175]:

    
c2.setvar('x1', 10)









    



10






    Out[175]:





[0, 10, None, None, None]



In [176]:

    
# x2
c2.setvar(2,20)









    



50






    Out[176]:





[0, 10, 20, None, None]



In [177]:

    
# only one unset var left, x4, so fire
c2.setvar('x3', 30)









    



140






    Out[177]:





[0, 10, 20, 30, -34.75]

Problem 3

write 'mindot'. given two equal length vectors, different dot products can be calculated, by permutting the order of the vectors. for example, given the vectors
```
[10,20]
[0, 1]
```
there are two possible dot products, 10 and 20.
mindot should return the min, 10
mindot can be written very easily by using functions from itertools and functools
'operator' module has functional versions of operators
- '+' <=> operator.add
- '*' <=> operator.mul



In [55]:

    
import itertools 
import functools
import operator

v2a = [10,20]
v2b = [0, 1]

v3a = [1,3,-5]
v3b = [-2, 4, 1]

v4a = range(1,6)
v4b = [1,0,1,0,1]

[operator.add(2,3), operator.mul(2,3)]









    Out[55]:





[5, 6]



In [56]:

    
b = [1,2,3]
a = list(itertools.permutations(b,len(b)))
len(a)
a[1]
sum(p*q for p,q in zip(b,a[1]))









    Out[56]:





13



In [57]:

    
def mindot(a,b):
    Sum = list()
    vector = list(itertools.permutations(b,len(b)))
    for i in range(len(vector)):
        c = vector[i]
        Sum.append(sum(p*q for p,q in zip(a,c)))
    return min(Sum)



In [58]:

    
[mindot(v2a,v2b),mindot(v3a, v3b), mindot(v4a, v4b)]









    Out[58]:





[10, -25, 6]

Problem 4

You are in a store, and you have some cash burning a hole in your pocket - you want to spend all of it!!
write 'pickitems'
- 1st arg - list of prices for things in the store
- 2nd arg - cash you have
- returns - list of prices that will exactly spend your cash
itertools module is your friend



In [101]:

    
cash1 = 4
prices1= [1,1,1,1,8]

cash2 = 200
prices2 = [150, 24, 79, 50, 88, 345, 3]

cash3 = 8
prices3 = [2, 1, 9, 4, 4, 56, 90, 3]

cash4 = 542
prices4 = [230, 863, 916, 585, 981, 404, 316, 785, 
       88, 12, 70, 435, 384, 778, 887, 755, 740, 
       337, 86, 92, 325, 422, 815, 650, 920, 125,
       277, 336, 221, 847, 168, 23, 677, 61, 400,
       136, 874, 363, 394, 199, 863, 997, 794, 587,
       124, 321, 212, 957, 764, 173, 314, 422, 927,
       783, 930, 282, 306, 506, 44, 926, 691, 568,
       68, 730, 933, 737, 531, 180, 414, 751, 28, 
       546, 60, 371, 493, 370, 527, 387, 43, 541,
       13, 457, 328, 227, 652, 365, 430, 803, 59,
       858, 538, 427, 583, 368, 375, 173, 809, 896,
       370, 789]



In [115]:

    
def pickn(price,cash):
    pSort = sorted(price)
    for i in range(len(pSort)):
        pSum = sum(pSort[:i])
        if pSum >= cash:
            return i
            break



In [117]:

    
def pickitems(price,cash):
    for i in range(1,pickn(price,cash)+1):
        b = list(itertools.permutations(price,i))
        A = list()
        for j in range(len(b)):
            A += [sum(b[j])]
        if cash in A:
            return b[A.index(cash)]



In [119]:

    
[pickitems(prices1, cash1), pickitems(prices2, cash2), pickitems(prices3, cash3), pickitems(prices4, cash4)]









    Out[119]:





[(1, 1, 1, 1), (150, 50), (4, 4), (221, 321)]

Problem 5

define a function decorator 'secure'
secure adds two required arguments before any others, a 'user' and a 'password'
if the user is not registered, raise an Exception
if the user is registered, but the password is wrong, raise an Exception



In [167]:

    
up = {}
up['jack'] = 'jackpw'
up['jill'] = 'jillpw'
up









    Out[167]:





{'jack': 'jackpw', 'jill': 'jillpw'}



In [169]:









    Out[169]:





[1, 2]



In [177]:

    
# the user/password 'database'
up = {}
up['jack'] = 'jackpw'
up['jill'] = 'jillpw'
up
def secure(func):
    
    def checkLogin(user, pw, *args,**kwargs):

        if not user in up:
            raise Exception('User %s not registered' % user)
        if pw != up[user]:
            raise Exception("Bad password")
        
        return(func(*args, **kwargs))
    
    return checkLogin

@secure
def foo(a,b):
    return (a+b)

@secure
def bar(a, b=34):
    return(a+b)



In [178]:

    
foo(1,2)









    



---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-178-8c799f9772bc> in <module>()
----> 1 foo(1,2)

<ipython-input-177-c425b92570b8> in checkLogin(user, pw, *args, **kwargs)
      9 
     10         if not user in up:
---> 11             raise Exception('User %s not registered' % user)
     12         if pw != up[user]:
     13             raise Exception("Bad password")

Exception: User 1 not registered



In [179]:

    
# wrong number of args

foo(1,2)









    



---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-179-790da69007fa> in <module>()
      1 # wrong number of args
      2 
----> 3 foo(1,2)

<ipython-input-177-c425b92570b8> in checkLogin(user, pw, *args, **kwargs)
      9 
     10         if not user in up:
---> 11             raise Exception('User %s not registered' % user)
     12         if pw != up[user]:
     13             raise Exception("Bad password")

Exception: User 1 not registered



In [180]:

    
# good call

foo('jack', 'jackpw', 1 ,2)









    Out[180]:





3



In [181]:

    
# bad user

foo('frank', 'bad', 1 ,2)









    



---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-181-b35ba770f676> in <module>()
      1 # bad user
      2 
----> 3 foo('frank', 'bad', 1 ,2)

<ipython-input-177-c425b92570b8> in checkLogin(user, pw, *args, **kwargs)
      9 
     10         if not user in up:
---> 11             raise Exception('User %s not registered' % user)
     12         if pw != up[user]:
     13             raise Exception("Bad password")

Exception: User frank not registered



In [182]:

    
# good user, bad passwd
foo('jack', 'nope')









    



---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-182-c358a6298bd4> in <module>()
      1 # good user, bad passwd
----> 2 foo('jack', 'nope')

<ipython-input-177-c425b92570b8> in checkLogin(user, pw, *args, **kwargs)
     11             raise Exception('User %s not registered' % user)
     12         if pw != up[user]:
---> 13             raise Exception("Bad password")
     14 
     15         return(func(*args, **kwargs))

Exception: Bad password



In [183]:

    
# works with keywords

bar('jill', 'jillpw', 5, b=34)









    Out[183]:





39