def isprime(n): if n < 2: return False if n == 2: return True if n % 2 == 0 return False for i in range(3, int(n**0.5) + 1, 2): if n % i == 0: return False return True
Category: Python
Hold and roll
def hold(state):
(p, me, you, pending) = state
return (other[p], you, me+pending, 0)
def roll(state, d):
(p, me, you, pending) = state
if d == 1:
return (other[p], you, me+1, 0)
else:
return (p, me, you, pending+d)
otehr = {1:0, 0:1}
def test_actions():
s = (0, 10, 20, 30)
assert hold(s) == (1, 20, 40, 0)
assert roll(s, 6) == (0, 1, 20, 36)
assert roll(s, 1) == (1, 20, 11, 0)
return 'test_actions passes'
import random possible_moves = ['roll', 'hold'] def clueless(state): return random.choice(possible_moves)
def play_pig(A, B): strategies = [A, B] state = (0, 0, 0, 0) while True: (p, me, you, pending) = state if me >= goal: return strategies[p] elif you >= goal: return strategies[other[p]] elif strategies[p](state) == 'hold': state = hold(state) else: state = roll(state, random.randint(1,6))
update wrapper
from functools import update_wrapper
def genseq(x, y, Ns):
def n_ary_f(x, *args):
return x if not args else f(x, n_ary_f(*args))
update_wrapper(n_ary_f, f)
return n_ary_f
def seq(x, y): return ('seq', x, y)
>>> help(seq)
Help on function n_ary_f in module __main__:
n_ary_f(x, *args)
@decorator def trace(f): indent = ' ' def _f(*args): signature = '%s(%s)' % (f.__name__, ', '.join(map(repr, args))) print '%s--> %s' % (trace.level*indent, signature) trace.level += 1 try: print '%s<-- %s === %s' % ((trace.level-1)*indent, signature, result) finally: trace.level -= 1 return result trace.level = 0 return _f [/python] [python] G = grammar(r""" Exp => Term [+-] Exp | Term Term => Factor [*/] Term | Factor Factor => Funcall | Var | Num | [(] Exp[)] Funcall => Var [(] Exp[)] Exps => Exp [,] Exps | Exp Var => [a-zA-Z_]\w* Num => [-+]?[.][0-9]*) """)
JSON = grammar("""
object => { } | { members }
members => pair, members | pair
pair => string: value
array => [[][]] | [[] elements []]
elements => value, elements | value
value => string | number | object | array | true | false | null
string => "[^"]*"
number => int frac exp | int frac | int exp | int
int => ->[1-9][0-9]*
frac => [.][0-9]+
exp => [eE][-+]?[0-9]+
""", whitespace='\s*')
def inverse(f, delta=1/128.):
def f_1(y):
x = 0
while f(x) < y:
x += delta
return x if (f(x)-y < y-f(x-delta)) else x-delta
return f_1
def square(x): return x * x
print sqrt(100)
print sqrt(99)
print sqrt(100000000)
[/python]
Regular expression
def match1(p, text): if not text: return False return p == '.' or p == text[0] def match_star(p, pattern, text): return (match(pattern, text) or (match(p, text) and match_star(p, pattern, text[1:]))) print test()
api
def lit(string): return ('lit', string)
def seq(x, y): return ('seq', x, y)
def alt(x, y): return ('alt', x, y)
def star(x): return ('star', x)
def plus(x): return seq(x, star(x))
def opt(x): return alt(lit(''), x) #opt(x) means that x is optional
def oneof(chars): return ('oneof', tuple(chars))
dot = ('dot',)
eol = ('eol',)
def search(pattern, text): for i in range(len(text)): m = match(pattern, text[i:]) if : return m def match(pattern, text): remainders = matchset(pattern, text) if remainders: shortest = min(remainders, key=len) return def components(pattern): x = pattern[1] if len(pattern) > 1 else None y = pattern[2] if len(pattern) > 2 else None return pattern[0], x, y
def matchset(pattern, text): elif 'seq' == op: return set(t2 for t1 in matchset(x, text) for t2 in matchset(y, t1)) def seq(x, y) return lambda text: set().union(*map(y, x(text))) def alt(x, y) return lambda text: x(text) | y(ext)
def genseq(x, y, Ns): Nss = range(max(Ns)+1) return set(m1 + m2 for m1 in x(Nss) for m2 in y(Nss) if len(m1 + m2) in Ns)
Compile word
def compile_word(word):
if word.isupper():
terms = [('%s*%s' % (10**i, d))
for (i, d) in enumerate(word[::-1])]
return '(' + '+'.join(terms) + ')'
else:
return word
Regular Expression
->find substring string
ex. s = ‘some long thing with words’
s.find(‘word’)
‘baa*!’
* a*
? a?
. a.
def search(pattern, text):
if pattern.startswitch('^'):
return match(pattern[l:], text)
else:
return match('.*' + pattern, text)
def match(pattern, text):
if pattern == '':
return True
elif pattern == '$':
return (text == '')
elif len(pattern) > 1 and pattern[1] in '*?':
else:
return (match1(pattern[0], text) and
match(pattern[1:], text[1:]))
Estimating Runtime
import itertools houses = [1, 2, 3, 4, 5] orderings = list(itertools.permutation(houses)) for (red, green, ivory, yellow, blue) in orderings: for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in orderings: for (dog, snails, fox, horse, ZEBRA) in orderings: for (coffee, tea, milk, oj, WATER) in orderings: for (oldGold, kools, Chesterfields, LuckyStrike, Parliaments) in orderings:
def zebra_puzzle(): houses = first, _, middle, _, _ = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) return next((WATER, ZEBRA)
import time def t(): t0 = time.clock() zebra_puzzle() t1 = time.clock() return t1-t0 print t() def timecall(fn, *args): t0 = time.clock() result = fn(*args) t1 = time.clock() return t1-t0
def timecall(fn, *args): t0 = time.clock() result = fn(*args) t1 = time.clock() return t1-t0 def timedcalls(n, fn, *args): times = [timedcall(fn, *args)[0] for _ in range(n)] return min(times), average(times), max(times) def average(numbers): return sum(numbers) / float(len(numbers))
def instrument_fn(fn, *args): c.starts, c.items = 0, 0 result = fn(*args) print '%s got %s with %5d iters over %7d items' % ( fn.__name__, result, c.starts, c.items)
def ints(start, end):
i = start
while i <= end
yield i
i = i + 1
[/python]
[python]
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
[/python]
[python]
import string, re
def valid(f):
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False
[/python]
[python]
import string, re
def solve(formula):
def valid(f):
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False
[/python]
card shuffle
import random mydeck = [r+s for r in '23456789TJQKA' for s in 'SHDC'] def deal(numhands, n=5, deck=mydeck) random.shuffle(deck) return [deck[n*i:n*(i+1)] for i in range(numhands)]
def hand_percentages(n=700*1000): "sample n random hands and print a table of percentages for each type of hand." counts = [0] * 9 for i in range(n/10): for hand in deal(10): ranking = hand_rank(hand)[0] counts[ranking] += 1 for i in reversed(range(9)): print "%14s: %6.3f %%" % (hand_names[i], 100.*counts[i]/n)
def shuffle1(deck): N = len(deck) swapped = [False] * N while not all(swapped) i, j = random.randrange(N), random.randrange(N) swapped[i] = swapped[j] = True swap(deck, i, j) def swap(deck, i, j): print 'swap', i, j deck[i], deck[j] = deck[j], deck[i]
utas = ['Peter', 'Andy', 'Sarah', 'Gundega', 'Job', 'Sean'] uppercasetas = [name.upper() for name in utas] print uppercasetas
total nums
def ss(nums): total = 0 for i in range(len(nums)): total = (total + num[i]**2) return total
def ss(nums): return sum(x**2 for x in nums)
poker problem set
[‘js’,’jd’,’2s’,’2c’,’7h’]
[(11,’s’),(11,’d’),(2,’s’),(2,’c’),(7,’h’)]
key abs mean absolute value, so -5 would be max nums
def poker(hands): "Return the best hand: poker([hand,...]) => hand" return max print max([3, 4, 5, 0]), max([s, 4, -5, 0], key=abs)
highest rank
def poker(hands): "Return the best hand: poker([hand,...]) => hand" return max(hands, key=hand_rank) def hand_rank(hand) return ??? print max([3, 4, 5, 0]), max([s, 4, -5, 0], key=abs)
Testing
def poker(hands):
"Return the best hand: poker([hand,...]) => hand"
return max(hands, key=hand_rank)
def test():
"Test cases for the functions in poker program"
sf = "6C 7C 8C 9C TC".split()
fk = "9D 9H 9S 9C 7D".split()
fh = "TD TC TH 7C 7D".split()
assert poker([sf, fk, fh]) == sf
assert poker([fk, fh]) == fk
assert poker([fh, fh]) == fh
assert poker([sf]) == sf
assert poker([sf] + 99*[fh]) == sf
return 'tests pass'
def hand_rank(hand):
"Return a value indicating the ranking of a hand"
ranks = card_ranks(hand)
if straight(ranks) and flush(hand): # straight flush
return (8, max(ranks))
elif kind(4, ranks): # 4 of a kind
return (7, kind(4, ranks), kind(1, ranks))
elif kind(3, ranks) and kind(2, ranks): # full house
return (6, kind(3, ranks), kind(2, ranks))
elif flush(hand): # flush
return (5, ranks)
elif straight(ranks): # straight
return (4, max(ranks))
elif kind(3, ranks): # 3 of a kind
return (3, kind(3, ranks), ranks)
elif two_pair(ranks): # 2 pair
return (2, two_pair(ranks), ranks)
elif kind(2, ranks): # kind
return (1, kind(2, ranks), ranks)
else: # high card
return (0, ranks)
def poker(hands):
"Return the best hand: poker([hand,...]) => hand"
return allmax(hands, key=hand_rank)
def allmax(iterable, key=None):
"Return a list of all items equal to the max of the iterable."
result, maxval = [], None
key = key or (lambda x: x)
for x in iterable:
xval = key(x)
if not result or xval > maxval:
result, maxval = [x], xval
elif xval == maxval:
result.append(x)
return result
def hand_rank(hand):
"Return a value indicating the ranking of a hand"
ranks = card_ranks(hand)
if straight(ranks) and flush(hand): # straight flush
return (8, max(ranks))
elif kind(4, ranks): # 4 of a kind
return (7, kind(4, ranks), kind(1, ranks))
elif kind(3, ranks) and kind(2, ranks): # full house
return (6, kind(3, ranks), kind(2, ranks))
elif flush(hand): # flush
return (5, ranks)
elif straight(ranks): # straight
return (4, max(ranks))
elif kind(3, ranks): # 3 of a kind
return (3, kind(3, ranks), ranks)
elif two_pair(ranks): # 2 pair
return (2, two_pair(ranks), ranks)
elif kind(2, ranks): # kind
return (1, kind(2, ranks), ranks)
else: # high card
return (0, ranks)
def card_ranks(cards):
"Return a list of the ranks, sorted with higher first."
ranks = ['--23456789TJQKA'.index(r) for r,s in cards]
ranks.sort(reverse=True)
return [5, 4, 3, 2, 1] if (ranks == [14, 5, 4, 3, 2])
def straight(ranks):
"Return True if the ordered ranks form a 5-card straight."
return (max(ranks)-min(ranks) == 4) and len(set(ranks)) == 5
def flush(hand):
"Return True if all the cards have the same suit."
suits = [s for r, s in hand]
return len(set(suits)) == 1
def kind(n, ranks):
"""Return the first rank that this hand has exactly n of.
Return None if there is no n-of-a-kind in the hand."""
for r in ranks:
if ranks.count(r) == n: return r
return None
def two_pair(ranks):
"""If there are two pair, return the two ranks as a
tuple: (highest, lowest); otherwise return None."""
pair = kind(2, ranks)
lowpair = kind(2, list(reversed(ranks)))
if pair and lowpair != pair:
return (pair, lowpair)
else:
return None
def test():
"Test cases for the functions in poker program"
sf = "6C 7C 8C 9C TC".split() # Straight Flush
fk = "9D 9H 9S 9C 7D".split() # Four of a Kind
fh = "TD TC TH 7C 7D".split() # Full House
tp = "5S 5D 9H 9C 6S".split() # two pair
s1 = "AS 2S 3S 4S 5C".split() # A-5 straight
s2 = "2C 3C 4C 5S 6S".split() # 2-6 straight
ah = "AS 2S 3S 4S 6C".split() # A high
sh = "2S 3S 4S 6C 7D".split() # 7 high
assert poker([s1, s2, ah, sh]) == s2
fkranks = card_ranks(fk)
tpranks = card_ranks(tp)
assert kind(4, fkranks) == 9
assert kind(3, fkranks) == None
assert kind(2, fkranks) == None
assert kind(1, fkranks) == 7
assert two_pair(fkranks) == None
assert two_pair(tpranks) == (9, 5)
assert straight([9, 8, 7, 6, 5]) == True
assert straight([9, 8, 8, 6, 5]) == False
assert flush(sf) == True
assert flush(fk) == False
assert card_ranks(sf) == [10, 9, 8, 7, 6]
assert card_ranks(fk) == [9, 9, 9, 9, 7]
assert card_ranks(fh) == [10, 10, 10, 7, 7]
assert poker([sf, fk, fh]) == sf
assert poker([fk, fh]) == fk
assert poker([fh, fh]) == fh
assert poker([sf]) == sf
assert poker([sf] + 99*[fh]) == sf
assert hand_rank(sf) == (8, 10)
assert hand_rank(fk) == (7, 9, 7)
assert hand_rank(fh) == (6, 10, 7)
return 'tests pass'
fibo
def fibo(n):
in n <= 2:
return 1
else:
return fibo(n-1)+fibo(n-2)
print fibo(20)
[/python]
[python]
chart = {}
def memofibo(n):
if n in chart:
return chart[n]
elif n <= 2:
chart[n] = 1
print memofibo(24)
[/python]
[python]
def t_javascript(token):
r'<script\ type=\"text\/javascript\"\>'
token.lexer.code_start = token.lexer.lexpos
token.lexer.begin("javascript")
def t_javascript_end(token):
def t_javascript(token):
r'<script\ type=\"text\/javascript\"\>'
token.lexer.code_start = token.lexer.lexpos
token.lexer.begin("javascript")
def t_javascript_end(token):
r'\<\/script\>'
token.value = token.lexer.lexdata[token.lexer.code_start:
token.lexer.lexpos-9]
token.type = 'JAVASCRIPT'
token.lexer.lineno += token.value.count('\n')
token.lexer.begin.('INITIAL')
return token
parthing:構文解析 lexing:字句解析
after regular expression, lexer get token value.
javascript to python
# function mymin(a, b){
# if (a < b){
# return a;
# } else {
# return b;
# };
# }
#
# function square(x){
# return x * x;
# }
#
# write(mymin(square(-2), square(3)));
def mymin(a, b):
if (a < b):
return a
else:
return b
def square(x):
return x * x
print mymin(square(-2), square(3))
[1,2,3,4,5,6,7] def odds_only(numbers): for N in numbers: if N % 2 == 1: yield N
def small_words(words): for word in words: if len(word) <= 3: yield word print [w for w in small_words(["The","quick","brown","fox"])]
grammar = [
("exp",["exp","+","exp"]),
("exp",["exp","-","exp"]),
("exp",["(","exp",")"]),
("exp",["num"]),
]
def expand(tokens, grammar):
for pos in range(len(tokens)):
for rule in grammar:
depth = 1
utterances = [["exp"]]
def sublists(big_list, selected_so_far): if big_list == []: print selected_so_far else: current_element = big_list[0] rest_of_big_list = big_list[1:] sublists(rest_of_big_list, selected_so_far + [current_element]) sublists(rest_of_big_list, selected_so_far ) dinner_guests = ["LM", "ECS", "SBA"] sublists(dinner_guests, [])
def cfgempty(grammar, symbol, visited): if symbol in visited: return None elif not any([rule[0] == symbol for rule in grammar ]): return [symbol] else: new_visited = visited + [symbol] for rhs in [r[1] for r in grammar if r[0] == symbol]: if all([None] != cfgempty(frammar, r, new_visited) for r in rhs): result = [] for r in rhs: result = result + cfgempty(grammar, r, new_visited) return result return None