cs61a：从入土到入门

Readme

版本：CS 61A Fall 2021

记录homework, lab and projects.

github地址：liuydd/cs61a-2021fall (github.com)

HW 01:Control

可能刚开始，连ok用的都不太熟练，所以hw01做的比较水…

cs61a每一题都会给出大概的模板，(是为了避免让你造轮子吗

Q2:A Plus Abs B

Fill in the blanks in the following function for adding a to the absolute value of b, without calling abs. You may not modify any of the provided code other than the two blanks.

def a_plus_abs_b(a, b):
    """Return a+abs(b), but without calling abs.

    >>> a_plus_abs_b(2, 3)
    5
    >>> a_plus_abs_b(2, -3)
    5
    """
    if b < 0:
        f = _____
    else:
        f = _____
    return f(a, b)

Use Ok to test your code:

python3 ok -q a_plus_abs_b

my answer:

def a_plus_abs_b(a, b):
    """Return a+abs(b), but without calling abs.

    >>> a_plus_abs_b(2, 3)
    5
    >>> a_plus_abs_b(2, -3)
    5
    """
    if b < 0:
        f = a-b
    else:
        f = a+b
    return f(a, b)

Q3: Two of Three

Write a function that takes three positive numbers as arguments and returns the sum of the squares of the two smallest numbers.Use only a single line for the body of the function.

def two_of_three(x, y, z):
    """Return a*a + b*b, where a and b are the two smallest members of the
    positive numbers x, y, and z.

    >>> two_of_three(1, 2, 3)
    5
    >>> two_of_three(5, 3, 1)
    10
    >>> two_of_three(10, 2, 8)
    68
    >>> two_of_three(5, 5, 5)
    50
    """
    return _____

Hint: Consider using the max or min function:

>>> max(1,2,3)
3
>>> min(-1,-2,-3)
-3

Use Ok to test your code:

python3 ok -q two_of_three

my answer:

def two_of_three(x, y, z):
    """Return a*a + b*b, where a and b are the two smallest members of the
    positive numbers x, y, and z.

    >>> two_of_three(1, 2, 3)
    5
    >>> two_of_three(5, 3, 1)
    10
    >>> two_of_three(10, 2, 8)
    68
    >>> two_of_three(5, 5, 5)
    50
    """
    return x*x+y*y+z*z-max(x,y,z)*max(x,y,z)

Q4: Largest Factor

Write a function that takes an integer n that is greater than 1 andreturns the largest integer that is smaller than n and evenly divides n.

def largest_factor(n):
    """Return the largest factor of n that is smaller than n.

    >>> largest_factor(15) # factors are 1, 3, 5
    5
    >>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
    40
    >>> largest_factor(13) # factor is 1 since 13 is prime
    1
    """
    "*** YOUR CODE HERE ***"

Hint: To check if b evenly divides a, you can use the expression a % b == 0, which can be read as, “the remainder of dividing a by b is 0.”

Use Ok to test your code:

python3 ok -q largest_factor

my answer:

def largest_factor(n):
    """Return the largest factor of n that is smaller than n.

    >>> largest_factor(15) # factors are 1, 3, 5
    5
    >>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
    40
    >>> largest_factor(13) # factor is 1 since 13 is prime
    1
    """
    "*** YOUR CODE HERE ***"
    i=n-1
    while n%i!=0:
        i=i-1
    print(i)

Q6: Hailstone

Douglas Hofstadter’s Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

1. Pick a positive integer n as the start.
2. If n is even, divide it by 2.
3. If n is odd, multiply it by 3 and add 1.
4. Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried – nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

This sequence of values of n is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"

Hailstone sequences can get quite long! Try 27. What’s the longest you can find?

Use Ok to test your code:

python3 ok -q hailstone

my answer:

#hw01 Q6:Hailstone
def hailstone(n):
    i=1
    while n!=1:
        print(int(n))
        if n%2==0:
            n=n/2
        else:
            n=n*3+1
        i=i+1
    print(1)
    #print(int(i))

Lab 01: Variables & Functions,Control

Q4： Falling Factorial

Let’s write a function falling, which is a “falling” factorial that takes two arguments, n and k, and returns the product of k consecutive numbers, starting from n and working downwards. When k is 0, the function should return 1.

def falling(n, k):
    """Compute the falling factorial of n to depth k.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    >>> falling(4, 0)
    1
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q falling

my answer:

def falling(n, k):
    """Compute the falling factorial of n to depth k.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    >>> falling(4, 0)
    1
    """
    "*** YOUR CODE HERE ***"
    '''  if(k==0):
        temp=1
    else:
        temp=n
        while(k!=1):
            k-=1
            temp*=(n-1)
            n-=1
    return temp    '''
    total,stop=1,n-k
    while n>stop:
        total,n=total*n,n-1
    return total                #感觉python有很多都和C++不同，而我的思维还在C++上面

Q5: Sum Digits

Write a function that takes in a nonnegative integer and sums its digits. (Using floor division and modulo might be helpful here!)

def sum_digits(y):
    """Sum all the digits of y.

    >>> sum_digits(10) # 1 + 0 = 1
    1
    >>> sum_digits(4224) # 4 + 2 + 2 + 4 = 12
    12
    >>> sum_digits(1234567890)
    45
    >>> a = sum_digits(123) # make sure that you are using return rather than print
    >>> a
    6
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q sum_digits

my answer:

def sum_digits(y):
    """Sum all the digits of y.

    >>> sum_digits(10) # 1 + 0 = 1
    1
    >>> sum_digits(4224) # 4 + 2 + 2 + 4 = 12
    12
    >>> sum_digits(1234567890)
    45
    >>> a = sum_digits(123) # make sure that you are using return rather than print
    >>> a
    6
    """
    "*** YOUR CODE HERE ***"
    total=y%10
    while(y!=0):
        y=y//10
        total+=y%10
    return total         #这个过的挺轻松的

Q7: Double Eights

Write a function that takes in a number and determines if the digits contain two
adjacent 8s.

def double_eights(n):
    """Return true if n has two eights in a row.
    >>> double_eights(8)
    False
    >>> double_eights(88)
    True
    >>> double_eights(2882)
    True
    >>> double_eights(880088)
    True
    >>> double_eights(12345)
    False
    >>> double_eights(80808080)
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q double_eights

my answer:

def double_eights(n):
    """Return true if n has two eights in a row.
    >>> double_eights(8)
    False
    >>> double_eights(88)
    True
    >>> double_eights(2882)
    True
    >>> double_eights(880088)
    True
    >>> double_eights(12345)
    False
    >>> double_eights(80808080)
    False
    """
    "*** YOUR CODE HERE ***"
    while(n!=0):
        t=n%10
        if(t==8):
            n//=10
            _t=n%10
            if(_t==8):
                return True
            else:
                return False
        else:
            n//=10
    return False    #最后这里不要忘了还有个return，针对while循环走完的情况

Project1：The Game of Hog

Rules

• Sow Sad: If any of the dice outcomes is a 1, the current player’s score for the turn is 1.
  • 所有骰子中有一个数为1，则得1分
• Picky Piggy: A player who chooses to roll zero dice scores the nth digit of the decimal expansion of 1/7 (0.14285714…), where n is the opponent’s score. As a special case, if n is 0, the player scores 7 points.
  • 玩家选择不掷骰子，则对手分数为几，他的分数就为1/7的第几位数字
• Hog Pile: After points for the turn are added to the current player’s score, if the players’ scores are the same, the current player’s score doubles.
  • 如果当前玩家掷骰子后的分数与对手相同，则当前玩家分数翻倍

Phase1: Simulator

In the first phase, you will develop a simulator for the game of Hog.

Problem 0

• a fair dice：正常的骰子
• a test dice：在输入进去的数中选一个输出

Problem 1

num_rolls：要掷的骰子数量

dice：所掷的骰子情况

cs61a的project会先设置一个unlocking环节，以填空的形式确保你真的理解了题目的意思

居然还会给你debugging tips，有点感动

www我破防了，为什么unlocking只能用vscode交互而不能用git

刚夸了这个理解程序的功能，结果在这耗了四五十分钟…

讲个笑话：

死者：lyd

死因：python3.9 -q 01 -u –local的50+cases

太好了，不是50+，只有几个cases

attention：令a=make_test_dice(4,1,2,6)，roll_dice(3,a)输出后，roll_dice(1,a)中a的值会接着来。

anyway，Berkerly的这门课程让我喜欢的就在这，给出了error、是哪个suite出了问题、过了多少个cases

又到了愉快的debug时间

好开心！！！虽然是个很简单的函数，虽然不知道前几次为什么过不了…

my answer:

def roll_dice(num_rolls, dice=six_sided):
    """Simulate rolling the DICE exactly NUM_ROLLS > 0 times. Return the sum of
    the outcomes unless any of the outcomes is 1. In that case, return 1.

    num_rolls:  The number of dice rolls that will be made.
    dice:       A function that simulates a single dice roll outcome.
    """
    # These assert statements ensure that num_rolls is a positive integer.
    assert type(num_rolls) == int, 'num_rolls must be an integer.'
    assert num_rolls > 0, 'Must roll at least once.'
    # BEGIN PROBLEM 1
    "*** YOUR CODE HERE ***"
    sum,f=0,0
    num_of_rolls=1
    while num_of_rolls<=num_rolls:
        c=dice()
        sum+=c
        num_of_rolls+=1
        if c==1:
            f=1
    if f==1:
        return 1
    else:
        return sum        
    # END PROBLEM 1

Problem 2

写的比较水…用枚举的方法直接AC

def picky_piggy(score):
    """Return the points scored from rolling 0 dice.

    score:  The opponent's current score.
    """
    # BEGIN PROBLEM 2
    "*** YOUR CODE HERE ***"
    if score%6==0:
        return 7
    else:
        s=score%6
        if s==1:
            return 1
        elif s==2:
            return 4
        elif s==3:
            return 2
        elif s==4:
            return 8
        elif s==5:
            return 5
    # END PROBLEM 2

Problem 3

函数take_turn：综合考虑roll_dice和picky_piggy情况。即若num_rolls>0，按roll_dice考虑，若num_rolls=0，按picky_piggy考虑

def take_turn(num_rolls, opponent_score, dice=six_sided, goal=GOAL_SCORE):
    """Simulate a turn rolling NUM_ROLLS dice, which may be 0 in the case
    of a player using Picky Piggy.
    Return the points scored for the turn by the current player.

    num_rolls:       The number of dice rolls that will be made.
    opponent_score:  The total score of the opponent.
    dice:            A function that simulates a single dice roll outcome.
    goal:            The goal score of the game.
    """
    # Leave these assert statements here; they help check for errors.
    assert type(num_rolls) == int, 'num_rolls must be an integer.'
    assert num_rolls >= 0, 'Cannot roll a negative number of dice in take_turn.'
    assert num_rolls <= 10, 'Cannot roll more than 10 dice.'
    assert opponent_score < goal, 'The game should be over.'
    # BEGIN PROBLEM 3
    "*** YOUR CODE HERE ***"
    if num_rolls==0:
        return picky_piggy(opponent_score)
    else:
        return roll_dice(num_rolls,dice)
    # END PROBLEM 3

Problem 4

函数hog_pile：return的是current player增加的points，而非总points

如果player_score!=opponent_score，则return 0；反之，return player_score

def hog_pile(player_score, opponent_score):
    """Return the points scored by player due to Hog Pile.

    player_score:   The total score of the current player.
    opponent_score: The total score of the other player.
    """
    # BEGIN PROBLEM 4
    "*** YOUR CODE HERE ***"
    if player_score!=opponent_score:
        return 0
    else:
        return player_score
    # END PROBLEM 4

Problem 5

def play(strategy0, strategy1, score0=0, score1=0, dice=six_sided,
         goal=GOAL_SCORE, say=silence):
    """Simulate a game and return the final scores of both players, with Player
    0's score first, and Player 1's score second.

    A strategy is a function that takes two total scores as arguments (the
    current player's score, and the opponent's score), and returns a number of
    dice that the current player will roll this turn.

    strategy0:  The strategy function for Player 0, who plays first.
    strategy1:  The strategy function for Player 1, who plays second.
    score0:     Starting score for Player 0
    score1:     Starting score for Player 1
    dice:       A function of zero arguments that simulates a dice roll.
    goal:       The game ends and someone wins when this score is reached.
    say:        The commentary function to call at the end of the first turn.
    """
    who = 0  # Who is about to take a turn, 0 (first) or 1 (second)
    # BEGIN PROBLEM 5
    "*** YOUR CODE HERE ***"
    while score0<goal and score1<goal:
        if next_player(who)==1:
            score0+=take_turn(strategy0(score0,score1), score1, dice, goal)
            a=hog_pile(score0,score1)
            score0+=a
            who=1
        elif next_player(who)==0:
            score1+=take_turn(strategy1(score1,score0),score0,dice,goal) #这里如果继续的话可能会有score0>goal而游戏还没停止，所以应该增加判断
            b=hog_pile(score1,score0)
            score1+=b
            who=0
    # END PROBLEM 5
    # (note that the indentation for the problem 6 prompt (***YOUR CODE HERE***) might be misleading)
    # BEGIN PROBLEM 6
    "*** YOUR CODE HERE ***"
    # END PROBLEM 6
    return score0, score1

Phase 2：Commentary

这个phase不重要吧，我就不改了（暴论

Problem 6

比较简单，不知为何，-u环节我的line2过不了，总报not quite。

Problem 7

…比较离谱

to be debug

执行了python3 hog_gui.py后发现bug：

• 底下的文字不会消失，本应该报历史最大新增，但却报的是当前的points，如

  8 point(s)! That’s a record gain for Player 0! 8 point(s)! That’s a record gain for Player 1!

Phase3：Strategies

Problem 8

a new piece of Python syntax

We would like to write a function that accepts an arbitrary number of arguments, and then calls another function using exactly those arguments. Here’s how it works.

Instead of listing formal parameters for a function, you can write *args, which represents all of the arguments that get passed into the function. We can then call another function with these same arguments by passing these *args into this other function. For example:

>>>def printed(f):
		def print_and_return(*args):
         result=f(*args)
         print('Result:',result)
         return result
     return print_and_return

简单的循环计算sum

def make_averaged(original_function, trials_count=1000):
    """Return a function that returns the average value of ORIGINAL_FUNCTION
    called TRIALS_COUNT times.

    To implement this function, you will have to use *args syntax, a new Python
    feature introduced in this project.  See the project description.

    >>> dice = make_test_dice(4, 2, 5, 1)
    >>> averaged_dice = make_averaged(roll_dice, 1000)
    >>> averaged_dice(1, dice)
    3.0
    """
    # BEGIN PROBLEM 8
    "*** YOUR CODE HERE ***"
    def average(*args):
        dice_nums=1
        sum=0
        while dice_nums<=trials_count:
            sum+=original_function(*args)
            dice_nums+=1
        return sum/trials_count
    return average
    # END PROBLEM 8

Problem 9

注意调用含*args函数的方法

def max_scoring_num_rolls(dice=six_sided, trials_count=1000):
    """Return the number of dice (1 to 10) that gives the highest average turn score
    by calling roll_dice with the provided DICE a total of TRIALS_COUNT times.
    Assume that the dice always return positive outcomes.

    >>> dice = make_test_dice(1, 6)
    >>> max_scoring_num_rolls(dice)
    1
    """
    # BEGIN PROBLEM 9
    "*** YOUR CODE HERE ***"
    #要用到make_averaged和roll_dice(num_rolls,dice)
    max_ave,num=0,1
    flag=1
    while num<=10:
        a=make_averaged(roll_dice,trials_count)
        b=a(num,dice)
        if max_ave<b:
            max_ave=b
            flag=num
        num+=1
    return flag
    # END PROBLEM 9

Problem 10

def picky_piggy_strategy(score, opponent_score, cutoff=8, num_rolls=6):
    """This strategy returns 0 dice if that gives at least CUTOFF points, and
    returns NUM_ROLLS otherwise.
    """
    # BEGIN PROBLEM 10
    if picky_piggy(opponent_score)>=cutoff:
        return 0
    else:
        return num_rolls
    # END PROBLEM 10

Problem 11

def hog_pile_strategy(score, opponent_score, cutoff=8, num_rolls=6):
    """This strategy returns 0 dice when this would result in Hog Pile taking
    effect. It also returns 0 dice if it gives at least CUTOFF points.
    Otherwise, it returns NUM_ROLLS.
    """
    # BEGIN PROBLEM 11
    a=hog_pile(score+picky_piggy(opponent_score),opponent_score)
    if a!=0:  #触发了
        return 0
    elif picky_piggy(opponent_score)>=cutoff:
        return 0
    else:
        return num_rolls
    # END PROBLEM 11

Some feelings when finishing the project

写的过程比较痛苦。

这个痛苦主要在于语言。毕竟是第一次做project，还是全英文，有好几处都不能理解，还好有部分cases来帮助我理解这个函数的作用。

写的过程有部分借鉴，但95%均为本人完成（有的看上去就写的很烂的代码除了你还有谁会写出来啊喂

写完的成就感还是很高的，高于写的过程中感受到的痛苦。

喜欢这种一个problem一个problem给我让我完成的，等我一步步写完后发现，我居然也能写个小游戏出来了（x

课程本身帮你写好了GUI，代码每完成一部分，就可以执行python3 hog_gui.py来试试功能。

挺好的，我就喜欢这种一看就知道重点在哪的project。

HW 02: Higher-Order Functions

Required questions

from operator import add, mul

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1

Q1：Product

The summation(n, term) function from the higher-order functions lecture adds up term(1) + ... + term(n). Write a similar function called product that returns term(1) * ... * term(n).

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term:  a function that takes one argument to produce the term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    "*** YOUR CODE HERE ***"

my answer:

def product(n, term):
    a,pro=1,1
    while a<=n:
        pro*=term(a)
        a+=1
    return pro

Q2：Accumulate

Let’s take a look at how summation and product are instances of a more general function called accumulate, which we would like to implement:

def accumulate(merger, base, n, term):
    """Return the result of merging the first n terms in a sequence and base.
    The terms to be merged are term(1), term(2), ..., term(n). merger is a
    two-argument commutative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    >>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
    >>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
    576
    >>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
    16
    """
    "*** YOUR CODE HERE ***"

After implementing accumulate, show how summation and product can both be defined as function calls to accumulate.

Important: You should have a single line of code (which should be a return statement) in each of your implementations for summation_using_accumulate and product_using_accumulate, which the syntax check will check for.

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    """
    "*** YOUR CODE HERE ***"

def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    """
    "*** YOUR CODE HERE ***"

my answer：

def accumulate(merger, base, n, term):
    a=1
    while a<=n:
         base=merger(base,term(a))
         a+=1
    return base

def summation_using_accumulate(n, term):
    return accumulate(add,1,n,term)

def product_using_accumulate(n, term):
    return accumulate(mul,1,n,term)

一点点感触：果然简洁的才是最美的

Q3：Church numerals（just for fun question)

This question is out of scope for 61A. You can try it if you want an extra challenge, but it’s just a puzzle that is not required or recommended at all. Almost all students will skip it, and that’s fine.

to be debug…

Lab2：Higher-Order Functions，Lambda Expressions

Q3：Lambdas and Currying

We can transform multiple-argument functions into a chain of single-argument, higher order functions by taking advantage of lambda expressions. For example, we can write a function f(x, y) as a different function g(x)(y). This is known as currying. It’s useful when dealing with functions that take only single-argument functions. We will see some examples of these later on.

Write a function lambda_curry2 that will curry any two argument function using lambdas. Refer to the textbook for more details about currying.

Your solution to this problem should fit entirely on the return line. You can try first writing a solution without the restriction, and then rewriting it into one line after.

If the syntax check isn’t passing: Make sure you’ve removed the line containing "***YOUR CODE HERE***" so that it doesn’t get treated as part of the function for the syntax check.

def lambda_curry2(func):
    """
    Returns a Curried version of a two-argument function FUNC.
    >>> from operator import add, mul, mod
    >>> curried_add = lambda_curry2(add)
    >>> add_three = curried_add(3)
    >>> add_three(5)
    8
    >>> curried_mul = lambda_curry2(mul)
    >>> mul_5 = curried_mul(5)
    >>> mul_5(42)
    210
    >>> lambda_curry2(mod)(123)(10)
    3
    """
    "*** YOUR CODE HERE ***"
    return ______

Use Ok to test your code:

python3 ok -q lambda_curry2

my answer：

def lambda_curry2(func):
    return lambda x:lambda y:func(x,y)

Q4：Count van Count

Consider the following implementations of count_factors and count_primes:

The implementations look quite similar! Generalize this logic by writing a function count_cond, which takes in a two-argument predicate function condition(n, i). count_cond returns a one-argument function that takes in n, which counts all the numbers from 1 to n that satisfy condition when called.

def count_cond(condition):
    """Returns a function with one parameter N that counts all the numbers from
    1 to N that satisfy the two-argument predicate function Condition, where
    the first argument for Condition is N and the second argument is the
    number from 1 to N.

    >>> count_factors = count_cond(lambda n, i: n % i == 0)
    >>> count_factors(2)   # 1, 2
    2
    >>> count_factors(4)   # 1, 2, 4
    3
    >>> count_factors(12)  # 1, 2, 3, 4, 6, 12
    6

    >>> is_prime = lambda n, i: count_factors(i) == 2
    >>> count_primes = count_cond(is_prime)
    >>> count_primes(2)    # 2
    1
    >>> count_primes(3)    # 2, 3
    2
    >>> count_primes(4)    # 2, 3
    2
    >>> count_primes(5)    # 2, 3, 5
    3
    >>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q count_cond

my answer：

def count_cond(condition):
    def count_func(n):
        i=1
        count=0
        while i<=n:
            if condition(n,i):
                count+=1
            i+=1
        return count
    return count_func

Q7：Composite Identity Function

optional

Write a function that takes in two single-argument functions, f and g, and returns another function that has a single parameter x. The returned function should return True if f(g(x)) is equal to g(f(x)). You can assume the output of g(x) is a valid input for f and vice versa. Try to use the composer function defined below for more HOF practice.

def composer(f, g):
    """Return the composition function which given x, computes f(g(x)).

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2
    >>> a1 = composer(square, add_one)   # (x + 1)^2
    >>> a1(4)
    25
    >>> mul_three = lambda x: x * 3      # multiplies 3 to x
    >>> a2 = composer(mul_three, a1)    # ((x + 1)^2) * 3
    >>> a2(4)
    75
    >>> a2(5)
    108
    """
    return lambda x: f(g(x))

def composite_identity(f, g):
    """
    Return a function with one parameter x that returns True if f(g(x)) is
    equal to g(f(x)). You can assume the result of g(x) is a valid input for f
    and vice versa.

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2
    >>> b1 = composite_identity(square, add_one)
    >>> b1(0)                            # (0 + 1)^2 == 0^2 + 1
    True
    >>> b1(4)                            # (4 + 1)^2 != 4^2 + 1
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q composite_identity

my answer：

def composite_identity(f, g):
    def judge(x):
        if composer(f,g)(x)==composer(g,f)(x):
            return True
        else: 
            return False
    return judge

Q8：I Heard You Liked Functions…

optional

Define a function cycle that takes in three functions f1, f2, f3, as arguments. cycle will return another function that should take in an integer argument n and return another function. That final function should take in an argument x and cycle through applying f1, f2, and f3 to x, depending on what n was. Here’s what the final function should do to x for a few values of n:

• n = 0, return x
• n = 1, apply f1 to x, or return f1(x)
• n = 2, apply f1 to x and then f2 to the result of that, or return f2(f1(x))
• n = 3, apply f1 to x, f2 to the result of applying f1, and then f3 to the result of applying f2, or f3(f2(f1(x)))
• n = 4, start the cycle again applying f1, then f2, then f3, then f1 again, or f1(f3(f2(f1(x))))
• And so forth.

Hint: most of the work goes inside the most nested function.

def cycle(f1, f2, f3):
    """Returns a function that is itself a higher-order function.

    >>> def add1(x):
    ...     return x + 1
    >>> def times2(x):
    ...     return x * 2
    >>> def add3(x):
    ...     return x + 3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q cycle

my answer：

def cycle(f1, f2, f3):
    def func1(x):
        def func2(x):
            def func3(x):
                return f1(x)
            return f2(f1(x))
        return f3(f2(f1(x)))
    return func1

Disc 2：Higher-Order Functions，Self Reference

Q1：Make Keeper

def make_keeper(n):
    """Returns a function which takes one parameter cond and prints
    out all integers 1..i..n where calling cond(i) returns True.

    >>> def is_even(x):
    ...     # Even numbers have remainder 0 when divided by 2.
    ...     return x % 2 == 0
    >>> make_keeper(5)(is_even)
    2
    4
    """
    "*** YOUR CODE HERE ***"
    def func(cond):
        i=1
        while i<=n:
            if cond(i):
                print(i)
            i+=1
    return func

Q5：Print N

def print_n(n):
    """
    >>> f = print_n(2)
    >>> f = f("hi")
    hi
    >>> f = f("hello")
    hello
    >>> f = f("bye")
    done
    >>> g = print_n(1)
    >>> g("first")("second")("third")
    first
    done
    done
    <function inner_print>
    """
    def inner_print(x):
        if n<=0:
            print("done")
        else:
            print(x)
        return print_n(n-1)
    return inner_print

Q8：Match Maker

optional

def match_k(k):
    """ Return a function that checks if digits k apart match

    >>> match_k(2)(1010)
    True
    >>> match_k(2)(2010)
    False
    >>> match_k(1)(1010)
    False
    >>> match_k(1)(1)
    True
    >>> match_k(1)(2111111111111111)
    False
    >>> match_k(3)(123123)
    True
    >>> match_k(2)(123123)
    False
    """
    def func(x):
        i=1
        while x!=0 and x//(10**k)!=0:
            if x%10==x//(10**k)%10:
                x=x//10
            else: return False
        return True
    return func

Q9：Three Memory & Q10：Natural Chain

咕了…

等能力再强点再来补坑吧

Lab 3：Midterm Review

Q1：Unique Digits

def unique_digits(n):
    """Return the number of unique digits in positive integer n.

    >>> unique_digits(8675309) # All are unique
    7
    >>> unique_digits(1313131) # 1 and 3
    2
    >>> unique_digits(13173131) # 1, 3, and 7
    3
    >>> unique_digits(10000) # 0 and 1
    2
    >>> unique_digits(101) # 0 and 1
    2
    >>> unique_digits(10) # 0 and 1
    2
    """
    "*** YOUR CODE HERE ***"
    i,count=0,0
    while i<10:
        if has_digit(n,i):
            count+=1
        i+=1
    return count
    



def has_digit(n, k):
    """Returns whether K is a digit in N.
    >>> has_digit(10, 1)
    True
    >>> has_digit(12, 7)
    False
    """
    "*** YOUR CODE HERE ***"
    while n!=0:
        if n%10==k:
            return True
        else:
            n=n//10
    return False

Q2：Ordered Digits

def ordered_digits(x):
    """Return True if the (base 10) digits of X>0 are in non-decreasing
    order, and False otherwise.

    >>> ordered_digits(5)
    True
    >>> ordered_digits(11)
    True
    >>> ordered_digits(127)
    True
    >>> ordered_digits(1357)
    True
    >>> ordered_digits(21)
    False
    >>> result = ordered_digits(1375) # Return, don't print
    >>> result
    False

    """
    "*** YOUR CODE HERE ***"
    vis=x%10
    while x!=0:
        x=x//10
        if vis>=x%10:
            vis=x%10
        else: return False
    return True

Q3：K Runner

def get_k_run_starter(n, k):
    """
    >>> get_k_run_starter(123444345, 0) # example from description
    3
    >>> get_k_run_starter(123444345, 1)
    4
    >>> get_k_run_starter(123444345, 2)
    4
    >>> get_k_run_starter(123444345, 3)
    1
    >>> get_k_run_starter(123412341234, 1)
    1
    >>> get_k_run_starter(1234234534564567, 0)
    4
    >>> get_k_run_starter(1234234534564567, 1)
    3
    >>> get_k_run_starter(1234234534564567, 2)
    2
    """
    i = 0
    final = None
    while i<=k:
        while n%10>(n//10)%10 and n//10!=0:
            n=n//10
        final = n%10
        i = i+1
        n = n//10
    return final

Q4：Make Repeater

def make_repeater(func, n):
    """Return the function that computes the nth application of func.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
    5
    """
    "*** YOUR CODE HERE ***"
    def func_n(x):
        if n==0:
            return x
        elif n==1:
            return func(x)
        else:
            i,final_func=2,composer(func,func)
            while i<n:
                final_func=composer(func,final_func)
                i+=1
            return final_func(x)
    return func_n

Q5：Apply Twice

def apply_twice(func):
    """ Return a function that applies func twice.

    func -- a function that takes one argument

    >>> apply_twice(square)(2)
    16
    """
    "*** YOUR CODE HERE ***"
    return make_repeater(func,2)

Q8 Protected Secret

def protected_secret(password, secret, num_attempts):
    """
    Returns a function which takes in a password and prints the SECRET if the password entered matches
    the PASSWORD given to protected_secret. Otherwise it prints "INCORRECT PASSWORD". After NUM_ATTEMPTS
    incorrect passwords are entered, the secret is locked and the function should print "SECRET LOCKED".

    >>> my_secret = protected_secret("correcthorsebatterystaple", "I love UCB", 2)
    >>> my_secret = my_secret("hax0r_1") # 2 attempts left
    INCORRECT PASSWORD
    >>> my_secret = my_secret("correcthorsebatterystaple")
    I love UCB
    >>> my_secret = my_secret("hax0r_2") # 1 attempt left
    INCORRECT PASSWORD
    >>> my_secret = my_secret("hax0r_3") # No attempts left
    SECRET LOCKED
    >>> my_secret = my_secret("correcthorsebatterystaple")
    SECRET LOCKED
    """
    def get_secret(password_attempt):
        "*** YOUR CODE HERE ***"
        if num_attempts>0:
            if password_attempt==password:
                print(secret)
                return get_secret
            else:
                print("INCORRECT PASSWORD")
                num=num_attempts-1
                return protected_secret(password,secret,num)
        else:
            print("SECRET LOCKED")
            return get_secret
    return get_secret

Disc 3：Recursive

Q1：Warm Up：Recursive Multiplication

Hint:5*3=5+(5*2)=5+5+(5*1)

def multiply(m, n):
    """ Takes two positive integers and returns their product using recursion.
    >>> multiply(5, 3)
    15
    """
    "*** YOUR CODE HERE ***"
    if n==1:
        return m
    else:
        return m+multiply(m,n-1)

Q4：Is Prime

def is_prime(n):
    """Returns True if n is a prime number and False otherwise.

    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    "*** YOUR CODE HERE ***"
    def helper(x):
        if x==n:
            return True
        elif n%x==0 or n==1:
            return False
        elif x==n:
            return True
        else: return helper(x+1)
    return helper(2)

Q5：Recursive Hailstone

fail to return the number of elements in the wequence…

def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the number of elements in the sequence.
    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"
    if n%2==0 and n!=1:
        print(n)
        return hailstone(n//2)
    elif n%2!=0 and n!=1:
        print(n)
        return hailstone(n*3+1)
    elif n==1:
        print(n)
        return count_num(n)

Q6：Merge Numbers

def merge(n1, n2):
    """ Merges two numbers by digit in decreasing order
    >>> merge(31, 42)
    4321
    >>> merge(21, 0)
    21
    >>> merge (21, 31) 
    3211
    """
    "*** YOUR CODE HERE ***"
    if n1==0:
        return n2
    elif n2==0:
        return n1
    elif n1%10>n2%10:
        return merge(n1,n2//10)*10+n2%10
    else:
        return merge(n1//10,n2)*10+n1%10

HW03：Recursion，Tree Recursion

Q1：Num eights

def num_eights(pos):
    """Returns the number of times 8 appears as a digit of pos.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr'])
    True
    """
    "*** YOUR CODE HERE ***"
    if pos//10!=0:
        if pos%10==8:
            return num_eights(pos//10)+1
        else:
            return num_eights(pos//10)
    else:
        if pos%10==8:
            return 1
        else:
            return 0

Q2：Ping-pong

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(8)
    8
    >>> pingpong(10)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    -2
    >>> pingpong(30)
    -2
    >>> pingpong(68)
    0
    >>> pingpong(69)
    -1
    >>> pingpong(80)
    0
    >>> pingpong(81)
    1
    >>> pingpong(82)
    0
    >>> pingpong(100)
    -6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr'])
    True
    """
    "*** YOUR CODE HERE ***"
    def helper(current,count,up):
        if n==count:
            return current
        else:
            if (count+1)%8==0 or num_eights(count+1)>0:
                if up:
                    return helper(current+1,count+1,False)
                else:
                    return helper(current-1,count+1,True)
            else:
                if up:
                    return helper(current+1,count+1,True)
                else:
                    return helper(current-1,count+1,False)
    return helper(0,0,True)

Q3：Missing Digits

def missing_digits(n):
    """Given a number a that is in sorted, non-decreasing order,
    return the number of missing digits in n. A missing digit is
    a number between the first and last digit of a that is not in n.
    >>> missing_digits(1248) # 3, 5, 6, 7
    4
    >>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8
    7
    >>> missing_digits(1122) # No missing numbers
    0
    >>> missing_digits(123456) # No missing numbers
    0
    >>> missing_digits(3558) # 4, 6, 7
    3
    >>> missing_digits(35578) # 4, 6
    2
    >>> missing_digits(12456) # 3
    1
    >>> missing_digits(16789) # 2, 3, 4, 5
    4
    >>> missing_digits(4) # No missing numbers between 4 and 4
    0
    >>> from construct_check import check
    >>> # ban while or for loops
    >>> check(HW_SOURCE_FILE, 'missing_digits', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    if n//10==0:
        return 0
    elif n%10>n//10%10:
        return missing_digits(n//10)+n%10-n//10%10-1
    elif n%10==n//10%10:
        return missing_digits(n//10)

Q4：Count coins（to be continued

跳过…

待填坑

Lab 4：Recursion，Tree Recursion，Python Lists

Q2：Summation

def summation(n, term):
    """Return the sum of numbers 1 through n (including n) wíth term applied to each number.
    Implement using recursion!

    >>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
    225
    >>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
    54
    >>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    62
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'summation',
    ...       ['While', 'For'])
    True
    """
    assert n >= 1
    "*** YOUR CODE HERE ***"
    if n==1:
        return term(n)
    else:
        return summation(n-1,term)+term(n)

Q3：Pascal’s Triangle

def pascal(row, column):
    """Returns the value of the item in Pascal's Triangle 
    whose position is specified by row and column.
    >>> pascal(0, 0)
    1
    >>> pascal(0, 5)	# Empty entry; outside of Pascal's Triangle
    0
    >>> pascal(3, 2)	# Row 3 (1 3 3 1), Column 2
    3
    >>> pascal(4, 2)     # Row 4 (1 4 6 4 1), Column 2
    6
    """
    "*** YOUR CODE HERE ***"
    if column>row:
        return 0
    elif column==0 or row==0:
        return 1
    else:
        return pascal(row-1,column-1)+pascal(row-1,column)

Q4：Insect Combinatorics

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m==1 or n==1:
        return 1
    else:
        return paths(m-1,n)+paths(m,n-1)

Q5：Couple

…感觉自己真傻

def couple(s, t):
    """Return a list of two-element lists in which the i-th element is [s[i], t[i]].

    >>> a = [1, 2, 3]
    >>> b = [4, 5, 6]
    >>> couple(a, b)
    [[1, 4], [2, 5], [3, 6]]
    >>> c = ['c', 6]
    >>> d = ['s', '1']
    >>> couple(c, d)
    [['c', 's'], [6, '1']]
    """
    assert len(s) == len(t)
    "*** YOUR CODE HERE ***"
    return [[s[i],t[i]] for i in range(0,len(s))]

Q6：Coordinates

optional

def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """
    "*** YOUR CODE HERE ***"
    return [[x,fn(x)] for x in seq if fn(x)>=lower and fn(x)<=upper]

Q7：Riffle Shuffle

optional

def riffle(deck):
    """Produces a single, perfect riffle shuffle of DECK, consisting of
    DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
    second half of the deck.  Assume that len(DECK) is even.
    >>> riffle([3, 4, 5, 6])
    [3, 5, 4, 6]
    >>> riffle(range(20))
    [0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
    """
    "*** YOUR CODE HERE ***"
    return [deck[i//2+(len(deck)//2)*(i%2)] for i in range(len(deck))]

Disc 4：Tree Recursion，Python Lists

Q1：Count Stair Ways

def count_stair_ways(n):
    """Returns the number of ways to climb up a flight of
    n stairs, moving either 1 step or 2 steps at a time.
    >>> count_stair_ways(4)
    5
    """
    "*** YOUR CODE HERE ***"
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        return count_stair_ways(n-1)+count_stair_ways(n-2)

Q2：Count K

呜呜真的不会写这类题目，说我递归次数太多了…

算了算了，先放着吧x

def count_k(n, k):
    """ Counts the number of paths up a flight of n stairs
    when taking up to and including k steps at a time.
    >>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 1
    4
    >>> count_k(4, 4)
    8
    >>> count_k(10, 3)
    274
    >>> count_k(300, 1) # Only one step at a time
    1
    """
    "*** YOUR CODE HERE ***"
    if n==1:
        return 1
    else:
        i,sum=1,0
        while  i<=k:
            sum+=count_k(n-i,k)
            i+=1
        return sum

Q5：Max Product

def max_product(s):
    """Return the maximum product that can be formed using
    non-consecutive elements of s.
    >>> max_product([10,3,1,9,2]) # 10 * 9
    90
    >>> max_product([5,10,5,10,5]) # 5 * 5 * 5
    125
    >>> max_product([])
    1
    """
    if s==[]:
        return 1
    else:
        return max(max_product(s[1:]),s[0]*max_product(s[2:]))

Project 2：CS61A Autocorrected Typing Software——Cats

Phase 1：Typing

Problem 1

def choose(paragraphs, select, k):
    """Return the Kth paragraph from PARAGRAPHS for which SELECT called on the
    paragraph returns True. If there are fewer than K such paragraphs, return
    the empty string.

    Arguments:
        paragraphs: a list of strings
        select: a function that returns True for paragraphs that can be selected
        k: an integer

    >>> ps = ['hi', 'how are you', 'fine']
    >>> s = lambda p: len(p) <= 4
    >>> choose(ps, s, 0)
    'hi'
    >>> choose(ps, s, 1)
    'fine'
    >>> choose(ps, s, 2)
    ''
    """
    # BEGIN PROBLEM 1
    "*** YOUR CODE HERE ***"
    i,j=0,0
    store_list=[]
    while i<len(paragraphs):
        if select(paragraphs[i]):
            store_list.insert(j,paragraphs[i])
            i+=1
            j+=1
        else:
            i+=1
    if k>=j:
        return ''
    else:
        return store_list[k]
    # END PROBLEM 1

Problem 2

def about(topic):
    """Return a select function that returns whether
    a paragraph contains one of the words in TOPIC.

    Arguments:
        topic: a list of words related to a subject

    >>> about_dogs = about(['dog', 'dogs', 'pup', 'puppy'])
    >>> choose(['Cute Dog!', 'That is a cat.', 'Nice pup!'], about_dogs, 0)
    'Cute Dog!'
    >>> choose(['Cute Dog!', 'That is a cat.', 'Nice pup.'], about_dogs, 1)
    'Nice pup.'
    """
    assert all([lower(x) == x for x in topic]), 'topics should be lowercase.'
    # BEGIN PROBLEM 2
    "*** YOUR CODE HERE ***"
    def sel(para):
        i=0
        para=remove_punctuation(para)
        para=lower(para)
        para=split(para)
        while i<len(para):
            if para[i] in topic:
                return True
            else:
                i+=1
        return False
    return sel
    # END PROBLEM 2

Problem 3

def accuracy(typed, reference):
    """Return the accuracy (percentage of words typed correctly) of TYPED
    when compared to the prefix of REFERENCE that was typed.

    Arguments:
        typed: a string that may contain typos
        reference: a string without errors

    >>> accuracy('Cute Dog!', 'Cute Dog.')
    50.0
    >>> accuracy('A Cute Dog!', 'Cute Dog.')
    0.0
    >>> accuracy('cute Dog.', 'Cute Dog.')
    50.0
    >>> accuracy('Cute Dog. I say!', 'Cute Dog.')
    50.0
    >>> accuracy('Cute', 'Cute Dog.')
    100.0
    >>> accuracy('', 'Cute Dog.')
    0.0
    >>> accuracy('', '')
    100.0
    """
    typed_words = split(typed)
    reference_words = split(reference)
    # BEGIN PROBLEM 3
    "*** YOUR CODE HERE ***"
    if typed=='' and reference=='':
        return 100.0
    elif typed=='' or reference=='':
        return 0.0
    else:
        ty=split(typed)
        ref=split(reference)
        i,count=0,0
        if len(ty)<=len(ref):
            while i<len(ty):
                if ty[i]==ref[i]:
                    count+=1
                i+=1
            return 100*count/len(ty)
        else:
            while i<len(ref):
                if ty[i]==ref[i]:
                    count+=1
                i+=1
            return 100*count/len(ty)
    # END PROBLEM 3

Problem 4

def wpm(typed, elapsed):
    """Return the words-per-minute (WPM) of the TYPED string.

    Arguments:
        typed: an entered string
        elapsed: an amount of time in seconds

    >>> wpm('hello friend hello buddy hello', 15)
    24.0
    >>> wpm('0123456789',60)
    2.0
    """
    assert elapsed > 0, 'Elapsed time must be positive'
    # BEGIN PROBLEM 4
    "*** YOUR CODE HERE ***"
    vis=len(typed)/5
    return vis*60/elapsed
    # END PROBLEM 4

Phase 2：Autocorrect

Problem 5

太ugly了我写的…

def autocorrect(typed_word, valid_words, diff_function, limit):
    """Returns the element of VALID_WORDS that has the smallest difference
    from TYPED_WORD. Instead returns TYPED_WORD if that difference is greater
    than LIMIT.

    Arguments:
        typed_word: a string representing a word that may contain typos
        valid_words: a list of strings representing valid words
        diff_function: a function quantifying the difference between two words
        limit: a number

    >>> ten_diff = lambda w1, w2, limit: 10 # Always returns 10
    >>> autocorrect("hwllo", ["butter", "hello", "potato"], ten_diff, 20)
    'butter'
    >>> first_diff = lambda w1, w2, limit: (1 if w1[0] != w2[0] else 0) # Checks for matching first char
    >>> autocorrect("tosting", ["testing", "asking", "fasting"], first_diff, 10)
    'testing'
    """
    # BEGIN PROBLEM 5
    "*** YOUR CODE HERE ***"
    if typed_word in valid_words:
        return typed_word
    else:
        i,j=0,0
        vis=limit+1
        while i<len(valid_words):
            a=diff_function(typed_word,valid_words[i],limit)
            if a<vis:
                vis=a
                j=i
            i+=1
        if vis<=limit:
            return valid_words[j]
        else:
            return typed_word
    # END PROBLEM 5

嘛，google到了一种简单的方法：建立一个dictionary

def autocorrect(user_word, valid_words, diff_function, limit):
    """Returns the element of VALID_WORDS that has the smallest difference
    from USER_WORD. Instead returns USER_WORD if that difference is greater
    than LIMIT.
    """
    # BEGIN PROBLEM 5
    "*** YOUR CODE HERE ***"
    if user_word in valid_words:
        return user_word
    # Create dictionary with keys as iterables in valid_words list
    # and values as difference between them and user_word
    d = {v : diff_function(user_word, v, limit) for v in valid_words}
    return min(d, key=d.get) if min(d.values()) <= limit else user_word
    # END PROBLEM 5

Problem 6

def feline_flips(start, goal, limit):
    """A diff function for autocorrect that determines how many letters
    in START need to be substituted to create GOAL, then adds the difference in
    their lengths and returns the result.

    Arguments:
        start: a starting word
        goal: a string representing a desired goal word
        limit: a number representing an upper bound on the number of chars that must change

    >>> big_limit = 10
    >>> feline_flips("nice", "rice", big_limit)    # Substitute: n -> r
    1
    >>> feline_flips("range", "rungs", big_limit)  # Substitute: a -> u, e -> s
    2
    >>> feline_flips("pill", "pillage", big_limit) # Don't substitute anything, length difference of 3.
    3
    >>> feline_flips("roses", "arose", big_limit)  # Substitute: r -> a, o -> r, s -> o, e -> s, s -> e
    5
    >>> feline_flips("rose", "hello", big_limit)   # Substitute: r->h, o->e, s->l, e->l, length difference of 1.
    5
    """
    # BEGIN PROBLEM 6
    if limit<0:
        return 1
    if len(start)==0 or len(goal)==0:
        return abs(len(start)-len(goal))
    else:
        if start[0]==goal[0]:
            return feline_flips(start[1:], goal[1:], limit)
        else:
            return feline_flips(start[1:], goal[1:], limit-1)+1
    # END PROBLEM 6

Problem 7

def minimum_mewtations(start, goal, limit):
    """A diff function that computes the edit distance from START to GOAL.
    This function takes in a string START, a string GOAL, and a number LIMIT.

    Arguments:
        start: a starting word
        goal: a goal word
        limit: a number representing an upper bound on the number of edits

    >>> big_limit = 10
    >>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
    2
    >>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
    2
    >>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
    3
    """
    
    if limit<0:  # Fill in the condition
        # BEGIN
        "*** YOUR CODE HERE ***"
        return 1
        # END

    elif len(start)==0 or len(goal)==0:  # Feel free to remove or add additional cases
        # BEGIN
        "*** YOUR CODE HERE ***"
        return abs(len(start)-len(goal))
        # END
    elif start[0]==goal[0]:
        return minimum_mewtations(start[1:], goal[1:], limit)
    else:
        add = minimum_mewtations(start,goal[1:],limit-1)  # Fill in these lines
        remove = minimum_mewtations(start[1:],goal,limit-1)
        substitute = minimum_mewtations(start[1:],goal[1:],limit-1)
        # BEGIN
        "*** YOUR CODE HERE ***"
        return min(add,remove,substitute)+1
        # END

Phase 3：Multiplayer

Problem 8

def report_progress(sofar, prompt, user_id, upload):
    """Upload a report of your id and progress so far to the multiplayer server.
    Returns the progress so far.

    Arguments:
        sofar: a list of the words input so far
        prompt: a list of the words in the typing prompt
        user_id: a number representing the id of the current user
        upload: a function used to upload progress to the multiplayer server

    >>> print_progress = lambda d: print('ID:', d['id'], 'Progress:', d['progress'])
    >>> # The above function displays progress in the format ID: __, Progress: __
    >>> print_progress({'id': 1, 'progress': 0.6})
    ID: 1 Progress: 0.6
    >>> sofar = ['how', 'are', 'you']
    >>> prompt = ['how', 'are', 'you', 'doing', 'today']
    >>> report_progress(sofar, prompt, 2, print_progress)
    ID: 2 Progress: 0.6
    0.6
    >>> report_progress(['how', 'aree'], prompt, 3, print_progress)
    ID: 3 Progress: 0.2
    0.2
    """
    # BEGIN PROBLEM 8
    "*** YOUR CODE HERE ***"
    i,j,count=0,0,0
    while i<len(sofar) and j<len(prompt):
        if sofar[i]==prompt[j]:
            count+=1
            j+=1
        i+=1
    gress=count/len(prompt)
    d={'id':user_id,'progress':gress}
    upload(d)
    return gress
    # END PROBLEM 8

Problem 9

def time_per_word(words, times_per_player):
    """Given timing data, return a match data abstraction, which contains a
    list of words and the amount of time each player took to type each word.

    Arguments:
        words: a list of words, in the order they are typed.
        times_per_player: A list of lists of timestamps including the time
                          the player started typing, followed by the time
                          the player finished typing each word.

    >>> p = [[75, 81, 84, 90, 92], [19, 29, 35, 36, 38]]
    >>> match = time_per_word(['collar', 'plush', 'blush', 'repute'], p)
    >>> get_words(match)
    ['collar', 'plush', 'blush', 'repute']
    >>> get_times(match)
    [[6, 3, 6, 2], [10, 6, 1, 2]]
    """
    # BEGIN PROBLEM 9
    "*** YOUR CODE HERE ***"
    i=0
    test=[]
    while i<len(times_per_player):
        p=times_per_player[i]
        j=0
        while j<len(p)-1:
            p[j]=p[j+1]-p[j]
            j+=1
        test.append(p[:len(p)-1])
        i+=1
    return match(words,test)
    # END PROBLEM 9

Problem 10

这个好难，参考了别人做的

def fastest_words(match):
    """Return a list of lists of which words each player typed fastest.

    Arguments:
        match: a match data abstraction as returned by time_per_word.

    >>> p0 = [5, 1, 3]
    >>> p1 = [4, 1, 6]
    >>> fastest_words(match(['Just', 'have', 'fun'], [p0, p1]))
    [['have', 'fun'], ['Just']]
    >>> p0  # input lists should not be mutated
    [5, 1, 3]
    >>> p1
    [4, 1, 6]
    """
    player_indices = range(len(get_times(match)))  # contains an *index* for each player
    word_indices = range(len(get_words(match)))    # contains an *index* for each word
    # BEGIN PROBLEM 10
    "*** YOUR CODE HERE ***"
    test=[[] for k in player_indices]
    for i in word_indices:
        times=[time(match,j,i) for j in player_indices]
        test[times.index(min(times))].append(word_at(match,i))
    return test
    # END PROBLEM 10

Some feelings

明显感觉project2比project1简单不少，花的时间也少多了

希望是我python水平提高的原因吧

Lab 5：Python Lists, Trees

Q1：Factors List

def factors_list(n):
    """Return a list containing all the numbers that divide `n` evenly, except
    for the number itself. Make sure the list is in ascending order.

    >>> factors_list(6)
    [1, 2, 3]
    >>> factors_list(8)
    [1, 2, 4]
    >>> factors_list(28)
    [1, 2, 4, 7, 14]
    """
    all_factors = []
    i=1
    while i<n:
        if n%i==0:
            all_factors.append(i)
        i+=1
    return all_factors

Q2：Flatten

Hint: you can check if something is a list by using the built-in type function. For example:

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

def flatten(s):
    """Returns a flattened version of list s.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]     # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x # Ensure x is not mutated
    [1, [2, 3], 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    >>> x
    [[1, [1, 1]], 1, [1, 1]]
    """
    "*** YOUR CODE HERE ***"
    result=[]
    for i in s:
        if type(i)==list:
            result+=flatten(i)
        else:
            result.append(i)
    return result

Q3：Distance

def distance(city_a, city_b):
    """
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    """
    "*** YOUR CODE HERE ***"
    return sqrt((get_lat(city_a)-get_lat(city_b))**2+(get_lon(city_a)-get_lon(city_b))**2)

Q4：Closer city

def closer_city(lat, lon, city_a, city_b):
    """
    Returns the name of either city_a or city_b, whichever is closest to
    coordinate (lat, lon). If the two cities are the same distance away
    from the coordinate, consider city_b to be the closer city.

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    """
    "*** YOUR CODE HERE ***"
    city=make_city('city',lat,lon)
    if distance(city,city_a)>=distance(city,city_b):
        return get_name(city_b)
    else:
        return get_name(city_a)

Q6：Finding Berries!

def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.

    >>> scrat = tree('berry')
    >>> berry_finder(scrat)
    True
    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
    >>> berry_finder(sproul)
    True
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> berry_finder(numbers)
    False
    >>> t = tree(1, [tree('berry',[tree('not berry')])])
    >>> berry_finder(t)
    True
    """
    "*** YOUR CODE HERE ***"
    if label(t)=='berry':
        return True
    else:
        for b in branches(t):
            if berry_finder(b):
                return True
        return False

Q7：Sprout leaves

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the data in leaves at each leaf in
    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
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return tree(label(t),[tree(b) for b in leaves])
    else:
        return tree(label(t),[sprout_leaves(b,leaves) for b in branches(t)])

Disc 5：Trees, Data Abstraction, Sequences

Q2：Height

def height(t):
    """Return the height of a tree.

    >>> t = tree(3, [tree(5, [tree(1)]), tree(2)])
    >>> height(t)
    2
    >>> t = tree(3, [tree(1), tree(2, [tree(5, [tree(6)]), tree(1)])])
    >>> height(t)
    3
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 1
    else:
        return max([height(b) for b in branches(t)])  #so cool

Q3：Maximum Path Sum

def max_path_sum(t):
    """Return the maximum path sum of the tree.

    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t)
    11
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return label(t)
    else:
        return max([max_path_sum(b) for b in branches(t)])+label(t)

Q4：Find Path

def find_path(t, x):
    """
    >>> t = tree(2, [tree(7, [tree(3), tree(6, [tree(5), tree(11)])] ), tree(15)])
    >>> find_path(t, 5)
    [2, 7, 6, 5]
    >>> find_path(t, 10)  # returns None
    """
    if x==label(t):
        return [label(t)]
    else:
        for b in branches(t):
            path=find_path(b,x)
            if path:
                result=[label(t)]+path
                return result

Q5：Map, Filter, Reduce

def my_map(fn, seq):
    """Applies fn onto each element in seq and returns a list.
    >>> my_map(lambda x: x*x, [1, 2, 3])
    [1, 4, 9]
    """
    "*** YOUR CODE HERE ***"
    seq_new=[]
    for x in seq:
        seq_new.append(fn(x))
    return seq_new

def my_filter(pred, seq):
    """Keeps elements in seq only if they satisfy pred.
    >>> my_filter(lambda x: x % 2 == 0, [1, 2, 3, 4])  # new list has only even-valued elements
    [2, 4]
    """
    "*** YOUR CODE HERE ***"
    seq_new=[]
    for x in seq:
        if pred(x):
            seq_new.append(x)
    return seq_new

def my_reduce(combiner, seq):
    """Combines elements in seq using combiner.
    seq will have at least one element.
    >>> my_reduce(lambda x, y: x + y, [1, 2, 3, 4])  # 1 + 2 + 3 + 4
    10
    >>> my_reduce(lambda x, y: x * y, [1, 2, 3, 4])  # 1 * 2 * 3 * 4
    24
    >>> my_reduce(lambda x, y: x * y, [4])
    4
    >>> my_reduce(lambda x, y: x + 2 * y, [1, 2, 3]) # (1 + 2 * 2) + 2 * 3
    11
    """
    "*** YOUR CODE HERE ***"
    if len(seq)==1:
        return seq[0]
    elif len(seq)==2:
        return combiner(seq[0],seq[1])
    else:
        return combiner(combiner(seq[0],seq[1]),my_reduce(combiner,seq[2:]))

Q6：Count palindromes

def count_palindromes(L):
    """The number of palindromic words in the sequence of strings
    L (ignoring case).

    >>> count_palindromes(("Acme", "Madam", "Pivot", "Pip"))
    2
    """
    return len(my_filter(lambda x:x.lower()==x[::-1].lower(),L))

Q7：Perfectly Balanced

似乎…有点问题

to be dubug

def sum_tree(t):
    """
    Add all elements in a tree.
    >>> t = tree(4, [tree(2, [tree(3)]), tree(6)])
    >>> sum_tree(t)
    15
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return label(t)
    else:
        sum=label(t)
        for b in branches(t):
            sum+=sum_tree(b)
        return sum

def balanced(t):
    """
    Checks if each branch has same sum of all elements and
    if each branch is balanced.
    >>> t = tree(1, [tree(3), tree(1, [tree(2)]), tree(1, [tree(1), tree(1)])])
    >>> balanced(t)
    True
    >>> t = tree(1, [t, tree(1)])
    >>> balanced(t)
    False
    >>> t = tree(1, [tree(4), tree(1, [tree(2), tree(1)]), tree(1, [tree(3)])])
    >>> balanced(t)
    False
    """
    "*** YOUR CODE HERE ***"
    store=[]
    for b in branches(t):
        store.append(sum_tree(b))
    if max(store)==min(store):
        return True
    else:
        return False

def sum_tree(t):
    """
    Add all elements in a tree.
    >>> t = tree(4, [tree(2, [tree(3)]), tree(6)])
    >>> sum_tree(t)
    15
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return label(t)
    else:
        sum=label(t)
        for b in branches(t):
            sum+=sum_tree(b)
        return sum

Q8：Hailstone Tree

#orz，咕了 

HW 4：Data Abstraction，Trees

Q2：Weights

def planet(size):
    """Construct a planet of some size."""
    assert size > 0
    "*** YOUR CODE HERE ***"
    return ['planet',size]


def size(w):
    """Select the size of a planet."""
    assert is_planet(w), 'must call size on a planet'
    "*** YOUR CODE HERE ***"
    return w[1]

Q3：Balanced

平衡条件：①左右力矩相等 ②每个挂在arm上的mobile都平衡

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

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

强行枚举所有情况

Q4：Totals

def totals_tree(m):
    """Return a tree representing the mobile with its total weight at the root.

    >>> t, u, v = examples()
    >>> print_tree(totals_tree(t))
    3
      2
      1
    >>> print_tree(totals_tree(u))
    6
      1
      5
        3
        2
    >>> print_tree(totals_tree(v))
    9
      3
        2
        1
      6
        1
        5
          3
          2
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'totals_tree', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"
    if is_planet(m):
        return tree(size(m))
    else:
        assert is_mobile(m)
        return tree(total_weight(m),[totals_tree(end(left(m))),totals_tree(end(right(m)))])

Q5：Replace Loki at Leaf

def replace_loki_at_leaf(t, lokis_replacement):
    """Returns a new tree where every leaf value equal to "loki" has
    been replaced with lokis_replacement.

    >>> yggdrasil = tree('odin',
    ...                  [tree('balder',
    ...                        [tree('loki'),
    ...                         tree('freya')]),
    ...                   tree('frigg',
    ...                        [tree('loki')]),
    ...                   tree('loki',
    ...                        [tree('sif'),
    ...                         tree('loki')]),
    ...                   tree('loki')])
    >>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
    >>> print_tree(replace_loki_at_leaf(yggdrasil, 'freya'))
    odin
      balder
        freya
        freya
      frigg
        freya
      loki
        sif
        freya
      freya
    >>> laerad == yggdrasil # Make sure original tree is unmodified
    True
    """
    "*** YOUR CODE HERE ***"
    if label(t)=='loki' and is_leaf(t):
        return tree(lokis_replacement)
    else:
        return tree(label(t),[replace_loki_at_leaf(b,lokis_replacement) for b in branches(t)])

ATTENTION: tree的结构为tree(label(t),branches=[])，所以可以直接用循环+递归：tree(label(t),[replace_loki_at_leaf(b,lokis_replacement) for b in branches(t)])

Q6：Has Path

def has_path(t, word):
    """Return whether there is a path in a tree where the entries along the path
    spell out a particular word.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    >>> has_path(greetings, 'hint')
    False
    """
    assert len(word) > 0, 'no path for empty word.'
    "*** YOUR CODE HERE ***"
    if label(t)==word and len(word)==1:
        return True
    elif label(t)==word[0]:
        for b in branches(t):
            if has_path(b,word[1:]):
                return True
        return False
    else:
        return False

Q7：Preorder

optional

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return [label(t)]
    else:
        result=[label(t)]
        for b in branches(t):
            result+=preorder(b)   #这里不能是=，如果赋值的话相当于最后result就等于最后那个分支加上去的值
        return result

Q8：Interval Abstraction

def interval(a, b):
    """Construct an interval from a to b."""
    assert a <= b, 'Lower bound cannot be greater than upper bound'
    return [a, b]


def lower_bound(x):
    """Return the lower bound of interval x."""
    "*** YOUR CODE HERE ***"
    return x[0]


def upper_bound(x):
    """Return the upper bound of interval x."""
    "*** YOUR CODE HERE ***"
    return x[1]

Q9：Interval Arithmetic

def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    p1 = lower_bound(x)*lower_bound(y)
    p2 = lower_bound(x)*upper_bound(y)
    p3 = upper_bound(x)*lower_bound(y)
    p4 = upper_bound(x)*upper_bound(y)
    return interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))

def sub_interval(x, y):
    """Return the interval that contains the difference between any value in x
    and any value in y."""
    "*** YOUR CODE HERE ***"
    lower=lower_bound(x)-upper_bound(y)
    upper=upper_bound(x)-lower_bound(y)
    return interval(lower,upper)

def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    assert lower_bound(y)>0 or upper_bound(y)<0
    reciprocal_y = interval(1 / upper_bound(y), 1 / lower_bound(y))
    return mul_interval(x, reciprocal_y)

①提供的代码：

def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    p1 = x[0] * y[0]
    p2 = x[0] * y[1]
    p3 = x[1] * y[0]
    p4 = x[1] * y[1]
    return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]

1. 提供的代码会报错**’function’ object is not subscriptable**

The error “TypeError: ‘function’ object is not subscriptable” occurs when you try to access an item from a function. Functions cannot be indexed using square brackets.

即数据抽象要用其他函数去访问函数中的某个值，而不能直接用方括号索引函数

2. 如果只改p1~p4的值，不改return，则会报错**’list’ object is not callable**

The Python “TypeError: ‘list’ object is not callable” occurs when we try to call a list as a function using parenthesis () . To solve the error, make sure to use square brackets when accessing a list at a specific index

即[]和()没用对

3. print(‘{0}:{1}’.format(key, value))

分别用key、value的值代替{0}和{1}

如输出-1 to 1：

>>>print('{0} to {1}'.format(-1,1))

Lab 06：Mutability, Iterators

Q2：Insert Items

def insert_items(lst, entry, elem):
    """Inserts elem into lst after each occurence of entry and then returns lst.

    >>> test_lst = [1, 5, 8, 5, 2, 3]
    >>> new_lst = insert_items(test_lst, 5, 7)
    >>> new_lst
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> double_lst = [1, 2, 1, 2, 3, 3]
    >>> double_lst = insert_items(double_lst, 3, 4)
    >>> double_lst
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_lst = [1, 4, 8]
    >>> large_lst2 = insert_items(large_lst, 4, 4)
    >>> large_lst2
    [1, 4, 4, 8]
    >>> large_lst3 = insert_items(large_lst2, 4, 6)
    >>> large_lst3
    [1, 4, 6, 4, 6, 8]
    >>> large_lst3 is large_lst
    True
    >>> # Ban creating new lists
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'insert_items',
    ...       ['List', 'ListComp', 'Slice'])
    True
    """
    "*** YOUR CODE HERE ***"
    i=0
    while i<len(lst):
        if lst[i]==entry:
            lst.insert(i+1,elem)
            i+=2
        else:
            i+=1
    return lst

Q4：Count Occurrences

def count_occurrences(t, n, x):
    """Return the number of times that x appears in 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
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s2, 3, 10)
    2
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(s, 1, 3)
    1
    >>> count_occurrences(s, 4, 2)
    3
    >>> next(s)
    2
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> count_occurrences(s2, 6, 6)
    2
    """
    "*** YOUR CODE HERE ***"
    i,count=0,0
    while i<n:
        num=next(t)
        if num==x:
            count+=1
        i+=1             #怎么老忘记加1啊啊啊啊啊
    return count

Q5：Repeated

本题关键点在于用一个变量记录前一个数的值

def repeated(t, k):
    """Return the first value in iterator T that appears K times in a row.
    Iterate through the items such that if the same iterator is passed into
    the function twice, it continues in the second call at the point it left
    off in the first.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s2, 3)
    8
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    5
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(s2, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"
    last_num,cnt=None,0
    while True:
        num=next(t)
        if last_num==None or num!=last_num:
            last_num,cnt=num,1
        else:
            cnt+=1
            if cnt==k:
                return num

Disc 06：Mutability, Iterators and Generators

pop(i)：i为索引

remove(el)：el为元素

Q2：Add This Many

def add_this_many(x, el, s):
    """ Adds el to the end of s the number of times x occurs in s.
    >>> s = [1, 2, 4, 2, 1]
    >>> add_this_many(1, 5, s)
    >>> s
    [1, 2, 4, 2, 1, 5, 5]
    >>> add_this_many(2, 2, s)
    >>> s
    [1, 2, 4, 2, 1, 5, 5, 2, 2]
    """
    "*** YOUR CODE HERE ***"
    i,count=0,0
    while i<len(s):
        if x==s[i]:
            count+=1
        i+=1
    j=0
    while j<count:
        s.append(el)
        j+=1
    return

Q4：Filter-Iter

def filter_iter(iterable, fn):
    """
    >>> is_even = lambda x: x % 2 == 0
    >>> list(filter_iter(range(5), is_even)) # a list of the values yielded from the call to filter_iter
    [0, 2, 4]
    >>> all_odd = (2*y-1 for y in range(5))
    >>> list(filter_iter(all_odd, is_even))
    []
    >>> naturals = (n for n in range(1, 100))
    >>> s = filter_iter(naturals, is_even)
    >>> next(s)
    2
    >>> next(s)
    4
    """
    "*** YOUR CODE HERE ***"
    t=[]
    for b in iterable:
        if fn(b):
            t.append(b)
    return iter(t)

#用yield方法：
def filter_iter(iterable, fn):
    for b in iterable:
        if fn(b):
            yield b

Q5：Merge

def merge(a, b):
    """
    >>> 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]
    """
    "*** YOUR CODE HERE ***"
    num_a=next(a)
    num_b=next(b)
    while 1:
        if num_a==num_b:
            yield num_a
            num_a=next(a)
            num_b=next(b)
        elif num_a<num_b:
            yield num_a
            num_a=next(a)
        else:
            yield num_b
            num_b=next(b)

Q6：Primes Generator

def is_prime(n):
    """Returns True if n is a prime number and False otherwise.
    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    def helper(i):
        if i > (n ** 0.5): # Could replace with i == n
            return True
        elif n % i == 0:
            return False
        return helper(i + 1)
    return helper(2)

def primes_gen(n):
    """Generates primes in decreasing order.
    >>> pg = primes_gen(7)
    >>> list(pg)
    [7, 5, 3, 2]
    """
    if n<2:
        return
    if is_prime(n):
        yield n
    yield from primes_gen(n-1)

HW 05：Iterators and Generators

Q1：Generate Permutations

先想base case是什么，然后将要写的函数当作已经完成要求的函数，实现递归。

def gen_perms(seq):
    """Generates all permutations of the given sequence. Each permutation is a
    list of the elements in SEQ in a different order. The permutations may be
    yielded in any order.

    >>> perms = gen_perms([100])
    >>> type(perms)
    <class 'generator'>
    >>> next(perms)
    [100]
    >>> try: #this piece of code prints "No more permutations!" if calling next would cause an error
    ...     next(perms)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(gen_perms([1, 2, 3])) # Returns a sorted list containing elements of the generator
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> sorted(gen_perms((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(gen_perms("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    "*** YOUR CODE HERE ***"
    if type(seq)!=list:
        seq=list(seq)
    if len(seq)<=1:
        yield seq
    else:
        for perm in gen_perms(seq[1:]):
            for i in range(len(seq)):
                yield perm[:i]+seq[:1]+perm[i:]

Q2：Yield Paths

def path_yielder(t, value):
    """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(path_yielder(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = path_yielder(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 = path_yielder(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    "*** YOUR CODE HERE ***"
    if label(t)==value:
        yield [value]
    for b in branches(t):
        for path in path_yielder(b,value): 
            yield [label(t)]+path

Q3：Preorder

见hw04 Q7

Q4：Generate Preorder

def generate_preorder(t):
    """Yield the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> gen = generate_preorder(numbers)
    >>> next(gen)
    1
    >>> list(gen)
    [2, 3, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    yield label(t)
    for b in branches(t):
        yield from generate_preorder(b)

Q5：Remainder Generator

会生成m个生成器，其中第i个生成器生成是除以m余i的所有数

令第一个生成器为余0，第二个为余1…

这题的题目意思好难理解

def remainders_generator(m):
    """
    Yields m generators. The ith yielded generator yields natural numbers whose
    remainder is i when divided by m.

    >>> import types
    >>> [isinstance(gen, types.GeneratorType) for gen in remainders_generator(5)]
    [True, True, True, True, True]
    >>> remainders_four = remainders_generator(4)
    >>> for i in range(4):
    ...     print("First 3 natural numbers with remainder {0} when divided by 4:".format(i))
    ...     gen = next(remainders_four)
    ...     for _ in range(3):
    ...         print(next(gen))
    First 3 natural numbers with remainder 0 when divided by 4:
    4
    8
    12
    First 3 natural numbers with remainder 1 when divided by 4:
    1
    5
    9
    First 3 natural numbers with remainder 2 when divided by 4:
    2
    6
    10
    First 3 natural numbers with remainder 3 when divided by 4:
    3
    7
    11
    """
    "*** YOUR CODE HERE ***"
    def helper(i):
        for x in naturals():
            if x%m==i:
                yield x
    for j in range(m):            #这里是关键，否则会Timeout
        yield helper(j)
    
    
"""
不用higher-order function也会报Timeout错误，怪
可能是没有用high-order function “封装”，使程序一直进行？
def remainders_generator(m):
	for i in range(m):
        for x in naturals():
            if x%m==i:
                yield x
"""

Lab 07：Object-Oriented Programming

Q2：Retirement

def time_to_retire(self, amount):
        """Return the number of years until balance would grow to amount."""
        assert self.balance > 0 and amount > 0 and self.interest > 0
        "*** YOUR CODE HERE ***"
        i=1
        while True:
            if self.balance*(self.interest+1)**i>=amount:
                return i
            i+=1

Q3：FreeChecking

class FreeChecking(Account):
    """A bank account that charges for withdrawals, but the first two are free!
    >>> ch = FreeChecking('Jack')
    >>> ch.balance = 20
    >>> ch.withdraw(100)  # First one's free
    'Insufficient funds'
    >>> ch.withdraw(3)    # And the second
    17
    >>> ch.balance
    17
    >>> ch.withdraw(3)    # Ok, two free withdrawals is enough
    13
    >>> ch.withdraw(3)
    9
    >>> ch2 = FreeChecking('John')
    >>> ch2.balance = 10
    >>> ch2.withdraw(3) # No fee
    7
    >>> ch.withdraw(3)  # ch still charges a fee
    5
    >>> ch.withdraw(5)  # Not enough to cover fee + withdraw
    'Insufficient funds'
    """
    withdraw_fee = 1
    free_withdrawals = 2

    "*** YOUR CODE HERE ***"
    def withdraw(self,amount):
        if amount > self.balance:
            self.free_withdrawals-=1
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            self.free_withdrawals-=1
            return "Can't withdraw that amount"
        if self.free_withdrawals>0:
            self.free_withdrawals-=1
            self.balance = self.balance - amount
        else:
            self.balance=self.balance-amount-self.withdraw_fee
        if amount > self.balance:
            self.free_withdrawals-=1
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            self.free_withdrawals-=1
            return "Can't withdraw that amount"
        return self.balance

Q4：Making Cards

class Card:
    cardtype = 'Staff'

    def __init__(self, name, attack, defense):
        """
        Create a Card object with a name, attack,
        and defense.
        >>> staff_member = Card('staff', 400, 300)
        >>> staff_member.name
        'staff'
        >>> staff_member.attack
        400
        >>> staff_member.defense
        300
        >>> other_staff = Card('other', 300, 500)
        >>> other_staff.attack
        300
        >>> other_staff.defense
        500
        """
        "*** YOUR CODE HERE ***"
        self.name=name
        self.attack=attack
        self.defense=defense

    def power(self, opponent_card):
        """
        Calculate power as:
        (player card's attack) - (opponent card's defense)/2
        >>> staff_member = Card('staff', 400, 300)
        >>> other_staff = Card('other', 300, 500)
        >>> staff_member.power(other_staff)
        150.0
        >>> other_staff.power(staff_member)
        150.0
        >>> third_card = Card('third', 200, 400)
        >>> staff_member.power(third_card)
        200.0
        >>> third_card.power(staff_member)
        50.0
        """
        "*** YOUR CODE HERE ***"
        return self.attack-opponent_card.defense/2

Q5：Making a Player

class Player:
    def __init__(self, deck, name):
        """Initialize a Player object.
        A Player starts the game by drawing 5 cards from their deck. Each turn,
        a Player draws another card from the deck and chooses one to play.
        >>> test_card = Card('test', 100, 100)
        >>> test_deck = Deck([test_card.copy() for _ in range(6)])
        >>> test_player = Player(test_deck, 'tester')
        >>> len(test_deck.cards)
        1
        >>> len(test_player.hand)
        5
        """
        self.deck = deck
        self.name = name
        "*** YOUR CODE HERE ***"
        self.hand=[self.deck.draw() for _ in range(5)]


    def draw(self):
        """Draw a card from the player's deck and add it to their hand.
        >>> test_card = Card('test', 100, 100)
        >>> test_deck = Deck([test_card.copy() for _ in range(6)])
        >>> test_player = Player(test_deck, 'tester')
        >>> test_player.draw()
        >>> len(test_deck.cards)
        0
        >>> len(test_player.hand)
        6
        """
        assert not self.deck.is_empty(), 'Deck is empty!'
        "*** YOUR CODE HERE ***"
        self.hand.append(self.deck.draw())

    def play(self, card_index):
        """Remove and return a card from the player's hand at the given index.
        >>> from cards import *
        >>> test_player = Player(standard_deck, 'tester')
        >>> ta1, ta2 = TACard("ta_1", 300, 400), TACard("ta_2", 500, 600)
        >>> tutor1, tutor2 = TutorCard("t1", 200, 500), TutorCard("t2", 600, 400)
        >>> test_player.hand = [ta1, ta2, tutor1, tutor2]
        >>> test_player.play(0) is ta1
        True
        >>> test_player.play(2) is tutor2
        True
        >>> len(test_player.hand)
        2
        """
        "*** YOUR CODE HERE ***"
        self.hand.pop(card_index)

Q6：ALs：Defenders

optional

class AICard(Card):
    cardtype = 'AI'

    def effect(self, opponent_card, player, opponent):
        """
        Reduce the opponent's card's attack by its defense,
        then double its defense.
        >>> from cards import *
        >>> player1, player2 = Player(player_deck, 'p1'), Player(opponent_deck, 'p2')
        >>> opponent_card = Card('other', 300, 600)
        >>> ai_test = AICard('AI', 500, 500)
        >>> ai_test.effect(opponent_card, player1, player2)
        >>> opponent_card.attack
        0
        >>> opponent_card.defense
        1200
        >>> opponent_card = Card('other', 600, 400)
        >>> ai_test = AICard('AI', 500, 500)
        >>> ai_test.effect(opponent_card, player1, player2)
        >>> opponent_card.attack
        200
        >>> opponent_card.defense
        800
        """
        "*** YOUR CODE HERE ***"
        if (opponent_card.attack-opponent_card.defense)<0:
            opponent_card.attack=0
            opponent_card.defense=opponent_card.defense*2
        else:
            opponent_card.attack=opponent_card.attack-opponent_card.defense
            opponent_card.defense=opponent_card.defense*2

Q7：Tutors：Flummox

optional

class TutorCard(Card):
    cardtype = 'Tutor'

    def effect(self, opponent_card, player, opponent):
        """
        Discard the first 3 cards in the opponent's hand and have
        them draw the same number of cards from their deck.
        >>> from cards import *
        >>> player1, player2 = Player(player_deck, 'p1'), Player(opponent_deck, 'p2')
        >>> opponent_card = Card('other', 500, 500)
        >>> tutor_test = TutorCard('Tutor', 500, 500)
        >>> initial_deck_length = len(player2.deck.cards)
        >>> tutor_test.effect(opponent_card, player1, player2)
        p2 discarded and re-drew 3 cards!
        >>> len(player2.hand)
        5
        >>> len(player2.deck.cards) == initial_deck_length - 3
        True
        """
        "*** YOUR CODE HERE ***"
        # You should add your implementation above this.
        i,j=0,0
        while i<3:
            opponent.hand.pop()
            i+=1
        while j<3:
            opponent.hand.append(opponent.deck.draw())
            j+=1
        print('{} discarded and re-drew 3 cards!'.format(opponent.name))

Q8：TAs：Shift

optional

class TACard(Card):
    cardtype = 'TA'

    def effect(self, opponent_card, player, opponent):
        """
        Swap the attack and defense of an opponent's card.
        >>> from cards import *
        >>> player1, player2 = Player(player_deck, 'p1'), Player(opponent_deck, 'p2')
        >>> opponent_card = Card('other', 300, 600)
        >>> ta_test = TACard('TA', 500, 500)
        >>> ta_test.effect(opponent_card, player1, player2)
        >>> opponent_card.attack
        600
        >>> opponent_card.defense
        300
        """
        "*** YOUR CODE HERE ***"
        store=opponent_card.attack
        opponent_card.attack=opponent_card.defense
        opponent_card.defense=store

Q9：The Instructor Arrives

optional

有点bug，算了算了

class InstructorCard(Card):
    cardtype = 'Instructor'

    def effect(self, opponent_card, player, opponent):
        """
        Adds the attack and defense of the opponent's card to
        all cards in the player's deck, then removes all cards
        in the opponent's deck that share an attack or defense
        stat with the opponent's card.
        >>> test_card = Card('card', 300, 300)
        >>> instructor_test = InstructorCard('Instructor', 500, 500)
        >>> opponent_card = test_card.copy()
        >>> test_deck = Deck([test_card.copy() for _ in range(8)])
        >>> player1, player2 = Player(test_deck.copy(), 'p1'), Player(test_deck.copy(), 'p2')
        >>> instructor_test.effect(opponent_card, player1, player2)
        3 cards were discarded from p2's deck!
        >>> [(card.attack, card.defense) for card in player1.deck.cards]
        [(600, 600), (600, 600), (600, 600)]
        >>> len(player2.deck.cards)
        0
        """
        orig_opponent_deck_length = len(opponent.deck.cards)
        "*** YOUR CODE HERE ***"
        # You should add your implementation above this.
        for i_cards in player.deck.cards:
            i_cards.attack+=opponent_card.attack
            i_cards.defense+=opponent_card.defense
        for o_cards in opponent.deck.cards:
            if o_cards.attack==opponent_card.attack or o_cards.defense==opponent_card.defense:
                opponent.deck.cards.remove(o_cards)

        discarded = orig_opponent_deck_length - len(opponent.deck.cards)
        if discarded:
            print('{} cards were discarded from {}\'s deck!'.format(discarded, opponent.name))
            return

Project 03：Ants

Problem 2

Hint: Remember that when the __init__ method is called, the first parameter, self, is bound to the newly created object

Problem 8

好开心！！！尽管改了几次，但最终看到“20 test cases passed! No cases failed.”时巨兴奋

8和7都是3pt。不过7基本上是我看别人代码写出来的（因为自己不太能理解题目和所给的代码意思

但8完全是自己写出来的，写了好久，一句一句地理解题目的意思，写的时候万分怀疑自己这样写是不是对的

希望以后这样的时刻能够多一些

写完的一点感想：

算是写过的三个project里面最难的了，写了好几天（当然，每天的coding时间较之前少

尽管有所参考，但也算是大有收获

super().action(gamestate)

等同于

FatherClass.action(gamestate) #FatherClass是所继承的类

"""CS 61A presents Ants Vs. SomeBees."""

import random
from ucb import main, interact, trace
from collections import OrderedDict

################
# Core Classes #
################


class Place:
    """A Place holds insects and has an exit to another Place."""
    is_hive = False

    def __init__(self, name, exit=None):
        """Create a Place with the given NAME and EXIT.

        name -- A string; the name of this Place.
        exit -- The Place reached by exiting this Place (may be None).
        """
        self.name = name
        self.exit = exit
        self.bees = []        # A list of Bees
        self.ant = None       # An Ant
        self.entrance = None  # A Place
        # Phase 1: Add an entrance to the exit
        # BEGIN Problem 2
        "*** YOUR CODE HERE ***"
        if self.exit:
            exit.entrance=self
        
        # END Problem 2

    def add_insect(self, insect):
        """
        Asks the insect to add itself to the current place. This method exists so
            it can be enhanced in subclasses.
        """
        insect.add_to(self)

    def remove_insect(self, insect):
        """
        Asks the insect to remove itself from the current place. This method exists so
            it can be enhanced in subclasses.
        """
        insect.remove_from(self)

    def __str__(self):
        return self.name


class Insect:
    """An Insect, the base class of Ant and Bee, has health and a Place."""

    damage = 0
    is_waterproof=False
    # ADD CLASS ATTRIBUTES HERE

    def __init__(self, health, place=None):
        """Create an Insect with a health amount and a starting PLACE."""
        self.health = health
        self.place = place  # set by Place.add_insect and Place.remove_insect

    def reduce_health(self, amount):
        """Reduce health by AMOUNT, and remove the insect from its place if it
        has no health remaining.

        >>> test_insect = Insect(5)
        >>> test_insect.reduce_health(2)
        >>> test_insect.health
        3
        """
        self.health -= amount
        if self.health <= 0:
            self.death_callback()
            self.place.remove_insect(self)

    def action(self, gamestate):
        """The action performed each turn.

        gamestate -- The GameState, used to access game state information.
        """

    def death_callback(self):
        # overriden by the gui
        pass

    def add_to(self, place):
        """Add this Insect to the given Place

        By default just sets the place attribute, but this should be overriden in the subclasses
            to manipulate the relevant attributes of Place
        """
        self.place = place

    def remove_from(self, place):
        self.place = None

    def __repr__(self):
        cname = type(self).__name__
        return '{0}({1}, {2})'.format(cname, self.health, self.place)


class Ant(Insect):
    """An Ant occupies a place and does work for the colony."""

    implemented = False  # Only implemented Ant classes should be instantiated
    food_cost = 0
    is_container = False
    buffed=False
    # ADD CLASS ATTRIBUTES HERE

    def __init__(self, health=1):
        """Create an Insect with a HEALTH quantity."""
        super().__init__(health)

    @classmethod
    def construct(cls, gamestate):
        """Create an Ant for a given GameState, or return None if not possible."""
        if cls.food_cost > gamestate.food:
            print('Not enough food remains to place ' + cls.__name__)
            return
        return cls()

    def can_contain(self, other):
        return False

    def store_ant(self, other):
        assert False, "{0} cannot contain an ant".format(self)

    def remove_ant(self, other):
        assert False, "{0} cannot contain an ant".format(self)

    def add_to(self, place):
        if place.ant is None:
            place.ant = self
        else:
            # BEGIN Problem 8
            
            if place.ant.can_contain(self):  #这个函数要不要改一下形式？
                place.ant.ant_contained=self
            elif self.can_contain(place.ant):
                self.ant_contained=place.ant
                place.ant=self  #这里要不要把二者交换，也就是令self=place.ant？
            else:
                assert place.ant is None, 'Two ants in {0}'.format(place)
            # END Problem 8
        Insect.add_to(self, place)

    def remove_from(self, place):
        if place.ant is self:
            place.ant = None
        elif place.ant is None:
            assert False, '{0} is not in {1}'.format(self, place)
        else:
            place.ant.remove_ant(self)
        Insect.remove_from(self, place)

    def buff(self):
        """Double this ants's damage, if it has not already been buffed."""
        # BEGIN Problem 12
        "*** YOUR CODE HERE ***"
        if not self.buffed:
            self.damage*=2
            self.buffed=True
        # END Problem 12


class HarvesterAnt(Ant):
    """HarvesterAnt produces 1 additional food per turn for the colony."""

    name = 'Harvester'
    implemented = True
    # OVERRIDE CLASS ATTRIBUTES HERE
    food_cost=2
    def action(self, gamestate):
        """Produce 1 additional food for the colony.

        gamestate -- The GameState, used to access game state information.
        """
        # BEGIN Problem 1
        "*** YOUR CODE HERE ***"
        gamestate.food+=1
        # END Problem 1


class ThrowerAnt(Ant):
    """ThrowerAnt throws a leaf each turn at the nearest Bee in its range."""

    name = 'Thrower'
    implemented = True
    damage = 1
    max_range=3
    min_range=5
    # ADD/OVERRIDE CLASS ATTRIBUTES HERE
    food_cost=3
    def nearest_bee(self):
        """Return the nearest Bee in a Place that is not the HIVE, connected to
        the ThrowerAnt's Place by following entrances.

        This method returns None if there is no such Bee (or none in range).
        """
        # BEGIN Problem 3 and 4
        current_place=self.place    #Start from the current Place of the ThrowerAnt
        while current_place.entrance: #只要不是hive
            if current_place.bees:
                return random_bee(current_place.bees)
            current_place=current_place.entrance    
        #感觉就是把题目的那几句话翻译出来
        # END Problem 3 and 4

    def throw_at(self, target):
        """Throw a leaf at the TARGET Bee, reducing its health."""
        if target is not None:
            target.reduce_health(self.damage)

    def action(self, gamestate):
        """Throw a leaf at the nearest Bee in range."""
        self.throw_at(self.nearest_bee())


def random_bee(bees):
    """Return a random bee from a list of bees, or return None if bees is empty."""
    assert isinstance(bees, list), "random_bee's argument should be a list but was a %s" % type(bees).__name__
    if bees:
        return random.choice(bees)

##############
# Extensions #
##############


class ShortThrower(ThrowerAnt):
    """A ThrowerAnt that only throws leaves at Bees at most 3 places away."""

    name = 'Short'
    food_cost = 2
    # OVERRIDE CLASS ATTRIBUTES HERE
    # BEGIN Problem 4
    implemented = True   # Change to True to view in the GUI
    def nearest_bee(self):
        count=0
        current_place=self.place
        while count<self.max_range and current_place.entrance:
            if current_place.bees:
                return random_bee(current_place.bees)
            current_place=current_place.entrance
            count+=1
            

    # END Problem 4


class LongThrower(ThrowerAnt):
    """A ThrowerAnt that only throws leaves at Bees at least 5 places away."""

    name = 'Long'
    food_cost = 2
    
    # OVERRIDE CLASS ATTRIBUTES HERE
    # BEGIN Problem 4
    implemented = True   # Change to True to view in the GUI
    def nearest_bee(self):
        current_place=self.place
        while current_place.entrance.entrance.entrance.entrance.entrance: #妙在这里
            if current_place.bees:
                return random_bee(current_place.bees)
            current_place=current_place.entrance

    # END Problem 4


class FireAnt(Ant):
    """FireAnt cooks any Bee in its Place when it expires."""

    name = 'Fire'
    damage = 3
    food_cost = 5
    # OVERRIDE CLASS ATTRIBUTES HERE
    # BEGIN Problem 5
    implemented = True   # Change to True to view in the GUI
    # END Problem 5

    def __init__(self, health=3):
        """Create an Ant with a HEALTH quantity."""
        super().__init__(health)

    def reduce_health(self, amount):
        """Reduce health by AMOUNT, and remove the FireAnt from its place if it
        has no health remaining.

        Make sure to reduce the health of each bee in the current place, and apply
        the additional damage if the fire ant dies.
        """
        # BEGIN Problem 5
        "*** YOUR CODE HERE ***"
        current_place=self.place
        for bee in current_place.bees[:]:
            bee.reduce_health(amount)
        if amount>=self.health:   #amount指蛰fireant的蜜蜂数量，此处指fireant的health为零
            for bee in current_place.bees[:]:
                bee.reduce_health(self.damage)
            super().reduce_health(amount)  #可以根据提示？
        else:
            super().reduce_health(amount)
        # END Problem 5

# BEGIN Problem 6
# The WallAnt class
class WallAnt(Ant):
    name='Wall'
    food_cost=4
    implemented=True
    def __init__(self, health=4):
        super().__init__(health)
# END Problem 6

# BEGIN Problem 7
# The HungryAnt Class
class HungryAnt(Ant):
    name='Hungry'
    implemented=True
    food_cost=4
    chew_duration=3
    def __init__(self,health=1):
        super().__init__(health)
        self.chew_countdown=0
    def action(self):
        if self.chew_countdown!=0:
            self.chew_countdown-=1
        else:
            current_place=self.place
            if len(current_place.bees)>0:
                self.chew_countdown=self.chew_duration
                bee=random_bee(current_place.bees)
                bee.reduce_health(bee.health)
# END Problem 7


class ContainerAnt(Ant):
    """
    ContainerAnt can share a space with other ants by containing them.
    ant_contained: stores the ant it contains
    """
    is_container = True

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.ant_contained = None

    def can_contain(self, other):
        # BEGIN Problem 8
        "*** YOUR CODE HERE ***"
        if not other.is_container and self.ant_contained ==None:
            return True
        # END Problem 8

    def store_ant(self, ant):
        # BEGIN Problem 8
        "*** YOUR CODE HERE ***"
        self.ant_contained=ant
        # END Problem 8

    def remove_ant(self, ant):
        if self.ant_contained is not ant:
            assert False, "{} does not contain {}".format(self, ant)
        self.ant_contained = None

    def remove_from(self, place):
        # Special handling for container ants (this is optional)
        if place.ant is self:
            # Container was removed. Contained ant should remain in the game
            place.ant = place.ant.ant_contained
            Insect.remove_from(self, place)
        else:
            # default to normal behavior
            Ant.remove_from(self, place)

    def action(self, gamestate):
        # BEGIN Problem 8
        "*** YOUR CODE HERE ***"
        if self.ant_contained!=None:
            self.ant_contained.action(gamestate)  
        # END Problem 8


class BodyguardAnt(ContainerAnt):
    """BodyguardAnt provides protection to other Ants."""

    name = 'Bodyguard'
    food_cost = 4
    # OVERRIDE CLASS ATTRIBUTES HERE
    # BEGIN Problem 8
    implemented = True   # Change to True to view in the GUI
    def __init__(self,health=2):
        super().__init__(health)
    # END Problem 8

# BEGIN Problem 9
# The TankAnt class
class TankAnt(ContainerAnt):
    name='Tank'
    food_cost=6
    damage=1
    implemented=True
    def __init__(self,health=2):
        super().__init__(health)
    def action(self,gamestate):
        current_place=self.place
        if self.ant_contained!=None:
            self.ant_contained.action(gamestate)
        for bee in current_place.bees[:]:
            bee.reduce_health(self.damage)
# END Problem 9


class Water(Place):
    """Water is a place that can only hold waterproof insects."""

    def add_insect(self, insect):
        """Add an Insect to this place. If the insect is not waterproof, reduce
        its health to 0."""
        # BEGIN Problem 10
        "*** YOUR CODE HERE ***"
        super().add_insect(insect)
        if not insect.is_waterproof:
            insect.reduce_health(insect.health)
        # END Problem 10

# BEGIN Problem 11
# The ScubaThrower class
class ScubaThrower(ThrowerAnt):
    food_cost=6
    is_waterproof=True
    name='Scuba'
    implemented=True


# END Problem 11

# BEGIN Problem 12


class QueenAnt(ScubaThrower):  # You should change this line
# END Problem 12
    """The Queen of the colony. The game is over if a bee enters her place."""

    name = 'Queen'
    food_cost = 7
    is_queenant=True
    # OVERRIDE CLASS ATTRIBUTES HERE
    # BEGIN Problem 12
    implemented = True   # Change to True to view in the GUI
    # END Problem 12

    @classmethod
    def construct(cls, gamestate): #有一定参考
        """
        Returns a new instance of the Ant class if it is possible to construct, or
        returns None otherwise. Remember to call the construct() method of the superclass!
        """
        # BEGIN Problem 12
        "*** YOUR CODE HERE ***"
        cls.is_queenant=QueenAnt.is_queenant
        if cls.food_cost > gamestate.food:
            print('Not enough food remains to place ' + cls.__name__)
            return 
        elif cls.is_queenant:
            QueenAnt.is_queenant=False
            return super().construct(gamestate)
        else:
            return None
        # END Problem 12

    def action(self, gamestate):  #有一定参考
        """A queen ant throws a leaf, but also doubles the damage of ants
        in her tunnel.
        """
        # BEGIN Problem 12
        "*** YOUR CODE HERE ***"
        #if not self.is_queenant:
            #self.reduce_health(self.health)
        #else:
        super().action(gamestate)
        behind=self.place.exit
        while behind:
            if behind.ant!=None:
                if not behind.ant.buffed:
                    behind.ant.buff()
                if behind.ant.is_container and behind.ant.ant_contained:
                    if not behind.ant.ant_contained.buffed:
                        behind.ant.ant_contained.buff()
            behind=behind.exit

        # END Problem 12

    def reduce_health(self, amount):
        """Reduce health by AMOUNT, and if the QueenAnt has no health
        remaining, signal the end of the game.
        """
        # BEGIN Problem 12
        "*** YOUR CODE HERE ***"
        current_place=self.place
        for bee in current_place.bees[:]:
            bee.reduce_health(amount)
        if amount>=self.health:
            ants_lose()
        
    def remove_from(self,place):
        '''
        if place.ant is self:
            return
        elif place.ant is None:
            assert False, '{0} is not in {1}'.format(self, place)
        else:
            place.ant.remove_ant(self)
        Insect.remove_from(self, place)
        '''
        None   #疑惑，为什么不能像上面那样写
        # END Problem 12

后面的optional部分就不写了，也没有截取到上面

Disc 07：Object-Oriented Programming, String Repredentation

Q2：Keyboard

未debug版（悲

class Button:
    def __init__(self, pos, key):
        self.pos = pos
        self.key = key
        self.times_pressed = 0

class Keyboard:
    """A Keyboard takes in an arbitrary amount of buttons, and has a
    dictionary of positions as keys, and values as Buttons.
    >>> b1 = Button(0, "H")
    >>> b2 = Button(1, "I")
    >>> k = Keyboard(b1, b2)
    >>> k.buttons[0].key   #dictionary的key
    'H'
    >>> k.press(1)
    'I'
    >>> k.press(2) # No button at this position
    ''
    >>> k.typing([0, 1])
    'HI'
    >>> k.typing([1, 0])
    'IH'
    >>> b1.times_pressed
    2
    >>> b2.times_pressed
    3
    """
    def __init__(self, *args):
        self.buttons={}  #dictionary
        for args in args:    #为什么这个要这样写，悲
            self.buttons[args.pos]=args

    def press(self, info):
        """Takes in a position of the button pressed, and
        returns that button's output."""
        if info<=len(self.buttons):
            return self.buttons[info].key
        else:
            return ''

    def typing(self, typing_input):
        """Takes in a list of positions of buttons pressed, and
        returns the total output."""
        output=''
        for word in typing_input:
            output+=typing_input[index(word)]
        return output

Q3：Cat

class Cat(Pet):

    def __init__(self, name, owner, lives=9):
        "*** YOUR CODE HERE ***"
        self.name=name
        self.owner=owner
        self.lives=lives

    def talk(self):
        """Print out a cat's greeting.

        >>> Cat('Thomas', 'Tammy').talk()
        Thomas says meow!
        """
        "*** YOUR CODE HERE ***"
        print('{} says meow!'.format(self.name))

    def lose_life(self):
        """Decrements a cat's life by 1. When lives reaches zero,
        is_alive becomes False. If this is called after lives has
        reached zero, print 'This cat has no more lives to lose.'
        """
        "*** YOUR CODE HERE ***"
        if self.lives==0:
            print('This cat has no more lives to lose.')

Q4：NoisyCat

def __init__(self, name, owner, lives=9):
        # Is this method necessary? Why or why not?
        "*** YOUR CODE HERE ***"
        self.name=name
        self.owner=owner
        self.lives=lives

    def talk(self):
        """Talks twice as much as a regular cat.
        >>> NoisyCat('Magic', 'James').talk()
        Magic says meow!
        Magic says meow!
        """
        "*** YOUR CODE HERE ***"
        for i in range(2):
            print('{} says meow!'.format(self.name))

Q5：Cat Adoption（cls用法

…to be continued

需要领悟一下cls的用法

关于cls：

一般来说，要使用某个类的方法，需要先实例化一个对象再调用方法,而使用@staticmethod或@classmethod，就可以不需要实例化，直接类名.方法名()来调用。

cls在python中表示类本身，self为类的一个实例

class Person(object):
    def __init__(self,name,age):
        ...
    @classmethod
    def build(cls):
        ...

则cls()等于Person()，Person.build()返回一个Person的实例

import random as random

class Cat(Pet):
    def __init__(self, name, owner, lives=9):
        "*** YOUR CODE HERE ***"
        self.name=name
        self.owner=owner
        self.lives=lives

    # Insert other previously defined methods here

    @classmethod
    def adopt_random_cat(cls, owner):
        """
        Returns a new instance of a Cat with the given owner,
        a randomly chosen name and a random number of lives.
        >>> randcat = Cat.adopt_random_cat("Ifeoma")
        >>> isinstance(randcat, Cat)
        True
        >>> randcat.owner
        'Ifeoma'
        """
        cls.name=random.choice[]   #这个函数用的不对
        cls.lives=random.randint(1,10)
        return cls(name, owner, lives)

就这样吧，有气无力.jpg

HW 06：Object-Oriented Programming, Linked Lists

Q1:Vending Machine

c++里类似cout的操作在python中可以用f表达式代替

各函数功能：

__init__：初始化

vend：出售物品

add_funds：增加所有的balance

restock：能被购买的物品数

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Nothing left to vend. Please restock.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'You must add $10 more funds.'
    >>> v.add_funds(7)
    'Current balance: $7'
    >>> v.vend()
    'You must add $3 more funds.'
    >>> v.add_funds(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.add_funds(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'

    >>> w = VendingMachine('soda', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.add_funds(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    """
    "*** YOUR CODE HERE ***"
    def __init__(self,name,price):
        self.name=name
        self.price=price
        self.stock=0
        self.balance=0
    def vend(self):
        if self.stock<=0:
            print(f"'Nothing left to vend. Please restock.'")
        else:
            if self.balance<self.price:
                print(f"'You must add ${self.price-self.balance} more funds.'")
            elif self.balance>self.price:
                print(f"'Here is your {self.name} and ${self.balance-self.price} change.'")
                self.balance=0
                self.stock-=1
            else:
                print(f"'Here is your {self.name}.'")
                self.balance=0
                self.stock-=1
        return

    def add_funds(self,funds):
        if self.stock<=0:
            print(f"'Nothing left to vend. Please restock. Here is your ${funds}.'")
        else:
            self.balance+=funds
            print(f"'Current balance: ${self.balance}'")
        return

    def restock(self,num):
        self.stock+=num
        print(f"'Current {self.name} stock: {self.stock}'")
        return

Q2：Mint

class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.present_year.

    >>> mint = Mint()
    >>> mint.year
    2021
    >>> dime = mint.create(Dime)
    >>> dime.year
    2021
    >>> Mint.present_year = 2101  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2021
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2101
    >>> Mint.present_year = 2176     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    """
    present_year = 2021

    def __init__(self):
        self.update()

    def create(self, kind):
        "*** YOUR CODE HERE ***"
        return kind(self.year)


    def update(self):
        "*** YOUR CODE HERE ***"
        self.year=Mint.present_year


class Coin:
    def __init__(self, year):
        self.year = year

    def worth(self):
        "*** YOUR CODE HERE ***"
        return self.cents+max(0,Mint.present_year-self.year-50)


class Nickel(Coin):
    cents = 5


class Dime(Coin):
    cents = 10

Q3：Store Digits

由于n是从右往左遍历，故也采用向前插入数据构建链表的方法

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> # a check for restricted functions
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    res=Link.empty
    while n>0:
        rem=Link(n%10)   #这里一定要是Link，不能是单独的数字
        rem.rest=res
        res=rem
        n=n//10
    return rem

Q4：Mutable Mapping

def deep_map_mut(fn, link):
    """Mutates a deep link by replacing each item found with the
    result of calling fn on the item.  Does NOT create new Links (so
    no use of Link's constructor)

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> # Disallow the use of making new Links before calling deep_map_mut
    >>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
    >>> try:
    ...     deep_map_mut(lambda x: x * x, link1)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    <9 <16> 25 36>
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:    #不能忘了link为empty的情况，否则递归无法完成
        return
    else:
        if isinstance(link.first,Link):
            deep_map_mut(fn,link.first)
        else:
            link.first=fn(link.first)
        deep_map_mut(fn,link.rest)

Q5:Two List

主要是想办法把vals的元素与amounts中相应位置的数量联系起来

def two_list(vals, amounts):
    """
    Returns a linked list according to the two lists that were passed in. Assume
    vals and amounts are the same size. Elements in vals represent the value, and the
    corresponding element in amounts represents the number of this value desired in the
    final linked list. Assume all elements in amounts are greater than 0. Assume both
    lists have at least one element.

    >>> a = [1, 3, 2]
    >>> b = [1, 1, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(3, Link(2)))
    >>> a = [1, 3, 2]
    >>> b = [2, 2, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(1, Link(3, Link(3, Link(2)))))
    """
    "*** YOUR CODE HERE ***"
    vals.reverse()
    amounts.reverse()
    res=Link.empty
    for i in range(len(vals)):
        for j in range(amounts[i]):
            res=Link(vals[i],res)
    return res

Lab 08：Linked Lists, Mutable Trees

Q2：Convert Link

简单的recursive

def convert_link(link):
    """Takes a linked list and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> convert_link(link)
    [1, 2, 3, 4]
    >>> convert_link(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"
    if link==Link.empty:
      return []
    else:
      return [link.first]+convert_link(link.rest)

Q4：Square

def label_squarer(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> label_squarer(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    #if t.is_leaf():
      #t.label=t.label**2
    #else:
    t.label=t.label**2
    for b in t.branches:
      b=label_squarer(b)
    #return t

Q5：Cumulative Mul

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    """
    "*** YOUR CODE HERE ***"
    for b in t.branches:
      cumulative_mul(b)
      t.label*=b.label

Q6：Add Leaves

抄的别人的…

def add_d_leaves(t, v):
  def helper(t,v,depth):
    if t.is_leaf():
      for i in range(depth):
        t.branches.append(v)
      return 
    for b in t.branches:
      helper(b,v,depth+1)
    for i in range(depth):
      t.branches.append(Tree(v))
  helper(t,v,0)

Disc 08：Linked Lists, Trees

均未跑版

Q3:Sum Nums

def sum_nums(s):
    if s.rest.empty:
        return s.first
    else:
        return s.first+sum_nums(s.rest)

Q4：Multiply Links

这个是这一组中最不确定的…

def multiply_lnks(lst_of_lnks):
    """
    >>> a = Link(2, Link(3, Link(5)))
    >>> b = Link(6, Link(4, Link(2)))
    >>> c = Link(4, Link(1, Link(0, Link(2))))
    >>> p = multiply_lnks([a, b, c])
    >>> p.first
    48
    >>> p.rest.first
    12
    >>> p.rest.rest.rest is Link.empty
    True
    """
    # Implementation Note: you might not need all lines in this skeleton code
    res = Link.empty
    for link in lst_of_lnks:
        if link.rest is Link.empty:
            res.rest=Link.empty
        link=link.rest
        res.first*=link.first
	nultiply_lnks(lst_of_lnks)
    return res

Q5：Flip Two

def flip_two(s):
    if s.rest.empty:
        return s
    else:
        store=s.first
        s.first=s.rest.first
        s.rest.first=store
        s.rest.rest=flip_two(s.rest.rest)
        return s

Q6：Make Even

def make_even(t):
    if t.label%2==1:
        t.label+=1
    for b in t.branches:
        b=make_even(b)

Q7：Leaves

def leaves(t):
    if t.is_leaf:
        return [t.label]
    else:
        res=[t.label]
        for b in t.branches:
            res.append(leaves(b))
        return res

Lab 09：Midterm Review（Optional）

Q1：Subsequences

本题关键是怎样利用insert_into_all这个函数，还是利用递归的思想。因为insert_into_all函数的作用是往list里面插入数字，所以递归采取向subseqs(s[1:])中插入s[0]

def insert_into_all(item, nested_list):
    """Return a new list consisting of all the lists in nested_list,
    but with item added to the front of each. You can assume that
     nested_list is a list of lists.

    >>> nl = [[], [1, 2], [3]]
    >>> insert_into_all(0, nl)
    [[0], [0, 1, 2], [0, 3]]
    """
    "*** YOUR CODE HERE ***"
    for list in nested_list:
        list.insert(0,item)
    return nested_list


def subseqs(s):
    """Return a nested list (a list of lists) of all subsequences of S.
    The subsequences can appear in any order. You can assume S is a list.

    >>> seqs = subseqs([1, 2, 3])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    >>> subseqs([])
    [[]]
    """
    if s==[]:
        return [[]]
    else:
        res=insert_into_all(s[0],subseqs(s[1:]))
        return res+subseqs(s[1:])

Q2：Non-Decreasing Subsequences

def non_decrease_subseqs(s):
    """Assuming that S is a list, return a nested list of all subsequences
    of S (a list of lists) for which the elements of the subsequence
    are strictly nondecreasing. The subsequences can appear in any order.

    >>> seqs = non_decrease_subseqs([1, 3, 2])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 3], [2], [3]]
    >>> non_decrease_subseqs([])
    [[]]
    >>> seqs2 = non_decrease_subseqs([1, 1, 2])
    >>> sorted(seqs2)
    [[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
    """
    def subseq_helper(s, prev):
        if not s:
            return [[]]
        elif s[0] < prev:
            return subseq_helper(s[1:],prev)
        else:
            a = subseq_helper(s[1:],s[0])
            b = subseq_helper(s[1:],prev)
            return insert_into_all(s[0], a) + b
    return subseq_helper(s, 0)

Q3：Number of Trees

n个叶子结点的完全二叉树可能有几种？结果是卡特兰数

设h(n)为catalan数的第n项，令h(0)=1,h(1)=1，catalan数满足递推式

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n≥2)

def num_trees(n):
    """Returns the number of unique full binary trees with exactly n leaves. E.g.,

    1   2        3       3    ...
    *   *        *       *
       / \      / \     / \
      *   *    *   *   *   *
              / \         / \
             *   *       *   *

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(8)
    429

    """
    "*** YOUR CODE HERE ***"
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        res=0
        for i in range(1,n):
            res+=num_trees(i)*num_trees(n-i)
        return res

Q4：Merge

def merge(incr_a, incr_b):
    """Yield the elements of strictly increasing iterables incr_a and incr_b, removing
    repeats. Assume that incr_a and incr_b have no repeats. incr_a or incr_b may or may not
    be infinite sequences.

    >>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
    >>> type(m)
    <class 'generator'>
    >>> list(m)
    [0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    >>> def big(n):
    ...    k = 0
    ...    while True: yield k; k += n
    >>> m = merge(big(2), big(3))
    >>> [next(m) for _ in range(11)]
    [0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    """
    iter_a, iter_b = iter(incr_a), iter(incr_b)
    next_a, next_b = next(iter_a, None), next(iter_b, None)
    "*** YOUR CODE HERE ***"
    while next_a is not None and next_b is not None:
        pos_a,pos_b=next_a,next_b
        if pos_a==pos_b:
            yield next_a
            next_a,next_b=next(iter_a,None),next(iter_b,None)
        elif pos_a>pos_b:
            yield next_b
            next_b=next(iter_b,None)
        else:
            yield next_a
            next_a=next(iter_a,None)
#当有迭代器空了的时候
    while next_a:
        yield next_a
        next_a=next(iter_a,None)
    while next_b:
        yield next_b
        next_b=next(iter_b,None)

Q5：Bank Account

class Account:
    """A bank account that allows deposits and withdrawals.
    It tracks the current account balance and a transaction
    history of deposits and withdrawals.

    >>> eric_account = Account('Eric')
    >>> eric_account.deposit(1000000)   # depositing paycheck for the week
    1000000
    >>> eric_account.transactions
    [('deposit', 1000000)]
    >>> eric_account.withdraw(100)      # make a withdrawal to buy dinner
    999900
    >>> eric_account.transactions
    [('deposit', 1000000), ('withdraw', 100)]
    >>> print(eric_account) #call to __str__
    Eric's Balance: $999900
    >>> eric_account.deposit(10)
    999910
    >>> eric_account #call to __repr__
    Accountholder: Eric, Deposits: 2, Withdraws: 1
    """

    interest = 0.02

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        "*** YOUR CODE HERE ***"
        self.deposits=0
        self.withdraws=0
        self.transactions=[]

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """
        "*** YOUR CODE HERE ***"
        self.balance+=amount
        self.deposits+=1
        self.transactions.append(('deposit', amount))
        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.
        """
        "*** YOUR CODE HERE ***"
        self.balance-=amount
        self.withdraws+=1
        self.transactions.append(('withdraw', amount))
        return self.balance


    def __str__(self):
        "*** YOUR CODE HERE ***"
        return f'{self.holder}\'s Balance: ${self.balance}' 

    def __repr__(self):
        "*** YOUR CODE HERE ***"
        return f'Accountholder: {self.holder}, Deposits: {self.deposits}, Withdraws: {self.withdraws}'

Q6：Trade

注意是要交换开头的几个元素

def trade(first, second):
    """Exchange the smallest prefixes of first and second that have equal sum.

    >>> a = [1, 1, 3, 2, 1, 1, 4]
    >>> b = [4, 3, 2, 7]
    >>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
    'Deal!'
    >>> a
    [4, 3, 1, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c = [3, 3, 2, 4, 1]
    >>> trade(b, c)
    'No deal!'
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [3, 3, 2, 4, 1]
    >>> trade(a, c)
    'Deal!'
    >>> a
    [3, 3, 2, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [4, 3, 1, 4, 1]
    >>> d = [1, 1]
    >>> e = [2]
    >>> trade(d, e)
    'Deal!'
    >>> d
    [2]
    >>> e
    [1, 1]
    """
    m, n = 1, 1

    equal_prefix = lambda: sum(first[:m])==sum(second[:n])
    while m<=len(first) and n<=len(second) and sum(first[:m])!=sum(second[:n]):
        if sum(first[:m])<sum(second[:n]):
            m += 1
        else:
            n += 1

    if equal_prefix():
        first[:m], second[:n] = second[:n], first[:m]
        return 'Deal!'
    else:
        return 'No deal!'

Q7:Shuffle

def card(n):
    """Return the playing card numeral as a string for a positive n <= 13."""
    assert type(n) == int and n > 0 and n <= 13, "Bad card n"
    specials = {1: 'A', 11: 'J', 12: 'Q', 13: 'K'}
    return specials.get(n, str(n))


def shuffle(cards):
    """Return a shuffled list that interleaves the two halves of cards.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> suits = ['H', 'D', 'S', 'C']
    >>> cards = [card(n) + suit for n in range(1,14) for suit in suits]
    >>> cards[:12]
    ['AH', 'AD', 'AS', 'AC', '2H', '2D', '2S', '2C', '3H', '3D', '3S', '3C']
    >>> cards[26:30]
    ['7S', '7C', '8H', '8D']
    >>> shuffle(cards)[:12]
    ['AH', '7S', 'AD', '7C', 'AS', '8H', 'AC', '8D', '2H', '8S', '2D', '8C']
    >>> shuffle(shuffle(cards))[:12]
    ['AH', '4D', '7S', '10C', 'AD', '4S', '7C', 'JH', 'AS', '4C', '8H', 'JD']
    >>> cards[:12]  # Should not be changed
    ['AH', 'AD', 'AS', 'AC', '2H', '2D', '2S', '2C', '3H', '3D', '3S', '3C']
    """
    assert len(cards) % 2 == 0, 'len(cards) must be even'
    half = len(cards)//2
    shuffled = []
    for i in range(half):
        shuffled.append(cards[i])
        shuffled.append(cards[i+half])
    return shuffled

Q8：Insert

参考了别人的写法：每次插入前拷贝当前结点

def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> print(link)
    <1 2 3>
    >>> other_link = link
    >>> insert(link, 9001, 0)
    >>> print(link)
    <9001 1 2 3>
    >>> link is other_link # Make sure you are using mutation! Don't create a new linked list.
    True
    >>> insert(link, 100, 2)
    >>> print(link)
    <9001 1 100 2 3>
    >>> insert(link, 4, 5)
    Traceback (most recent call last):
        ...
    IndexError: Out of bounds!
    """
    "*** YOUR CODE HERE ***"
    sto=link
    index_=0
    while sto is not Link.empty:
        if index_==index:
            current_link=Link(sto.first,sto.rest)
            sto.first=value
            sto.rest=current_link
            return
        index_+=1
        sto=sto.rest
    raise IndexError('Out of bounds!')

Q9：Deep Linked List Length

def deep_len(lnk):
    """ Returns the deep length of a possibly deep linked list.

    >>> deep_len(Link(1, Link(2, Link(3))))
    3
    >>> deep_len(Link(Link(1, Link(2)), Link(3, Link(4))))
    4
    >>> levels = Link(Link(Link(1, Link(2)), \
            Link(3)), Link(Link(4), Link(5)))
    >>> print(levels)
    <<<1 2> 3> <4> 5>
    >>> deep_len(levels)
    5
    """
    if lnk is Link.empty:
        return 0
    elif isinstance(lnk,int):
        return 1
    else:
        return deep_len(lnk.first)+deep_len(lnk.rest)

Q10：Linked Lists as Strings

def make_to_string(front, mid, back, empty_repr):
    """ Returns a function that turns linked lists to strings.

    >>> kevins_to_string = make_to_string("[", "|-]-->", "", "[]")
    >>> jerrys_to_string = make_to_string("(", " . ", ")", "()")
    >>> lst = Link(1, Link(2, Link(3, Link(4))))
    >>> kevins_to_string(lst)
    '[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
    >>> kevins_to_string(Link.empty)
    '[]'
    >>> jerrys_to_string(lst)
    '(1 . (2 . (3 . (4 . ()))))'
    >>> jerrys_to_string(Link.empty)
    '()'
    """
    def printer(lnk):
        if lnk is Link.empty:
            return empty_repr
        else:
            return front+str(lnk.first)+mid+printer(lnk.rest)+back
    return printer

Q11：Long Paths

不想写了qwq

先鸽掉

Lab 10：Scheme

Q2：Over or Under

挺简单的，就是刚开始的时候cond的格式搞错了几次

用cond：

(define (over-or-under num1 num2) 
(cond ((< num1 num2) -1)
    ((= num1 num2) 0)
    (else 1)
))

用if：

(define (over-or-under num1 num2) 
(if (< num1 num2) -1
(if (= num1 num2) 0 1))
)

如果有大于2的判断条件，用if嵌套

Q3：Make Adder

(define (make-adder num) 
(lambda (inc)(+ inc num))
)

Q4：Compose

(define (composed f g) 
(lambda (x) (f (g x)))
)

Q5：Make a List

(define lst 
(cons (cons 1 nil) (cons 2 (cons (cons 3 (cons 4 nil)) (cons 5 nil))))
)

HW 07：Scheme

Q1：Thane of Cadr

(define (cadr s) 
(car (cdr s))
)

(define (caddr s) 
(car (cdr (cdr s)))
)

Q2：Ordered

就是base case要搞清楚

(define (ordered? s) 
(cond ((null? s) True)
    ((null? (cdr s)) True)
    ((<= (car s) (car(cdr s))) (ordered? (cdr s)))
    (else False)
    )            #这里用cond就不用另打个括号了
)

Q3：Pow

(define (square x) (* x x))

(define (pow base exp) 
(cond ((= base 1) 1)
    ((= exp 1) base)
    ((even? exp) (* (pow base (/ exp 2)) (pow base (/ exp 2))))
    ((odd? exp) (* base (* (pow base (/ (- exp 1) 2)) (pow base (/ (- exp 1) 2)))))
)               #把后两排的pow改为二者相乘外就过了，原来的timeout，估计是recurse太多次了
)

Disc 10：Scheme, Scheme Lists

Q1：Virahanka-Fibonacci

(define (vir-fib n)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (vir-fib (- n 2)) (vir-fib (- n 1))))
    )
)

(expect (vir-fib 10) 55)
(expect (vir-fib 1) 1)

Q2：List Making

(define with-list
    (list
        (list 'a 'b) 'c 'd (list 'e)
    )
)
(draw with-list)

(define with-quote
    '(
        (a b) c d (e)
    )

)
(draw with-quote)

(define helpful-list
   (cons 'a (cons 'b nil)))
(draw helpful-list)

(define another-helpful-list
    (cons 'c (cons 'd (cons (cons 'e nil) nil))))
(draw another-helpful-list)

(define with-cons
    (cons
        helpful-list another-helpful-list
    )
)
(draw with-cons)

Q3：List Concatenation

(define (list-concat a b)
    (cond ((null? a) b)
        ((null? b) a)
        (else (cons (car a) (list-concat (cdr a) b)))
    )
)

(expect (list-concat '(1 2 3) '(2 3 4)) (1 2 3 2 3 4))
(expect (list-concat '(3) '(2 1 0)) (3 2 1 0))

Q4：Map

(define (map-fn fn lst)
    (cond ((null? lst) nil)
        ((null? (cdr lst)) (fn (car lst)))
        (else (cons (fn (car lst)) (map-fn fn (cdr lst))))
    )
)

(map-fn (lambda (x) (* x x)) '(1 2 3))
; expect (1 4 9)

Q5：Make Tree

(define (make-tree label branches) (cons label branches))

(define (label tree)
    (car tree)
)

(define (branches tree)
    (cdr tree)
)

(make-tree 1 (list (make-tree 2 '()) (make-tree 3 '())))
; expect (1 (2) (3))

Q6：Tree Sum

(define (tree-sum tree)
    (cond ((null? tree) 0)
        (else (cons ((null? (branches tree)) (label tree))
            (else (+ (label tree) (tree-sum (branches tree))))
        )
        )
    )
)

(define (sum lst)
    (cond ((null? lst) 0)
        (else (+ (car lst) (sum (cdr lst))))
    )
)

(define t (make-tree 1 (list (make-tree 2 '()) (make-tree 3 '()))))
(expect (tree-sum t) 6)

HW 08：Scheme Lists

Q1：My Filter

(define (my-filter func lst) 
  (cond ((null? lst) nil)                       
    ((func (car lst)) (cons (car lst) (my-filter func (cdr lst))))
    (else (my-filter func (cdr lst)))
  )
)

Q2：Interleave

(define (interleave s1 s2) 
(cond ((null? s1) s2)
      ((null? s2) s1)
      (else (cons (car s1) (cons (car s2) (interleave (cdr s1) (cdr s2)))))
)
)

Q3：Accumulate

(define (accumulate merger start n term)
  (cond ((= n 1) (merger start (term n)))
        (else (merger (term n) (accumulate merger start (- n 1) term)))
  )
  )

Q4：No Repeats

(define (no-repeats lst) 
  (cond ((null? lst) nil)
        ((null? (cdr lst)) lst)
        ((= (car lst) (car (cdr lst))) (cons (car lst) (no-repeats (cdr (cdr lst)))))
        ((not (= (car lst) (car (cdr lst)))) (cons (car lst) (cons (car (cdr lst)) (no-repeats (cdr (cdr lst))))))
  )
)
#这个版本无法判断后面的数字是否与前面的重复

参考了他人代码：

(define (no-repeats lst) 
  (cond ((null? lst) nil)
        (else (cons (car lst) (no-repeats (filter (lambda (x) (not (= x (car lst)))) (cdr lst))))))
)

感受就是scheme里面的括号太多了，一下子就把自己绕晕了///

Lab 11：Interpreters

Problem 1

def pop_first(self):
        """Remove the next item from self and return it. If self has
        exhausted its source, returns None."""
        # BEGIN PROBLEM 1
        current=self.current()
        self.index+=1
        return current
        # END PROBLEM 1

    def current(self):
        """Return the current element, or None if none exists."""
        while not self.more_on_line():
            self.index=0
            try:
                # BEGIN PROBLEM 1
                self.current_line=next(self.source)
                # END PROBLEM 1
            except StopIteration:
                self.current_line = ()
                return None
        return self.current_line[self.index]

Problem 2、3

照着题目意思写就可以了（感觉像照着答案抄一样

def scheme_read(src):
    """Read the next expression from SRC, a Buffer of tokens.

    >>> scheme_read(Buffer(tokenize_lines(['nil'])))
    nil
    >>> scheme_read(Buffer(tokenize_lines(['1'])))
    1
    >>> scheme_read(Buffer(tokenize_lines(['true'])))
    True
    >>> scheme_read(Buffer(tokenize_lines(['(+ 1 2)'])))
    Pair('+', Pair(1, Pair(2, nil)))
    """
    if src.current() is None:
        raise EOFError
    val = src.pop_first()  # Get and remove the first token
    if val == 'nil':
        # BEGIN PROBLEM 2
        "*** YOUR CODE HERE ***"
        return nil
        # END PROBLEM 2
    elif val == '(':
        # BEGIN PROBLEM 2
        "*** YOUR CODE HERE ***"
        return read_tail(src)
        # END PROBLEM 2
    elif val == "'":
        # BEGIN PROBLEM 3
        "*** YOUR CODE HERE ***"
        return Pair('quote', Pair(scheme_read(src), nil))
        # END PROBLEM 3
    elif val not in DELIMITERS:
        return val
    else:
        raise SyntaxError('unexpected token: {0}'.format(val))


def read_tail(src):
    """Return the remainder of a list in SRC, starting before an element or ).

    >>> read_tail(Buffer(tokenize_lines([')'])))
    nil
    >>> read_tail(Buffer(tokenize_lines(['2 3)'])))
    Pair(2, Pair(3, nil))
    """
    try:
        if src.current() is None:
            raise SyntaxError('unexpected end of file')
        elif src.current() == ')':
            # BEGIN PROBLEM 2
            "*** YOUR CODE HERE ***"
            src.pop_first()
            return nil
            # END PROBLEM 2
        else:
            # BEGIN PROBLEM 2
            "*** YOUR CODE HERE ***"
            return Pair(scheme_read(src), read_tail(src))
            # END PROBLEM 2
    except EOFError:
        raise SyntaxError('unexpected end of file')

Disc 11：Interpreters

Q2：New Procedure

def calc_eval(exp):
    if isinstance(exp, Pair): # Call expressions
        return calc_apply(calc_eval(exp.first), exp.rest.map(calc_eval))
    elif exp in OPERATORS:      # Names
        return OPERATORS[exp]
    else:                       # Numbers
        return exp
def floor_div(expr):
    "*** YOUR CODE HERE ***"
    dividend=expr.first
    expr=expr.rest
    while expr.rest!=nil:
        divisor=expr.first
        dividend//=divisor
        expr=expr.rest
    return dividend
# Assume OPERATORS['//'] = floor_div is added for you in the code

Q3：New Form

def calc_eval(exp):
    if isinstance(exp, Pair):
        if expr.first=='and': # and expressions
            return eval_and(exp.rest)
        else:                   # Call expressions
            return calc_apply(calc_eval(exp.first), exp.rest.map(calc_eval))
    elif exp in OPERATORS:      # Names
        return OPERATORS[exp]
    else:                       # Numbers
        return exp

def eval_and(operands):
    "*** YOUR CODE HERE ***"
    ope=operands
    jud=True
    while ope!=nil:
        jud=calc_eval(ope.first)
        if jud==False:
            return False
        ope=ope.rest
    return jud

Q4：Saving Values

bindings = {}
def calc_eval(exp):
    if isinstance(exp, Pair):
        if exp.first=='and': # and expressions[paste your answer from the earlier]
            return eval_and(exp.rest)
        elif exp.first=='define': # define expressions
            return eval_define(exp.rest)

        else:                   # Call expressions
            return calc_apply(calc_eval(exp.first), exp.rest.map(calc_eval))
    elif exp in bindings: # Looking up variables
        "*** YOUR CODE HERE ***"
        return bindings[exp]
    elif exp in OPERATORS:      # Looking up procedures
        return OPERATORS[exp]
    else:                       # Numbers
        return exp

def eval_define(expr):
    "*** YOUR CODE HERE ***"
    bindings[expr.first]=expr.rest.first
    return expr.first

HW 09：Regular Expressions

这个homework告诉我有时候自学的效果更好…其次就是光听还是不行（因为你不能保证你听懂了…），还是要动手

Q2：Roman Numerals

def roman_numerals(text):
    """
    Finds any string of letters that could be a Roman numeral
    (made up of the letters I, V, X, L, C, D, M).

    >>> roman_numerals("Sir Richard IIV, can you tell Richard VI that Richard IV is on the phone?")
    ['IIV', 'VI', 'IV']
    >>> roman_numerals("My TODOs: I. Groceries II. Learn how to count in Roman IV. Profit")
    ['I', 'II', 'IV']
    >>> roman_numerals("I. Act 1 II. Act 2 III. Act 3 IV. Act 4 V. Act 5")
    ['I', 'II', 'III', 'IV', 'V']
    >>> roman_numerals("Let's play Civ VII")
    ['VII']
    >>> roman_numerals("i love vi so much more than emacs.")
    []
    >>> roman_numerals("she loves ALL editors equally.")
    []
    """
    return re.findall(r'\b([IVXLCDM]+)\b', text)

Q3：CS Classes

def cs_classes(post):
    """
    Returns strings that look like a Berkeley CS class,
    starting with "CS", followed by a number, optionally ending with A, B, or C
    and potentially with a space between "CS" and the number.
    Case insensitive.

    >>> cs_classes("Is it unreasonable to take CS61A, CS61B, CS70, and EE16A in the summer?")
    True
    >>> cs_classes("how do I become a TA for cs61a? that job sounds so fun")
    True
    >>> cs_classes("Can I take ECON101 as a CS major?")
    False
    >>> cs_classes("Should I do the lab lites or regular labs in EE16A?")
    False
    >>> cs_classes("What are some good CS upper division courses? I was thinking about CS 161 or CS 169a")
    True
    """
    return bool(re.search('[Cc][Ss][0-9]+[ABCabc]*', post)) or bool(re.search(r'[Cc][Ss]\s[0-9]+[ABCabc]*', post))

Q4：Time for Times

根据别人的提示去看了题目给的提示（没办法，英语不太好

(?:...), 表示我们想匹配但是不把 () 里的结果保存下来返回.

(? : …)?后面的那个问号表示可选择性

def match_time(text):
    """
    >>> match_time("At 05:24AM, I had sesame bagels with cream cheese before my coffee at 7:23.")
    ['05:24AM', '7:23']
    >>> match_time("At 23:59 I was sound asleep as the time turned to 00:00.")
    ['23:59', '00:00']
    >>> match_time("Mix water in a 1:2 ratio with chicken stock.")
    []
    >>> match_time("At 2:00 I pinged 127.0.0.1:80.")
    ['2:00']
    """
    return re.findall(r'(?:[01]?[0-9]|2[0-3]):[0-5][0-9](?:AM)?', text)

Q5：Most Common Area Code

区号：

• 十位电话号码的前三位
• 可能会用空格括起来，可能会与后面的数字有空格

def area_codes(text):
    """
    Finds all phone numbers in text and captures the area code. Phone numbers
    have 10 digits total and may have parentheses around the area code, and
    hyphens or spaces after the third and sixth digits.

    >>> area_codes('(111) 111 1111, 1234567890 and 123 345 6789 should be matched.')
    ['111', '123', '123']
    >>> area_codes("1234567890 should, but 54321 and 654 456 78901 should not match")
    ['123']
    >>> area_codes("no matches for 12 3456 7890 or 09876-54321")
    []
    """
    return re.findall(r'(?:\()?(\d{3})(?:\))?(?:\s|-)?\d{3}(?:\s|-)?\d{4}\b', text)

\d等同于[0-9]

\d{n}表示有n个[0-9]数

#下面这个求最常见的区号方法比较常规
def most_common_code(text):
    """
    Takes in an input string which contains at least one phone number (and
    may contain more) and returns the most common area code among all phone
    numbers in the input. If there are multiple area codes with the same
    frequency, return the first one that appears in the input text.

    >>> most_common_code('(501) 333 3333')
    '501'
    >>> input_text = '''
    ... (123) 000 1234 and 12454, 098-123-0941, 123 451 0951 and 410-501-3021 has
    ... some phone numbers. '''
    >>> most_common_code(input_text)
    '123'
    """
    "*** YOUR CODE HERE ***"
    mylist=area_codes(text)
    mycount=0
    max=0
    mycode=''
    for code in mylist:
        mycount=mylist.count(code)
        if mycount>max:
            max=mycount
            mycode=code
    return mycode

注意list.count的使用

list.count(x)

Return the number of times x appears in the list.

Project 4：Scheme

Problem 1

把题目说的三种情况都写出来就可以了，注意第二种情况是调用lookup函数

def define(self, symbol, value):
        """Define Scheme SYMBOL to have VALUE."""
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        self.bindings[symbol]=value
        # END PROBLEM 1

    def lookup(self, symbol):
        """Return the value bound to SYMBOL. Errors if SYMBOL is not found."""
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        if symbol in self.bindings:
            return self.bindings[symbol]
        # END PROBLEM 1
        elif self.parent!=None:
            return self.parent.lookup(symbol)
        else:
            raise SchemeError('unknown identifier: {0}'.format(symbol))

Problem 2

可以记住把link化成list的方式：

if isinstance(procedure, BuiltinProcedure):
        # BEGIN PROBLEM 2
        "*** YOUR CODE HERE ***"
        #第一步：把args转化为list
        args_list=[]
        while args:
            args_list.append(args.first)
            args=args.rest
        if procedure.expect_env:
            args_list.append(env)
        try:
            return procedure.py_func(*args_list)
        except TypeError:
            raise SchemeError('incorrect number of arguments')

一遍过的感觉真爽

Problem 3

# All non-atomic expressions are lists (combinations)
    if not scheme_listp(expr):
        raise SchemeError('malformed list: {0}'.format(repl_str(expr)))
    first, rest = expr.first, expr.rest
    if scheme_symbolp(first) and first in scheme_forms.SPECIAL_FORMS:
        return scheme_forms.SPECIAL_FORMS[first](rest, env)
    else:
        # BEGIN PROBLEM 3
        "*** YOUR CODE HERE ***"
        operator=scheme_eval(first,env)
        operands=rest.map(lambda x:scheme_eval(x,env))
        return scheme_apply(operator,operands,env)
        # END PROBLEM 3

Problem 4

if scheme_symbolp(signature):
        # assigning a name to a value e.g. (define x (+ 1 2))
        validate_form(expressions, 2, 2)  # Checks that expressions is a list of length exactly 2
        # BEGIN PROBLEM 4
        "*** YOUR CODE HERE ***"
        env.define(signature,scheme_eval(expressions.rest.first,env))
        return signature
        # END PROBLEM 4

Problem 5

注意expressions的结构：

Pair(A, nil)

A is the quoted expression

def do_quote_form(expressions, env):
    """Evaluate a quote form.

    >>> env = create_global_frame()
    >>> do_quote_form(read_line("((+ x 2))"), env) # evaluating (quote (+ x 2))
    Pair('+', Pair('x', Pair(2, nil)))
    """
    validate_form(expressions, 1, 1)
    # BEGIN PROBLEM 5
    "*** YOUR CODE HERE ***"
    return expressions.first
    # END PROBLEM 5

Problem 6

def eval_all(expressions, env):
    """Evaluate each expression in the Scheme list EXPRESSIONS in
    Frame ENV (the current environment) and return the value of the last.

    >>> eval_all(read_line("(1)"), create_global_frame())
    1
    >>> eval_all(read_line("(1 2)"), create_global_frame())
    2
    >>> x = eval_all(read_line("((print 1) 2)"), create_global_frame())
    1
    >>> x
    2
    >>> eval_all(read_line("((define x 2) x)"), create_global_frame())
    2
    """
    # BEGIN PROBLEM 6
    if expressions==nil:
        return None
    res=nil
    while expressions!=nil:
        res=scheme_eval(expressions.first,env)
        expressions=expressions.rest
    return res
    # END PROBLEM 6

Problem 7

unlocked questions:

lambda_line = read_line(“(lambda (a b c) (+ a b c))”)

lambda_proc = do_lambda_form(lambda_line.rest, env)

lambda_proc.formals:

—Pair(‘a’, Pair(‘b’, Pair(‘c’, nil)))

lambda_proc.body:

—Pair(Pair(‘+’, Pair(‘a’, Pair(‘b’, Pair(‘c’, nil)))), nil)

def do_lambda_form(expressions, env):
    """Evaluate a lambda form.

    >>> env = create_global_frame()
    >>> do_lambda_form(read_line("((x) (+ x 2))"), env) # evaluating (lambda (x) (+ x 2))
    LambdaProcedure(Pair('x', nil), Pair(Pair('+', Pair('x', Pair(2, nil))), nil), <Global Frame>)
    """
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    # BEGIN PROBLEM 7
    "*** YOUR CODE HERE ***"
    return LambdaProcedure(formals,expressions.rest,env)
    # END PROBLEM 7

搞清楚formals=expressions.first，body=expressions.rest

Problem 8

def make_child_frame(self, formals, vals):
        """Return a new local frame whose parent is SELF, in which the symbols
        in a Scheme list of formal parameters FORMALS are bound to the Scheme
        values in the Scheme list VALS. Both FORMALS and VALS are represented as Pairs.
        Raise an error if too many or too few
        vals are given.

        >>> env = create_global_frame()
        >>> formals, expressions = read_line('(a b c)'), read_line('(1 2 3)')
        >>> env.make_child_frame(formals, expressions)
        <{a: 1, b: 2, c: 3} -> <Global Frame>>
        """
        if len(formals) != len(vals):
            raise SchemeError('Incorrect number of arguments to function call')
        # BEGIN PROBLEM 8
        "*** YOUR CODE HERE ***"
        child_frame=Frame(self)
        for i in range(len(formals)):
            child_frame.define(formals.first,vals.first)
            formals=formals.rest
            vals=vals.rest
        return child_frame
        # END PROBLEM 8

Problem 9

elif isinstance(procedure, LambdaProcedure):
        # BEGIN PROBLEM 9
        "*** YOUR CODE HERE ***"
        expr=procedure.env.make_child_frame(procedure.formals,args)
        return eval_all(procedure.body,expr)

Problem 10

elif isinstance(signature, Pair) and scheme_symbolp(signature.first):
        # defining a named procedure e.g. (define (f x y) (+ x y))
        # BEGIN PROBLEM 10
        "*** YOUR CODE HERE ***"
        formals=signature.rest
        validate_formals(formals)
        env.define(signature.first,LambdaProcedure(formals,expressions.rest,env))
        return signature.first
        # END PROBLEM 10

Problem 11

elif isinstance(procedure, MuProcedure):
        # BEGIN PROBLEM 11
        "*** YOUR CODE HERE ***"
        child=env.make_child_frame(procedure.formals,args)
        return eval_all(procedure.body,child)
        # END PROBLEM 11
        
def do_mu_form(expressions, env):
    """Evaluate a mu form."""
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    # BEGIN PROBLEM 11
    "*** YOUR CODE HERE ***"
    return MuProcedure(formals,expressions.rest)
    # END PROBLEM 11

Problem 12

def do_and_form(expressions, env):
    """Evaluate a (short-circuited) and form.

    >>> env = create_global_frame()
    >>> do_and_form(read_line("(#f (print 1))"), env) # evaluating (and #f (print 1))
    False
    >>> # evaluating (and (print 1) (print 2) (print 4) 3 #f)
    >>> do_and_form(read_line("((print 1) (print 2) (print 3) (print 4) 3 #f)"), env)
    1
    2
    3
    4
    False
    """
    # BEGIN PROBLEM 12
    "*** YOUR CODE HERE ***"
    if expressions==nil:
        return True
    elif expressions.rest==nil:
        return scheme_eval(expressions.first,env)
    else:
        first_expr=scheme_eval(expressions.first,env)
        if is_scheme_true(first_expr):
            return do_and_form(expressions.rest,env)
        else:
            return False
    # END PROBLEM 12


def do_or_form(expressions, env):
    """Evaluate a (short-circuited) or form.

    >>> env = create_global_frame()
    >>> do_or_form(read_line("(10 (print 1))"), env) # evaluating (or 10 (print 1))
    10
    >>> do_or_form(read_line("(#f 2 3 #t #f)"), env) # evaluating (or #f 2 3 #t #f)
    2
    >>> # evaluating (or (begin (print 1) #f) (begin (print 2) #f) 6 (begin (print 3) 7))
    >>> do_or_form(read_line("((begin (print 1) #f) (begin (print 2) #f) 6 (begin (print 3) 7))"), env)
    1
    2
    6
    """
    # BEGIN PROBLEM 12
    "*** YOUR CODE HERE ***"
    if expressions==nil:
        return False
    elif expressions.rest==nil:
        return scheme_eval(expressions.first,env)
    else:
        fir=scheme_eval(expressions.first,env)
        if is_scheme_false(fir):
            return do_or_form(expressions.rest,env)
        else:
            return fir
    # END PROBLEM 12

Problem 13

这个比较简单

def do_cond_form(expressions, env):
    """Evaluate a cond form.

    >>> do_cond_form(read_line("((#f (print 2)) (#t 3))"), create_global_frame())
    3
    """
    while expressions is not nil:
        clause = expressions.first
        validate_form(clause, 1)
        if clause.first == 'else':
            test = True
            if expressions.rest != nil:
                raise SchemeError('else must be last')
        else:
            test = scheme_eval(clause.first, env)
        if is_scheme_true(test):
            # BEGIN PROBLEM 13
            "*** YOUR CODE HERE ***"
            if clause.rest==nil:
                return test
            else:
                return eval_all(clause.rest,env)
        else:
            # END PROBLEM 13
            expressions = expressions.rest

Problem 14

def make_let_frame(bindings, env):
    """Create a child frame of Frame ENV that contains the definitions given in
    BINDINGS. The Scheme list BINDINGS must have the form of a proper bindings
    list in a let expression: each item must be a list containing a symbol
    and a Scheme expression."""
    if not scheme_listp(bindings):
        raise SchemeError('bad bindings list in let form')
    names = values = nil
    # BEGIN PROBLEM 14
    "*** YOUR CODE HERE ***"
    while bindings!=nil:
        validate_form(bindings.first,2,2)
        names=Pair(bindings.first.first,names)
        values=Pair(scheme_eval(bindings.first.rest.first,env),values)
        bindings=bindings.rest
    validate_formals(names)
    # END PROBLEM 14
    return env.make_child_frame(names, values)

Problem 15

(define (enumerate s)
  ; BEGIN PROBLEM 15
  (define (helper index s)
    (if (null? s) nil
        (cons (list index (car s)) (helper (+ 1 index) (cdr s)))
    )
    )
    (helper 0 s)
  )
  ; END PROBLEM 15

Problem 16

(define (merge inorder? list1 list2)
  ; BEGIN PROBLEM 16
  (cond ((null? list1) list2)
        ((null? list2) list1)
        ((inorder? (car list1) (car list2)) (cons (car list1) (merge inorder? (cdr list1) list2)))
        (else (cons (car list2) (merge inorder? list1 (cdr list2))))
  )
  )
  ; END PROBLEM 16

终于把scheme这个project写完了

（虽然有好几题都是参考别人的思路与代码，因为不太能理解题目的英文以及不熟悉题目给的函数ww

Lab 12：Regular Expressions, BNF

Q1：Calculator Ops

就是要找出类似“(* 2 4)”这样的格式

注意多位数是由[0-9]+打出来的，不要漏了+号

import re


def calculator_ops(calc_str):
    """
    Finds expressions from the Calculator language that have two
    numeric operands and returns the expression without the parentheses.

    >>> calculator_ops("(* 2 4)")
    ['* 2 4']
    >>> calculator_ops("(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))")
    ['* 2 4', '+ 3 5', '- 10 7']
    >>> calculator_ops("(* 2)")
    []
    """
    return re.findall(r'[+*-/]\s[0-9]+\s[0-9]+', calc_str)

Q3：Linked List BNF

就是要写一个能匹配链表的grammer

注：NUMBER指数字

link: "Link("link_first")"|"Link("link_first","link_rest")"
    
    ?link_first: NUMBER | link
    
    ?link_rest: NUMBER | link
    
    %ignore /\s+/
    %import common.NUMBER

Q4：Tree BNF

tree_node: "Tree("label")"|"Tree("label","branches")"
    
    
    ?label: NUMBER
    
    branches: "["tree_node"]"|"["tree_node","tree_node+"]"
    
    %ignore /\s+/
    %import common.NUMBER

Disc 12：Regular Expressions, BNF, SQL

Q2：SELECTs in BNF

Q3~5

SELECT name FROM records WHERE supervisor="Oliver Warbucks";

SELECT name FROM records WHERE supervisor=name

SELECT name FROM records WHERE salary>50000 ORDER BY name asc

Q6：Email Domain Validator

import re
def email_validator(email, domains):
    """
    >>> email_validator("oski@berkeley.edu", ["berkeley.edu", "gmail.com"])
    True
    >>> email_validator("oski@gmail.com", ["berkeley.edu", "gmail.com"])
    True
    >>> email_validator("oski@berkeley.com", ["berkeley.edu", "gmail.com"])
    False
    >>> email_validator("oski@berkeley.edu", ["yahoo.com"])
    False
    >>> email_validator("xX123_iii_OSKI_iii_123Xx@berkeley.edu", ["berkeley.edu", "gmail.com"])
    True
    >>> email_validator("oski@oski@berkeley.edu", ["berkeley.edu", "gmail.com"])
    False
    >>> email_validator("oski@berkeleysedu", ["berkeley.edu", "gmail.com"])
    False
    """
    pattern = r"^\w+@("
    for domain in domains:
        if domain ==domains[-1]:
            pattern+=domain[:-4]+r"\."+domain[-3:]+r")$"
        else:
            pattern+=domain[:-4]+r"\."+domain[-3:]+"|"
    return bool(re.search(pattern, email))

HW 10：BNF, SQL

决定了，从这里开始暂时都鸽掉…

Q4：Size of Dogs

将两个table联系起来可以用dot

CREATE TABLE size_of_dogs AS
  SELECT d.name, s.size from dogs as d, sizes as s where d.height<=s.max and d.height>s.min;

Q5：By Parent Height

Lab 13：SQL

Lab 14：Final Review

Disc 14：Final Review