# ex.py
from operator import floordiv, mod
def divide_exact(n, d):
    """Return the quotient and remainder of dividing N by D
    >>> q, r = divide_exact(2013,10)
    >>> q
    201
    >>> r
    3
    """
    return floordiv(n, d), mod(n, d)

python3 -m doctest ex.py

assert a > 0, 'a must greater than 0'

square = lambda x: x * x
# square is a function that takes in x and returns x * x

def search(f):
    x = 0
    while not f(x):
        x + =1
    return x
def inverse(f):
    """return g(y) such that g(f(x)) = x"""
    return lambda y: search(lambda x: f(x) == y)

def trace1(fn):
    def traced(x):
        print('Calling', fn, 'on argument', x)
        return fn(x)
    return traced

@trace1
def square(x):
    return x * x

>>> square(2)
Calling <function square at 0x1006ee170> on argument 2
4

def apply_twice(f, x):
    return f(f(x))
def square(x):
    return x * x

>>> apply_twice(square, 3)
>>> 81

def make_adder(n):
    def ader(k):
        return k + n
    return adder

add_three = make_adder(3)
add_three(4)  # equals 7

def print_sums(x):
    print(x)
    def next_sum(y):
        return print_sums(x+y)
    return next_sum

>>> print_sums(1)(3)(5)
1
4
9

def curry2(f):
    def g(x):
        def h(y):
            return f(x, y)
        return h
    return g

>>> m = curry2(add)
>>> add_three = m(3)
>>> add_three(2)
5
# 效果等同于
>>> curry = lambda f: lambda x: lambda y: f(x, y)

flip, flop = flop, flip

flip = lambda flip: 3

def split(n):
    """Split a positive integer into all but its last digit and its last digit."""
    return n // 10, n % 10

def sum_digits(n):
    """Return the sum of the digits of positive integer n.
    """
    if n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last

def luhn_sum(n):
    """Return the digit sum of n computed by the Luhn algorithm.

    >>> luhn_sum(2)
    2
    >>> luhn_sum(12)
    4
    >>> luhn_sum(42)
    10
    >>> luhn_sum(138743)
    30
    >>> luhn_sum(5105105105105100) # example Mastercard
    20
    >>> luhn_sum(4012888888881881) # example Visa
    90
    >>> luhn_sum(79927398713) # from Wikipedia
    70
    """
    if n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last) + last

def luhn_sum_double(n):
    """Return the Luhn sum of n, doubling the last digit."""
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2 * last)
    if n < 10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last) + luhn_digit

def inverse_cascade(n):
    """Print an inverse cascade of prefixes of n.
    
    >>> inverse_cascade(1234)
    1
    12
    123
    1234
    123
    12
    1
    """
    grow(n)
    print(n)
    shrink(n)

def f_then_g(f, g, n):
    if n:
        f(n)
        g(n)

grow = lambda n: f_then_g(grow, print, n//10)
shrink = lambda n: f_then_g(print, shrink, n//10)

def fib(n):
    """Compute the nth Fibonacci number.

    >>> fib(8)
    21
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-2) + fib(n-1)

def next_largest_coin(coin):
    """Return the next coin. 
    >>> next_largest_coin(1)
    5
    >>> next_largest_coin(5)
    10
    >>> next_largest_coin(10)
    25
    >>> next_largest_coin(2) # Other values return None
    """
    if coin == 1:
        return 5
    elif coin == 5:
        return 10
    elif coin == 10:
        return 25


def count_coins(total):
    """Return the number of ways to make change for total using coins of value of 1, 5, 10, 25.
    >>> count_coins(15)
    6
    >>> count_coins(10)
    4
    >>> count_coins(20)
    9
    >>> count_coins(100) # How many ways to make change for a dollar?
    242
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])                                          
    True
    """
    "*** YOUR CODE HERE ***"
    def helper(lowest, n):
        if (lowest == None):
            return 0
        elif (lowest == n):
            return 1
        elif (lowest > n):
            return 0
        with_coin = helper(lowest, n - lowest)
        without_coin = helper(next_largest_coin(lowest), n)
        return with_coin + without_coin
    return helper(1, total)

def max_subseq(n, t):
    """
    Return the maximum subsequence of length at most t that can be found in the given number n.
    For example, for n = 20125 and t = 3, we have that the subsequences are
        2
        0
        1
        2
        5
        20
        21
        22
        25
        01
        02
        05
        12
        15
        25
        201
        202
        205
        212
        215
        225
        012
        015
        025
        125
    and of these, the maxumum number is 225, so our answer is 225.
    >>> max_subseq(20125, 3)
    225
    >>> max_subseq(20125, 5)
    20125
    >>> max_subseq(20125, 6) # note that 20125 == 020125
    20125
    >>> max_subseq(12345, 3)
    345
    >>> max_subseq(12345, 0) # 0 is of length 0
    0
    >>> max_subseq(12345, 1)
    5
    """
    "*** YOUR CODE HERE ***"
    if n == 0 or t == 0:
        return 0
    with_ones = max_subseq(n//10, t-1) * 10 + n%10
    not_with = max_subseq(n//10, t)
    if with_ones > not_with:
        return with_ones
    else:
        return not_with

>>> odds = [41, 43, 47, 49]
>>> odds[0]
41
>>> len(odds)
4
# concatenation and repetition
>>> [2, 7] + odds * 2
[2, 7, 41, 43, 47, 49, 41, 43, 47, 49]
# nested lists
>>> pairs = [[1, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
30

for <name> in <expression>:
    <suite>

>>> list(range(-2, 2))  # list constructor
[-2, -1, 0, 1]
>>> list(range(4))
[0, 1, 2, 3] 

>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds if 25 % x == 0]
[2, 6]

>>> numerals = {'I':1, 'V': 5, 'X': 10}
>>> numerals['I']
1
>>> numerals.key()
dict_keys(['X', 'V', 'I'])
>>> numerals.items()
dict_items([('X', 10), ('V', 5), ('I', 1)])
>>> 'X' in numerals
True

>>> s = [3, 4, 5]
>>> t = iter(s)
>>> next(t)
3
>>> next(t)
4

>>> d = {'one': 1, 'two': 2, 'three': 3}
>>> d['zero'] = 0
>>> k = iter(d.keys()) # ir iter(d)
>>> next(k)
'one'
>>> v = iter(d.values())
>>> next(v)
1
>>> i = iter(d.items())
>>> next(i)
('one', 1)

>>> r = range(3, 6)
>>> ri = iter(r)
>>> for i in ri:
... 	print(i)
3
4
5
>>> for i in ri:
... 	print(i)
>>>

>>> def plus_minus(x):
... 	yield x
... 	yield -x
>>> t = plus_minus(3)
>>> next(t)
3
>>> next(t)
-3
# plus_minus executed only when next is called

def a_then_b(a, b):
    for x in a:
        yield x
    for x in b:
        yield x
# 与以下函数等价
def a_then_b(a, b):
    yield from a
    yield from b

def countdown(k):
   if k > 0:
       yield k
       yield from countdown(k-1)
>>> t = countdown(3)
>>> next(t)
3
>>> next(t)
2
>>> next(t)
1

>>> suits = ['coin', 'string', 'myriad']
>>> original_suits = suits
>>> suit.pop()
'myriad'
>>> suits.remove('string')
>>> suits
['coin']
>>> suits.append('cup')
>>> suits.extend(['sword', 'club'])
>>> suits
['coin', 'cup', 'sword', 'club']
>>> original_suits
['coin', 'cup', 'sword', 'club']  # 2个名称指向了同一个对象，对对象的改变可以在这两个名称中被反映

a = 1
a += 1  # a指向的对象由1这个对象变成了2这个对象
b = 2   # b此时指向的对象和a是一样的，都是2这个对象（在heap中同样数值的对象只有1个）

a = [1, 2, 3]
a = [1, 2, 3]   # 这两个a指向的对象是不同的，也就是说不同的可变类型对象可以拥有同样的数值

>>> (3, 4, 5, 6)
(3, 4, 5, 6)
>>> tuple([3, 4, 5])
(3, 4, 5)
>>> 3,
(3,)
>>> (3, 4) + (5, 6)
(3, 4, 5, 6)

>>> s = ([1, 2], 3)
>>> s[0][0] = 4
>>> s
([4, 2], 3 )

def f(s=[]):
	s.append(5)   
    return len(s)
>>> f()
1
>>> f()
2
>>> f()
3

s = [2, 3]
t = [5, 6]

def make_withdraw(balance):
    """Return a withdraw function with a starting balance."""
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

def make_withdraw_list(balance):
    b = [balance]
    def withdraw(amount):
        if amount > b[0]:
            return 'Insufficient funds'
        b[0] = b[0] - amount
        return b[0]
    return withdraw

class <name>:
    <suite>

class Account:
    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
>>> a = Account('Jim')
>>> a.holder
'Jim'

a = getattr(obj, 'attr')

class <name>(<base class>):
    <suite>

class A:
    z = -1
    def f(self, x):
        return B(x-1)
    
class B(A):
    n = 4
    def __init__(self, y):
        if y:
            self.z = self.f(y)
        else:
            self.z = C(y+1)

class C(B):
    def f(self, x):
        return x

>>> a = A()
>>> b = B(1)
>>> b.n = 5
-----------
>>> C(2).n
4
>>> a.z == C.z
True
>>> a.z == b.z
False

>>> s = 'Hello'
>>> repr(s)
"'Hello'"

def repr(x):
    return type(x).__repr__(x)

class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

def range_link(start, end):
   """Return a Link containing consecutive integers from start to end.

   >>> range_link(3, 6)
   Link(3, Link(4, Link(5)))
   """
   if start >= end:
       return Link.empty
   else:
       return Link(start, range_link(start + 1, end))


def map_link(f, s):
   """Return a Link that contains f(x) for each x in Link s.

   >>> map_link(square, range_link(3, 6))
   Link(9, Link(16, Link(25)))
   """
   if s is Link.empty:
       return s
   else:
       return Link(f(s.first), map_link(f, s.rest))


def filter_link(f, s):
   """Return a Link that contains only the elements x of Link s for which f(x)
   is a true value.

   >>> filter_link(odd, range_link(3, 6))
   Link(3, Link(5))
   """
   if s is Link.empty:
       return s
   filtered_rest = filter_link(f, s.rest)
   if f(s.first):
       return Link(s.first, filtered_rest)
   else:
       return filtered_rest

class Tree:
    """A tree is a label and a list of branches."""
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)
        
    def __repr__(self):
        if self.branches:
            branch_str = ', ' + repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)

    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('  ' + line)
        return [str(self.label)] + lines

    def is_leaf(self):
        return not self.branches

> (quotient 10 2)
5
> (quotient (+ 8 7) 5)
3
> (+ (* 3
        (+ (* 2 4)
           (+ 3 5)))
     (+ (- 10 7)
        6))
57

;build a list with element 2 and points to null
> (define x (cons 2 nil))
> (car x)
1
> (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)
> (list 1 (list 2 3) 4)
(1 (2 3) 4fil)

> (list 'quotient 10 2)
(quotient 10 2)
> (eval (list 'quotient 10 2))
5

> (define a 4)
> 'a
a
> a
4

> (define b 4)
> '(a ,(+ b 1))
(a (unquote (+ b 1)))
> `(a ,(+ b 1))
(a, 5)

x = 2
total = 0
while x < 10:
    total = total + x * x
    x = x + 2

(begin
 	(define (f x total)
      (if (< x 10)
          (f (+ x 2) (+ total (* x x)))
          total))
 	(f 2 0))

(define (factorial n k)
  (if (= n 0) k
      (factorial (- n 1)
                 (* k n))))

(define (length s)
  (if (null? s) 0
      (+ 1 (length (cdr s)))))

(define (length-tail s)
  (define (length-iter s n)
    (if (null? s) n
        (length-iter (cdr s) (+ 1 n))))
  (length-iter s 0))

(define (sum n total)
      	(if (zero? n) total
        (sum (- n 1) (+ n total))))

(sum 1001 0)

(define-macro (twice expr)
              (list 'begin expr expr))
(define (twice2 expr)
  		(list 'begin expr expr))
> (twice (print 2))
2
2
> (twice2 (print 2))
2
(begin undefined undefined)

create table cities as
	select 38 as latitude, 122 as longtitude, "Berkeley" as name union
	select 42,             71,                "Cambridge"        union
	select 45,             93,                "Minneapolis";

select [columns] from [table] where [condition] order by [order];

create table lift as
  select 101 as chair, 2 as single, 2 as couple union
  select 102         , 0          , 3           union
  select 103         , 4          , 1;

select chair, single + 2 * couple as total from lift;

-- Parents
CREATE TABLE parents AS
  SELECT "abraham" AS parent, "barack" AS child UNION
  SELECT "abraham"          , "clinton"         UNION
  SELECT "delano"           , "herbert"         UNION
  SELECT "fillmore"         , "abraham"         UNION
  SELECT "fillmore"         , "delano"          UNION
  SELECT "fillmore"         , "grover"          UNION
  SELECT "eisenhower"       , "fillmore";

-- Fur
CREATE TABLE dogs AS
  SELECT "abraham" AS name, "long" AS fur UNION
  SELECT "barack"         , "short"       UNION
  SELECT "clinton"        , "long"        UNION
  SELECT "delano"         , "long"        UNION
  SELECT "eisenhower"     , "short"       UNION
  SELECT "fillmore"       , "curly"       UNION
  SELECT "grover"         , "short"       UNION
  SELECT "herbert"        , "curly";
  
-- Parents of curly dogs
SELECT parent FROM parents, dogs WHERE child = name AND fur = "curly";

-- Siblings
SELECT a.child AS first, b.child AS second
  FROM parents AS a, parents AS b
  WHERE a.parent = b.parent AND a.child < b.child;

> select "hello," || " world";
hello, world

> create table phrase as select "hello, world" as s;
> select substr(s, 4, 2) || substr(s, instr(s, " ")+1, 1) from phrase;
low