notes

Notes for Desigh of Computer Programs course in Python from Udacity cs212


Define a Poker Program


A card has a rank and a suit eg. 3 of Diamonds or 3D
hand = 5 cards
hands is a list of hand eg. [hand1, hand2, ..]
poker(hands) -> hand # function poker returns the best hand


Hand rank concept:
n-kind 22  33  888
straight 56789
flush 	 5 diamonds or 5 hearts etc

Order of ranks from highest to lowest:
8 - Straight and Flush
7 - Four of a kind
6 - Full House (3 kinds and 2 kinds)
5 - Flush
4 - Straight
3 - Three of a kind
2 - Two 2 of a kinds
1 - Two of a kind
0 - Nothing

'--23456789TJQKA'.index(r) : Returns a number from 2 to 14 for any rank r.

<List>.count(<element>) : Returns the no. of times the element is present in the list.

To find no. of unique elements in a list, convert it to a set and then check its length : len(set(<List>))

To create a list from a part of another list, use something like: 
List1 = [a.some_function() for a,b in List2] 

Combine if statement with return:
return a if <condition> else b


List comprehensions:

udacity_tas = ['Peter', 'Andy', 'Sarah', 'Job', 'Sean', 'Parker']
uppercase_tas = [name.upper() for name in udacity_tas]

This is possible for all iterable objects: strings, lists, tuples


Multiple values can be unpacked and combined with if statement like below:

ta_data = [('Peter', 'Australia', 'CS101'),
	  ('Andy', 'Brazil', 'CS212'),
	  ('Sarah', 'England', 'CS375'),
	  ('Job', 'Germany', 'CS301'),
	  ('Sean', 'France', 'CS251'),
	  ('Parker', 'USA', 'CS153')]

ta_facts = [name + ' from ' + country + ' is the TA for ' + course for name, country, course in ta_data if course.find('CS3') != -1]


defaultdict :

Using list as the default_factory, it is easy to group a sequence of key-value pairs into a dictionary of lists:

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]


int as default_factory is useful for counting (like a bag or multiset in other languages):

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
... 
>>> d.items()	
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]


Functions are of 'computing' type and 'doing' type. 
Computing fns: sine, sqrt  
	       Take input and return an output like mathematical fns.
	       Easier to use and test. Should be preffered.
	       sorted([3,2,1]) == [1,2,3]

'Doing' type: shuffle()
	      Modify the input. Takes more code - setup the state, call the subroutine or method, and inspect the state (assert statement)
	      input = [3,2,1]
	      input.sort()
	      input == [1,2,3]


itertools.combinations(iterable, r):
Returns r length subsequences of elements from the input iterable.

Can be used like:
return max(itertools.combinations(hand, 5), key=hand_rank)

Examples:
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123

---

itertools.product :

Cartesian product of input iterables.

E.g.:
>>> list(itertools.product('ABCD', 'xy'))
[('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y'), ('D', 'x'), ('D', 'y')]

Applies to any iterable:
>>> list(itertools.product(['A', 'B', 'C'], ['x'], ['z','w']))
[('A', 'x', 'z'), ('A', 'x', 'w'), ('B', 'x', 'z'), ('B', 'x', 'w'), ('C', 'x', 'z'), ('C', 'x', 'w')]

Use repeat to specify if additonal 
>>> list(itertools.product('ABC', repeat=2))
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

>>> list(itertools.product('01', repeat=3))
[('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'), ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '1', '1')]

---

map(function, iterable, ...)

Apply function to every item of iterable and return a list of the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. (Built in function)

---

Generator functions:

Similar to generator expression

def ints(start, end):
    i = start
    while i<= end:
    	  yield i
	  i = i + 1

To call the above fn:

L = ints(0, 100000)
L won't be a list right away. It will be a generator object.
L = <generator>
next(L) gives 0 as output.
Normally this function will be used with a for:
for i in L: ...	       

Generator functions allow us to deal with infinite sequences.

def ints(start, end=None):
    i = start
    while i <= end or end is None:
    	  yield i
	  i = i + 1

ints(0) generates infinite sequence 0, 1, 2...

# Define a function, all_ints(), that generates the 
# integers in the order 0, +1, -1, +2, -2, ...

def all_ints():
    "Generate integers in the order 0, +1, -1, +2, -2, +3, -3, ..."
    yield 0
    i = 1
    while True:
        yield +i
	yeild -i
	i += 1

---

for loops:

for loop internally creates an iterable object using iter(). 

for x in items:
    print x

when the above code is run, the following code is actually implemented:
     
it = iter(items):
try:
     while True:
     	   x = next(it)
	   print x
except StopIteration:
     pass

---

Use ''.join(a) to make a string from a tupple or list of strings or from another string.

If a tupple of ints is to converted to a single string use ''.join(map(str, <tupple>))

Use join() to insert a character between letters of a string:
', '.join('AEIOU') => 'A, E, I, O, U' 

Use a for loop inside join() to create a list from another list:
firstletters = ['Y', 'M']
' and '.join(L + '!=0' for L in firstletters) => 'Y!=0 and M!=0'  

---

When a list is to be returned, check if returning a generator object makes sense: When you don't have to necessarily iterate over the whole list and you might get lucky after a few iterations, making a generator function is the correct thing.
Example: In module 2, fill_in() we said yield in a for loop instead of returning a list:

def fill_in(formula):
    "Generate all possible fillings-in of letters in formula with digits."
    letters = ''.join(set(re.findall('[A-Z]', formula)))
    for digits in itertools.permutations('1234567890', len(letters)):
        table = string.maketrans(letters, ''.join(digits))
        yield formula.translate(table)

This is because we might have gotten our valid formula before the complete iteration.

---

To find out time taken in a file by each function, no. of calls, time per call, etc., use the module cProfile:

From the terminal run:
python -m cProfile <file_to_test>.py 

OR

From inside the script, add the following to the code:

import cProfile
cProfile.run('test()') # where the timing data for test() is required.

---

Handling types "polymorphism"

To check type of a variable use isinstance():
if(isinstance(n, int)):
	...
else:
	...

---

Use brackets inside re.split() to include the chars of split.

str_to_split = 'YOU==ME**2'
list1 = re.split('([A-Z]+)', str_to_split) # ['YOU', '==', 'ME', '**2']
list2 = re.split('[A-Z]+'  , str_to_split) # ['==', '**2']

---

eval is a time consuming function: first creates a parse tree of the expression and then loads and solves the expressions.
Whenever possible, reduce the number of calls to eval. Specially if eval is bieng called inside a for loop: create a string of a simplified expression that was otherwise bieng evaluated inside a loop, evaluate it and return the compiled version: 

# Inside compile_formula():
f = 'lambda Y, O, U, M, E: Y!=0 and M!=0 and ((U+10*O+100*Y) == (E+10*M)**2))'
return eval(f)

# Inside faster_solve()
f = compile_formula(formula)
for digits in ...:
    if f(*digits) is True:
       ...
       return formula.translate(table)

---

We can assign a long function name to a short variable inside a function if it is to be called multiple times:
def test():
    L = longest_subpalindrome_slice
    assert L('racecar')  == (0, 7)
    assert L('Racecar')  == (0, 7)
    assert L('RacecarX') == (0, 7)
    ...

---

Small functions can be written inside another function.

Example:

def longest_subpalindrome_slice(text):
    "Return (i, j) such that text[i:j] is the longest palindrome in text."
    if text == '': return (0, 0)
    def length(slice): a,b = slice; return b-a
    ...

This function length can only be called from within this function only. 

---

To implement regular expression as an API, we need to understand the following concepts: 
Partial Results
Control over iteration

e.g. If pattern is a*b+ and string is 'aaab' then
     we we need to check for b+ in all of the possible results of a* i.e. a, aa, aaa
     i.e. we need to have control over iteration

To do that it is best to first obtain a list of possible remainders after each match.
To match a*b+ first obtain remainders with the match a*:
aaab,  aab, ab, b
Then for each of the above match with b+:
b matches successfully, giving aaab as the result

matchset(pattern, text) => set of all remainders
returns set of all possible remainders when pattern is matched against text.
If no match exists empty set is returned.

matchset('a*', aaab) => ['aaab', 'aab', 'ab', 'b']

---

Interpretter vs. Compiler

Interpretter: 1 step : matchset(pattern, text) => not efficient if same pattern is to be used multiple times.
Compiler    : 2 steps: compile(pattern)  => returns c as compiled object of pattern, now apply to any text as c(text)

Example of implementation:
Interpretter:

def matchset(pattern, text):
    "Match pattern at start of text; return a set of remainders of text."
    op, x, y = components(pattern)
    if 'lit' == op:
        return set([text[len(x):]]) if text.startswith(x) else null

def lit(s): return ('lit', x)

Example: 
>>> matchset(pat2, 'aaab')


Compiler:

def lit(s): return lambda text: set([text[len(x):]]) if text.startswith(x) else null

Compiled form can be of several types:

1. Python functions as above,
2. Actual machine instructions 
3. Machine instructions of a VM, portable across different computers(Java, Python)

Examples:
>>> pat = lit('a')
>>> pat
      <function <lambda> at 0x170b32>
>>> pat('a string')
      set([' string'])
>>>
>>> pat2 = plus(pat)
>>> pat2
      <function <lambda> at 0x180b65>
>>> pat2('aaab')
      set(['b', 'ab', 'aab', 'aaab'])

---

Recognizer

match(pattern, text) => txt | None

Called a recognizer because we are recognizing whether a prefix of text is in the language defined by pattern. 

Generator

gen(pattern) -=> Language L defined by pattern

Eg: 
(a|b)(a|b) => {aa, ab, ba, bb}

a*         => {'', a, aa, aaa, ....}
To make a finite set pass a set of numbers Ns, to limit the lengths of matched patterns, i.e:
pat( {1,2,3} ) => {a, aa, aaa}

Hence we want to find set of all possible patterns (with lengths in Ns) without giving the text

---

map fn can be applied to strings:

a, b, c = lit('a'), lit('b'), lit('c') 
can be written as
a, b, c = map(lit, 'abc')

---

To extend a binary function to an n_ary function use decorators:

If f is a binary function
f2 = n_ary(f) so that 
f2(a,b,c) = f(a, f(b,c))

where n_ary is a function (decorator) we have defined which takes a binary function and returns an n_ary fn.

we can now simply say 
f = n_ary(f)
This extends the functionality of f to take multiple arguments. We did not have to change the definition of f. Had there been multiple functions like f which needed extension to n_ary args like sequence, alternate, add, mul, etc, we would have to change each one of those.

This technique of extension of function's functionality is so common that there is a shortcut for this in Python. Write @<ecorator_name> before defining the function:

@n_ary 
def seq(x, y):
    ...

Defn of n_ary
def n_ary(f):
    """Given binary function f(x,y), return an n_ary function such that
    f(x,y,z) = f(x, f(y,z)), etc. Also allow f(x)=x"""
    def n_ary_f(x, *args):
        return x if not args else f(x, n_ary_f(*args))
    return n_ary_f

---

*args and **kwargs

def f(x, *args):
     print x
     for count, arg in enumerate(args):
             print count, arg

Output of f('a','b','c')
a
0 b
1 c


def bar(**kwargs):
     for a in kwargs:
         print a, kwargs[a]
         

Output of bar(name='one', age=27)
age 27
name one

---

To avoid repetition of line update_wrapper(n_ary_f, f) in all decorator fns like n_ary, 
define a decorator fn which updates the help of fn it is applied to and of the fn that 
the applied fn is applied to.

@decorator
def n_ary(f):
    """Given binary function f(x,y), return an n_ary function such that
    f(x,y,z) = f(x, f(y,z)), etc. Also allow f(x)=x"""
    def n_ary_f(x, *args):
        return x if not args else f(x, n_ary_f(*args))
    # update_wrapper(n_ary_f, f) # Violates DRY principle
    return n_ary_f

def decorator(d):
    """Make function d a decorator; d wraps a function fn.
    Updates help of both the fn d and the fn that d is applied to."""
    def _d(fn):
        return update_wrapper(d(fn), d)
    return update_wrapper(_d, d)

---

y = [1,2,3]
d = {}
if y in d -> ..
If you try to look up a list in a dictionary(hash table) you will get a type error:
TypeError: unhashable type : list

That is because lists are mutable, i.e. you can change the value of any list item. Then the hash value for that list will change at the time of retrival from when it was stored. 
Some languages do allow lists to be put into a hash table. 

------