import itertools

houses = [1, 2, 3, 4, 5]
orderings = list(itertools.permutations(houses)) 

for (red, green, ivory, yellow, blue) in orderings:
    for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in orderings:
        for (coffee, tea, milk, oj, WATER) in orderings:
            for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in orderings:
                for (dog, snails, fox, horse, ZEBRA) in orderings:
                    #constrains go here

                

"""
Explanation: our computers can do about billions instructions per seconds.

2.4 GHZ --> 2.4 billion
Hao: what is a typical number of instructions for a if statement? 

estimation of computing time
End of explanation
"""


#List comprehensions
#[]
#generator expression
# (), g is the promise

def sq(x): print 'sq called',x; return x*x
g=(sq(x) for x in range(10) if x%2==0)
print g
next(g)

for x2 in (sq(x) for x in range(10) if x%2==0): pass
list((sq(x) for x in range(10) if x%2==0))

"""
Explanation: How long does it take?
$5!^5= 24$ billions, if we have a 2.4 GHZ computer, if all these above ( I think this means run for one situation, where totally 24b) can be compiled into one computer instruction, it will take  10 seconds. Here perhaps 1,000 instructions are need. Thus, 10,000 seconds = 2 hour.
generator expression
End of explanation
"""


import itertools
import time

def imright(h1, h2):
    "House h1 is immediately right of h2 if h1-h2 == 1."
    return h1-h2 == 1

def nextto(h1, h2):
    "Two houses are next to each other if they differ by 1."
    return abs(h1-h2) == 1

def zebra_puzzle():
    "Return a tuple (WATER, ZEBRA indicating their house numbers."
    houses = first, _, middle, _, _ = [1, 2, 3, 4, 5]
    orderings = list(itertools.permutations(houses)) # 1
    return next((WATER, ZEBRA)
                for (red, green, ivory, yellow, blue) in orderings
                if imright(green, ivory)
                for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in orderings
                if Englishman is red
                if Norwegian is first
                if nextto(Norwegian, blue)
                for (coffee, tea, milk, oj, WATER) in orderings
                if coffee is green
                if Ukranian is tea
                if milk is middle
                for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in orderings
                if Kools is yellow
                if LuckyStrike is oj
                if Japanese is Parliaments
                for (dog, snails, fox, horse, ZEBRA) in orderings
                if Spaniard is dog
                if OldGold is snails
                if nextto(Chesterfields, fox)
                if nextto(Kools, horse)
                )


#put all "if" statement in last "for" statement will slow down your code a lot!!
print zebra_puzzle()

import time 

#functions are objects in python
def timecall(fn,*args): #multiple input
    "Call function with arguments and return the time in seconds and results"
    t0=time.clock()
    result = fn(*args)
    t1=time.clock()
    return t1-t0,result

print timecall(zebra_puzzle)
print timecall(zebra_puzzle()) #delay execuation; function in python is 
                               #a first class object

def average(numbers):
    "Return the average (arithmetic mean) of a sequence of numbers."
    return sum(numbers) / float(len(numbers)) 

def timedcalls(n, fn, *args):
    """Call fn(*args) repeatedly: n times if n is an int, or up to
    n seconds if n is a float; return the min, avg, and max time"""
    
    if isinstance(n,int):
        times=[timecall(fn,*args)[0] for _ in range(n)]
    else:
        times = []
        while sim(times) < n:
            times.append(timecall(fn,*args)[0])
    return min(times), average(times), max(times)

"""
Explanation: why choose generator expression?

stop early(list comprehensions will go through every situation), 
less indentaion, 
easier to edit (flat vs indent)
End of explanation
"""


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

L=ints(1,100)

next(L)

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

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

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

def all_ints():#my answer
    "Generate integers in the order 0, +1, -1, +2, -2, +3, -3, ..."
    i=0
    while True:
        if i>0:
            yield i
            i=-i
        else:
            yield i
            i=-i+1

L=all_ints()

next(L)

###Teacher's answer
def all_ints():
    "Generate integers in the order 0, +1, -1, +2, -2, +3, -3, ..."
    yield 0
    for i in ints(1):
        yield +i
        yield -i

L2=all_ints()

next(L2)

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

 houses = first, _, middle, _, _ = [1, 2, 3, 4, 5]

"""
Explanation: Till clean up functions ()aspects
generator function (similar to generator expression)
End of explanation
"""


eval("2+2==4")

import string, re

table=string.maketrans('ABC','123')
f='A+B==C'
eval(f.translate(table))

# '1+3==3'
# '1/0==3'
def valid(f):
    "Formula f is valid iff it has no numbers with leading zero and evals true."
    try:
        return not re.search(r'\b0[0-9]',f) and eval(f) is True
    except ZeroDivisionError:
        return False
#b stands for boundry
#012 is 10 in python (octal 8)

"""
Explanation: Next puzzle
End of explanation
"""


# User Instructions
#
# Write a function, solve(formula) that solves cryptarithmetic puzzles.
# The input should be a formula like 'ODD + ODD == EVEN', and the 
# output should be a string with the digits filled in, or None if the
# problem is not solvable.
#
# Note that you will not be able to run your code yet since the 
# program is incomplete. Please SUBMIT to see if you are correct.

import string, re 

def solve(formula):
    """Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
    Input formula is a string; output is a digit-filled-in string or None."""
    # Your code here
    for i in fill_in(formula):
        if valid(i):
            return i
    
# assume: def fill_in(formula):
#        "Generate all possible fillings-in of letters in formula with digits."
    
def valid(f):
    """Formula f is valid if and only if it has no 
    numbers with leading zero, and evals true."""
    try: 
        return not re.search(r'\b0[0-9]', f) and eval(f) is True
    except ArithmeticError:
        return False

a=('1','2')
print '__'.join(a)

import itertools

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

''.join(set(re.findall('[A-Z]','ABC')))

from __future__ import division
#we are using python2, if we want to use division feature in python3, use
#from __future__ import division

#python 2.x --> 3/2=1;1/2=0
#python 3 -->3/2=1.5;1/2=0.5

"""
Explanation: solving
End of explanation
"""


## in terminal, $python -m cProfile crpty.py

import cProfile
cProfile.run(solve('C+B==AB'))

"""
Explanation: now just return one possibility, what if we want to return all possibilities?
haha! just change return to print in solve function
<font color="red">profiling</font>
End of explanation
"""


####devide an conquer
####split it to make easier calls

#####Here is not a easier call
####SPLIT eval("1+1==2") TO eval("1+1"), eval("2") 

###Fewer calls(watch this part videop again)

# --------------
# User Instructions
#
# Write a function, compile_word(word), that compiles a word
# of UPPERCASE letters as numeric digits. For example:
# compile_word('YOU') => '(1*U + 10*O +100*Y)' 
# Non-uppercase words should remain unchaged.

def compile_word(word):
    """Compile a word of uppercase letters as numeric digits.
    E.g., compile_word('YOU') => '(1*U+10*O+100*Y)'
    Non-uppercase words unchanged: compile_word('+') => '+'"""
    # Your code here.
    # His answer
    if word.isupper():
        terms = [('%s*%s' % (10**i,d))
                 for (i,d) in enumerate(word[::-1])]
        return '('+'+'.join(terms)+')'
    else:
        return word

"""
Explanation: speed the eval part

easier calls
fewer calls
End of explanation
"""


