def hailstone(n):
    """Q1: Yields the elements of the hailstone sequence starting at n.
       At the end of the sequence, yield 1 infinitely.

    >>> hail_gen = hailstone(10)
    >>> [next(hail_gen) for _ in range(10)]
    [10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
    >>> next(hail_gen)
    1
    """
    yield n
    if n==1:
        n=1
    elif n%2==0:
        n=int(n/2)
    else:
        n=3*n+1
    yield from hailstone(n)

def merge(a, b):
    """Q2:
    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    gene_a = next(a)
    gene_b = next(b)
    while True:
        if gene_a == gene_b:
            yield gene_a
            gene_a = next(a)
            gene_b = next(b)
        elif gene_a> gene_b:
            yield gene_b
            gene_b = next(b)
        else:
            yield gene_a
            gene_a = next(a)

def yield_paths(t, value):
    """Q4: Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:
        yield [value]
    for b in branches(t):
        for p in yield_paths(b, value):
            yield [label(t)]+p

def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    idx = 0
    while idx<len(s):
        if s[idx]==before:
            s.insert(idx+1,after)
            idx+=1
        idx+=1
    return s

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for val in s:
        key = fn(val)
        if key in grouped:
            grouped[key].append(val)
        else:
            grouped[key] = [val]
    return grouped

def count_occurrences(t, n, x):
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    cnt = 0
    times = 0
    while cnt<n:
        if next(t)== x:
            times+=1
        cnt+=1
    return times

def repeated(t, k):
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    pre = 0
    cnt = 0
    while True:
        cur = next(t)
        if cur == pre:
            cnt+=1
        else:
            cnt=1
        pre = cur
        if cnt == k:
            return cur

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    if is_leaf(t):
        return tree(label(t), [tree(leaf) for leaf in leaves])
    return tree(label(t), [sprout_leaves(s, leaves) for s in branches(t)])

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    end = len(s)-1
    while start < end:
        s[start], s[end] = s[end], s[start]
        start+=1
        end-=1

class Transaction:
    def __init__(self, id, before, after):
        self.id = id
        self.before = before
        self.after = after

    def changed(self):
        """Return whether the transaction resulted in a changed balance."""
        if self.before == self.after:
            return False
        else :
            return True

    def report(self):
        """Return a string describing the transaction.

        >>> Transaction(3, 20, 10).report()
        '3: decreased 20->10'
        >>> Transaction(4, 20, 50).report()
        '4: increased 20->50'
        >>> Transaction(5, 50, 50).report()
        '5: no change'
        """
        msg = 'no change'
        if self.changed():
            if self.before > self.after:
                msg = 'decreased ' + str(self.before)+'->'+str(self.after)
            else :
                msg = 'increased ' + str(self.before) + '->' + str(self.after)
        return str(self.id) + ': ' + msg

class Account:
    """A bank account that tracks its transaction history.

    >>> a = Account('Eric')
    >>> a.deposit(100)    # Transaction 0 for a
    100
    >>> b = Account('Erica')
    >>> a.withdraw(30)    # Transaction 1 for a
    70
    >>> a.deposit(10)     # Transaction 2 for a
    80
    >>> b.deposit(50)     # Transaction 0 for b
    50
    >>> b.withdraw(10)    # Transaction 1 for b
    40
    >>> a.withdraw(100)   # Transaction 3 for a
    'Insufficient funds'
    >>> len(a.transactions)
    4
    >>> len([t for t in a.transactions if t.changed()])
    3
    >>> for t in a.transactions:
    ...     print(t.report())
    0: increased 0->100
    1: decreased 100->70
    2: increased 70->80
    3: no change
    >>> b.withdraw(100)   # Transaction 2 for b
    'Insufficient funds'
    >>> b.withdraw(30)    # Transaction 3 for b
    10
    >>> for t in b.transactions:
    ...     print(t.report())
    0: increased 0->50
    1: decreased 50->40
    2: no change
    3: decreased 40->10
    """

    # *** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        self.counter = -1
        self.transactions = []

    def id_gene(self):
        self.counter+=1
        yield self.counter

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """
        pre = self.balance
        self.balance = self.balance + amount
        self.transactions.append(Transaction(next(self.id_gene()),pre, self.balance))
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount, add the withdraw
        to the transaction history, and return the new balance.
        """
        if amount > self.balance:
            self.transactions.append(Transaction(next(self.id_gene()), self.balance, self.balance))
            return 'Insufficient funds'
        pre = self.balance
        self.balance = self.balance - amount
        self.transactions.append(Transaction(next(self.id_gene()), pre, self.balance))
        return self.balance

class Email:
    """An email has the following instance attributes:

        msg (str): the contents of the message
        sender (Client): the client that sent the email
        recipient_name (str): the name of the recipient (another client)
    """
    def __init__(self, msg, sender, recipient_name):
        self.msg = msg
        self.sender = sender
        self.recipient_name = recipient_name

class Server:
    """Each Server has one instance attribute called clients that is a
    dictionary from client names to client objects.
    """
    def __init__(self):
        self.clients = {}

    def send(self, email):
        """Append the email to the inbox of the client it is addressed to."""
        self.clients[email.recipient_name].inbox.append(email)

    def register_client(self, client):
        """Add a client to the dictionary of clients."""
        self.clients[client.name] = client

class Client:
    """A client has a server, a name (str), and an inbox (list).

    >>> s = Server()
    >>> a = Client(s, 'Alice')
    >>> b = Client(s, 'Bob')
    >>> a.compose('Hello, World!', 'Bob')
    >>> b.inbox[0].msg
    'Hello, World!'
    >>> a.compose('CS 61A Rocks!', 'Bob')
    >>> len(b.inbox)
    2
    >>> b.inbox[1].msg
    'CS 61A Rocks!'
    >>> b.inbox[1].sender.name
    'Alice'
    """
    def __init__(self, server, name):
        self.inbox = []
        self.server = server
        self.name = name
        server.register_client(self)

    def compose(self, message, recipient_name):
        """Send an email with the given message to the recipient."""
        email = Email(message, self, recipient_name)
        self.server.send(email)

def make_change(amount, coins):
    """Return a list of coins that sum to amount, preferring the smallest coins
    available and placing the smallest coins first in the returned list.

    The coins argument is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> make_change(2, {2: 1})
    [2]
    >>> make_change(2, {1: 2, 2: 1})
    [1, 1]
    >>> make_change(4, {1: 2, 2: 1})
    [1, 1, 2]
    >>> make_change(4, {2: 1}) == None
    True

    >>> coins = {2: 2, 3: 2, 4: 3, 5: 1}
    >>> make_change(4, coins)
    [2, 2]
    >>> make_change(8, coins)
    [2, 2, 4]
    >>> make_change(25, coins)
    [2, 3, 3, 4, 4, 4, 5]
    >>> coins[8] = 1
    >>> make_change(25, coins)
    [2, 2, 4, 4, 5, 8]
    """
    if not coins:
        return None
    smallest = min(coins)
    rest = remove_one(coins, smallest)
    if amount < smallest:
        return None
    elif amount == smallest:
        return [smallest]
    else:
        temp = make_change(amount-smallest, rest)
        if not temp:
            return make_change(amount, rest)
        else :
            return [smallest]+temp

class ChangeMachine:
    """A change machine holds a certain number of coins, initially all pennies.
    The change method adds a single coin of some denomination X and returns a
    list of coins that sums to X. The machine prefers to return the smallest
    coins available. The total value in the machine never changes, and it can
    always make change for any coin (perhaps by returning the coin passed in).

    The coins attribute is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> m = ChangeMachine(2)
    >>> m.coins == {1: 2}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.coins == {2: 1}
    True
    >>> m.change(2)
    [2]
    >>> m.coins == {2: 1}
    True
    >>> m.change(3)
    [3]
    >>> m.coins == {2: 1}
    True

    >>> m = ChangeMachine(10) # 10 pennies
    >>> m.coins == {1: 10}
    True
    >>> m.change(5) # takes a nickel & returns 5 pennies
    [1, 1, 1, 1, 1]
    >>> m.coins == {1: 5, 5: 1} # 5 pennies & a nickel remain
    True
    >>> m.change(3)
    [1, 1, 1]
    >>> m.coins == {1: 2, 3: 1, 5: 1}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.change(2) # not enough 1's remaining; return a 2
    [2]
    >>> m.coins == {2: 1, 3: 1, 5: 1}
    True
    >>> m.change(8) # cannot use the 2 to make 8, so use 3 & 5
    [3, 5]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(1) # return the penny passed in (it's the smallest)
    [1]
    >>> m.change(9) # return the 9 passed in (no change possible)
    [9]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(10)
    [2, 8]
    >>> m.coins == {10: 1}
    True

    >>> m = ChangeMachine(9)
    >>> [m.change(k) for k in [2, 2, 3]]
    [[1, 1], [1, 1], [1, 1, 1]]
    >>> m.coins == {1: 2, 2: 2, 3: 1}
    True
    >>> m.change(5) # Prefers [1, 1, 3] to [1, 2, 2] (more pennies)
    [1, 1, 3]
    >>> m.change(7)
    [2, 5]
    >>> m.coins == {2: 1, 7: 1}
    True
    """
    def __init__(self, pennies):
        self.coins = {1: pennies}

    def change(self, coin):
        """Return change for coin, removing the result from self.coins."""
        self.coins[coin] = self.coins.get(coin, 0)+1
        result = make_change(coin, self.coins)
        for c in result:
            self.coins = remove_one(self.coins, c)
        return result

class <name>:
    <suite>

class Account:

    interest = 0.02 # 类属性

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        self.balance = self.balance + amount
        return self.balance  
tom = Account('Tom')
jim = Account('Jim')
print(tom.interest)
print(jim.interest)

tom.interest = 0.08
Account.interest = 0.04

tom.deposit(10)

print(type(Account.deposit))
print(type(tom.deposit))

Account.deposit(tom, 1001)
tom.deposit(1007)

print(list)
s = list(range(3))
print(type(s))

class Account:   # 一个类以class开头，并给他命名
    
    def __init__(self, account_holder):
        '''
        定义创建类的新实例时会发生什么，即给予对象属性
        一般使用方法名__init__来构造一个类的实例，调用时自动执行, 该方法有时也被称为构造方法
        将新实例称为self，并给它分配属性，其中，account_holder是调用时传入的内容
        '''
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        '''
        deposit方法调用两个参数
        self： self是该方法被调用时的类的实例
        amount：添加的余额
        '''
        self.balance = self.balance + amount
        return self.balance   # 出现输出时的情况，若没有return则返回None

    def withdraw(self, amount):
        if amount > self.balance:   # 引用balance时要加.,因为其是对象的一个属性
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance

a = Account('Alan')
print(a.holder)
print(a.balance)

a.balance = 12   # 已存在的属性可以被更改
b = Account('Ada')
b.balance = 20
a.backup = b   # 新属性可以在任何时候添加
print(a.backup.balance)

print(a is a)
print(a is not b)
c = a
print(a is c)

tom = Account('Tom')
print(tom.deposit(100))  # 调用时只需要一个参数, 方法会自动绑定到self(这里是tom)

def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """

    for i in range(len(s)):
        if type(s[i])==list:
            deep_map(f,s[i])
        else:
            s[i]=f(s[i])

def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = mobile(arm(3, t), arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(mobile(arm(1, v), arm(1, p)))
    False
    >>> balanced(mobile(arm(1, p), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    if is_planet(m):
        return True
    else:
        torque_left = length(left(m))*total_mass(end(left(m)))
        torque_right = length(right(m))*total_mass(end(right(m)))
        return torque_left == torque_right and balanced(end(left(m))) and balanced(end(right(m)))

def evens(start, end):
    even = start + (start%2)
    while even<end:
        yield even
        even+=2

if __name__ == "__main__":
    t = evens(2,10)
    for i in t:
        print(i)

def countdown(k):
    if k>0:
        yield k
        yield from countdown(k-1)
        '''
        等价于 
        for i in countdown(k-1):
            yield i
        '''
    else:
        yield 'Blast off'
if __name__ == "__main__":
    t = countdown(3)
    for i in t:
        print(i)

def prefixes(s):
    if s:
        yield from prefixes(s[:-1])
        yield s
def substrings(s):
    if s:
        yield from prefixes(s)
        yield from substrings(s[1:])
if __name__ == "__main__":
    print(list(prefixes("both")))
    print(list(substrings("top")))

def partitions(n,m):
    if n<0 or m==0:
        return []
    else:
        exact_match = []
        if n==m:
            exact_match = [str(m)]
        with_m = [p+'+'+str(m) for p in partitions(n-m,m)]
        without_m = partitions(n,m-1)
        return exact_match+with_m+without_m
if __name__ == "__main__":
    for p in partitions(6,4):
        print(p)

def partitions(n,m):
    if n>0 and m>0:
        if n==m:
            yield str(m)
        for p in partitions(n-m,m):
            yield p+'+'+str(m)
        yield from partitions(n,m-1)
if __name__ == "__main__":
    t = partitions(6,4)
    for p in range(5):
        print(next(t))

s = [[1,2],3,4,5]
t = iter(s)
u = iter(s)
print("t:",next(t))
print("u:",next(u))
print("t:",next(t))
list(t)
print(next(t))

d = {'one':1, 'two':2, 'three':3}
d['zero'] = 0
# 遍历键
k = iter(d.keys()) # iter(d)
print(next(k))
# 遍历值
v = iter(d.values())
print(next(v))
# 遍历键值对
i = iter(d.items()) # 以元组形式迭代
print(next(i))

r = range(3,6)
ri = iter(r)
for i in ri:
    print(i)
for i in ri:
    print(i)

bcd = ['b', 'c', 'd']
m = map(lambda x: x.upper(), bcd) # 返回一个迭代器
print(next(m))
print(next(m))
print(next(m))

def double(x):
    print(x, '=>',2*x)
    return 2*x
m = map(double, range(3,7))
f = lambda y: y>=10
t = filter(f,m) # 仅遍历满足f函数下的返回值
list(filter(f,m)) # 将所有可能的返回值存入列表

print(list(zip([1,2],[3,4])))

print(list(zip([1,2],[3,4,5])))

print(list(zip([1,2],[3,4,5], [6,7])))

def palindrome(s):
    # >>> palindrome([3,1,4,1,5])
    # False
    # >>> palindrome([3,1,4,1,3])
    # True
    # >>> palindrome('seveneves')
    # True
    return all([a==b for a,b in zip(s,reversed(s))])
if __name__ == '__main__':
    print(palindrome([3,1,4,1,3]))
    print(palindrome('seveneves'))