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?
In [ ]:
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
$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.
In [ ]:
#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)
In [20]:
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))
Out[20]:
In [40]:
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)
)
In [47]:
#put all "if" statement in last "for" statement will slow down your code a lot!!
print zebra_puzzle()
In [35]:
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
In [37]:
print timecall(zebra_puzzle)
print timecall(zebra_puzzle()) #delay execuation; function in python is
#a first class object
In [39]:
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)
Till clean up functions ()aspects
In [12]:
def ints(start,end):
i=start
while i <= end:
yield i
i=i+1
In [13]:
L=ints(1,100)
In [21]:
next(L)
Out[21]:
In [ ]:
def ints(start,end=None): #generate infinite integers
i=start
while i <= end or end is None:
yield i
i=i+1
In [26]:
# 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
In [27]:
L=all_ints()
In [73]:
next(L)
Out[73]:
In [74]:
###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
In [94]:
L2=all_ints()
In [99]:
next(L2)
Out[99]:
In [100]:
###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
In [101]:
houses = first, _, middle, _, _ = [1, 2, 3, 4, 5]
In [104]:
eval("2+2==4")
Out[104]:
In [107]:
import string, re
In [106]:
table=string.maketrans('ABC','123')
f='A+B==C'
eval(f.translate(table))
Out[106]:
In [ ]:
# '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)
In [135]:
# 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
In [122]:
a=('1','2')
print '__'.join(a)
In [131]:
import itertools
In [133]:
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)
In [129]:
''.join(set(re.findall('[A-Z]','ABC')))
Out[129]:
In [132]:
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
In [140]:
## in terminal, $python -m cProfile crpty.py
import cProfile
cProfile.run(solve('C+B==AB'))
In [ ]:
####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")
In [ ]:
###Fewer calls(watch this part videop again)
In [142]:
# --------------
# 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