[CS61A] Lecture 4. Higher-Order Functions & Project 1: The Game of Hog
Lecture
Lecture 4. Higher-Order Functions
本节课介绍了高阶函数的概念与用法，主要包含如下内容：
- 从斐波那契数列说起，定义fib函数并使用迭代法解答。
面积公式，介绍正方形、五边形以及圆形的面积公式，它们的共同点是面积公式都可以变为：半径x半径x面积系数 的形式，因此将函数抽象成一个通用函数。
求和公式，西格玛求和公式可以通过一个包含序列长度n和元素计算函数term的方式表达，就此引入高阶函数的概念。
局部函数：在非全局作用域中定义的函数，例如make_adder函数接受一个整数n，返回用来+n的函数adder。
高阶函数：将函数作为参数或返回值的函数。
匿名函数：lambda函数，没有绑定名称的函数。
return关键词：表示函数的结束，函数有两种返回的方法，一种是当满足条件时返回，另一个是判断所有不满足的条件后返回。
控制语句if、else，控制表达式and、or、x if a else b。
Q&A：lambda函数
Project 1: The Game of Hog
Phase 1: Rules of the Game
该项目要求充分运用python中控制与高阶函数相关的知识，实现一个hog游戏。
Problem 0 (0 pt)
要求在dice.py文件中实现一个公平的骰子。实际上是个判断题，判断多个骰子函数中哪个才是真正公平的骰子，答案是a) six_sided()。
执行测试用例：
$ python3 ok -q 00 -u
Question 0 > Suite 1 > Case 1
? 4
? 1
? 2
? 4
---------------------------------------------------------------------
Question 0 > Suite 2 > Case 1
? 0
Problem 1 (2 pt)
要求在hog.py中实现roll_dice函数。
roll_dice函数：
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
res = [dice() for _ in range(num_rolls)]
return 1 if 1 in res else sum(res)
# END PROBLEM 1
执行测试用例：
$ python3 ok -q 01 -u
Question 1 > Suite 1 > Case 1
? 10
---------------------------------------------------------------------
Question 1 > Suite 1 > Case 2
? 1
---------------------------------------------------------------------
Question 1 > Suite 1 > Case 3
? 1
---------------------------------------------------------------------
Question 1 > Suite 1 > Case 5
? 1
? 6
---------------------------------------------------------------------
Question 1 > Suite 1 > Case 6
? 54
$ python3 ok -q 01
Test summary
59 test cases passed! No cases failed.
Problem 2 (4 pt)
要求实现oink_points函数。
oink_points函数：
def oink_points(player_score, opponent_score):
"""Return the points scored by player due to Oink Points.
player_score: The total score of the current player.
opponent_score: The total score of the other player.
"""
ones = opponent_score%10
tens = opponent_score//10%10
return max(2*tens-ones, 1)
执行测试用例：
$ python3 ok -q 02 -u
Question 2 > Suite 1 > Case 1
? 1
---------------------------------------------------------------------
Question 2 > Suite 1 > Case 2
? 12
---------------------------------------------------------------------
Question 2 > Suite 1 > Case 3
? 1
$ python3 ok -q 02
Test summary
34 test cases passed! No cases failed.
Problem 3 (2 pt)
要求实现take_turn函数。
take_turn函数：
def take_turn(num_rolls, player_score, 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 Oink Points.
Return the points scored for the turn by the current player.
num_rolls: The number of dice rolls that will be made.
player_score: The total score of the current player.
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 max(player_score, opponent_score) < goal, 'The game should be over.'
# BEGIN PROBLEM 3
if num_rolls==0:
return oink_points(player_score, opponent_score)
return roll_dice(num_rolls, dice)
# END PROBLEM 3
执行测试用例：
$ python3 ok -q 03 -u
Question 3 > Suite 1 > Case 1
? 9
---------------------------------------------------------------------
Question 3 > Suite 1 > Case 2
? 1
---------------------------------------------------------------------
Question 3 > Suite 1 > Case 3
? 7
---------------------------------------------------------------------
Question 3 > Suite 1 > Case 4
? 1
$ python3 ok -q 03
Test summary
10 test cases passed! No cases failed.
Problem 4 (1 pt)
要求实现pigs_on_prime函数。
pigs_on_prime函数：
def pigs_on_prime(player_score, opponent_score):
"""Return the points scored by the current player due to Pigs on Prime.
player_score: The total score of the current player.
opponent_score: The total score of the other player.
"""
# BEGIN PROBLEM 4
if not is_prime(player_score):
return 0
additional_score = 1
while not is_prime(player_score+additional_score):
additional_score+=1
return additional_score
# END PROBLEM 4
执行测试用例：
$ python3 ok -q 04 -u
Question 4 > Suite 1 > Case 1
? 0
---------------------------------------------------------------------
Question 4 > Suite 1 > Case 2
? 4
---------------------------------------------------------------------
Question 4 > Suite 1 > Case 3
? 0
---------------------------------------------------------------------
Question 4 > Suite 1 > Case 4
? 2
---------------------------------------------------------------------
Question 4 > Suite 1 > Case 5
? 2
$ python3 ok -q 04
Test summary
105 test cases passed! No cases failed.
Phase 2: Playing the Game
Problem 5 (5 pt)
要求实现play函数。
play函数：
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 every turn.
"""
who = 0 # Who is about to take a turn, 0 (first) or 1 (second)
leader = None # To be used in problem 7
# BEGIN PROBLEM 5
while score0 < goal and score1 < goal:
if who == 0:
score0 += take_turn(strategy0(score0, score1), score0, score1, dice, goal)
score0 += pigs_on_prime(score0, score1)
else:
score1 += take_turn(strategy1(score1, score0), score1, score0, dice, goal)
score1 += pigs_on_prime(score1, score0)
who = next_player(who)
# END PROBLEM 5
# (note that the indentation for the problem 7 prompt (***YOUR CODE HERE***) might be misleading)
# BEGIN PROBLEM 7
"*** YOUR CODE HERE ***"
# END PROBLEM 7
return score0, score1
执行测试用例：
$ python3 ok -q 05 -u
Question 5 > Suite 1 > Case 1
? 2
---------------------------------------------------------------------
Question 5 > Suite 1 > Case 2
? 1
---------------------------------------------------------------------
Question 5 > Suite 1 > Case 3
? 3
---------------------------------------------------------------------
Question 5 > Suite 2 > Case 1
? 106
? 10
---------------------------------------------------------------------
Question 5 > Suite 2 > Case 2
? 15
? 0
---------------------------------------------------------------------
Question 5 > Suite 3 > Case 1
? 87
? 108
$ python3 ok -q 05
Test summary
111 test cases passed! No cases failed.
Problem 6 (2 pt)
要求实现announce_lead_changes函数。
announce_lead_changes函数：
def announce_lead_changes(score0, score1, last_leader=None):
"""A commentary function that announces when the leader has changed.
>>> leader, message = announce_lead_changes(5, 0)
>>> print(message)
Player 0 takes the lead by 5
>>> leader, message = announce_lead_changes(5, 12, leader)
>>> print(message)
Player 1 takes the lead by 7
>>> leader, message = announce_lead_changes(8, 12, leader)
>>> print(leader, message)
1 None
>>> leader, message = announce_lead_changes(8, 13, leader)
>>> leader, message = announce_lead_changes(15, 13, leader)
>>> print(message)
Player 0 takes the lead by 2
"""
# BEGIN PROBLEM 6
if score0 == score1:
leader = None
changes = 0
elif score0 < score1:
leader = 1
changes = score1-score0
else:
leader = 0
changes = score0-score1
return leader, f'Player {leader} takes the lead by {changes}' if leader != last_leader and leader != None else None
# END PROBLEM 6
执行测试用例：
$ python3 ok -q 06 -u
Question 6 > Suite 1 > Case 1
? 1
---------------------------------------------------------------------
Question 6 > Suite 1 > Case 2
? 0
---------------------------------------------------------------------
Question 6 > Suite 1 > Case 3
? 0
$ python3 ok -q 06
Test summary
4 test cases passed! No cases failed.
Problem 7 (2 pt)
要求更新play函数，
函数：
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 every turn.
"""
who = 0 # Who is about to take a turn, 0 (first) or 1 (second)
leader = None # To be used in problem 7
# BEGIN PROBLEM 5
while score0 < goal and score1 < goal:
if who == 0:
score0 += take_turn(strategy0(score0, score1), score0, score1, dice, goal)
score0 += pigs_on_prime(score0, score1)
else:
score1 += take_turn(strategy1(score1, score0), score1, score0, dice, goal)
score1 += pigs_on_prime(score1, score0)
who = next_player(who)
# END PROBLEM 5
# (note that the indentation for the problem 7 prompt (***YOUR CODE HERE***) might be misleading)
# BEGIN PROBLEM 7
leader, message = say(score0, score1, leader)
print(message) if message else 0
# END PROBLEM 7
return score0, score1
执行测试用例：
$ python3 ok -q 07 -u
Question 7 > Suite 1 > Case 1
? 0
---------------------------------------------------------------------
Question 7 > Suite 2 > Case 3
(line 1)? 5 0
(line 2)? 5 5
(line 3)? 8 5
---------------------------------------------------------------------
Question 7 > Suite 2 > Case 4
(line 1)? 1 7
(line 2)? 2 7
(line 3)? 3 12
(line 4)? 4 12
(line 5)? 5 19
---------------------------------------------------------------------
Question 7 > Suite 3 > Case 1
(line 1)? 4 0
(line 2)? 4 12
(line 3)? 7 12
(line 4)? 7 24
---------------------------------------------------------------------
Question 7 > Suite 3 > Case 2
(line 1)? 3
(line 2)? 10
(line 3)? 14
(line 4)? 19
---------------------------------------------------------------------
Question 7 > Suite 3 > Case 3
(line 1)? * 3
(line 2)? ** 0
(line 3)? * 3
(line 4)? ** 3
(line 5)? * 7
(line 6)? ** 3
$ python3 ok -q 07
Test summary
9 test cases passed! No cases failed.
Phase 3: Strategies of the Game
Problem 8 (2 pt)
实现make_averaged函数。
make_averaged函数：
def make_averaged(original_function, total_samples=1000):
"""Return a function that returns the average value of ORIGINAL_FUNCTION
called TOTAL_SAMPLES 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
def inner(*args):
return sum([original_function(*args) for _ in range(total_samples)])/total_samples
return inner
# END PROBLEM 8
执行测试用例：
$ python3 ok -q 08 -u
Question 8 > Suite 1 > Case 1
? 3
---------------------------------------------------------------------
Question 8 > Suite 1 > Case 2
? 0
---------------------------------------------------------------------
Question 8 > Suite 2 > Case 1
? 3.75
---------------------------------------------------------------------
Question 8 > Suite 2 > Case 2
? 6.0
$ python3 ok -q 08
Test summary
7 test cases passed! No cases failed.
Problem 9 (2 pt)
实现max_scoring_num_rolls函数。
max_scoring_num_rolls函数：
def max_scoring_num_rolls(dice=six_sided, total_samples=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 TOTAL_SAMPLES times.
Assume that the dice always return positive outcomes.
>>> dice = make_test_dice(1, 6)
>>> max_scoring_num_rolls(dice)
1
"""
# BEGIN PROBLEM 9
new_roll_dice = make_averaged(roll_dice, total_samples)
return max([(new_roll_dice(i, dice), i) for i in range(1, 11)], key=lambda x: x[0])[1]
# END PROBLEM 9
执行测试用例：
$ python3 ok -q 09 -u
Question 9 > Suite 1 > Case 1
? 2
---------------------------------------------------------------------
Question 9 > Suite 2 > Case 1
? 10
---------------------------------------------------------------------
Question 9 > Suite 3 > Case 1
? 10
---------------------------------------------------------------------
Question 9 > Suite 3 > Case 2
? 1
---------------------------------------------------------------------
Question 9 > Suite 3 > Case 3
? 1
$ python3 ok -q 09
Test summary
10 test cases passed! No cases failed.
Problem 10 (1 pt)
要求实现oink_points_strategy函数。
oink_points_strategy函数：
def oink_points_strategy(score, opponent_score, threshold=8, num_rolls=6):
"""This strategy returns 0 dice if that gives at least THRESHOLD points, and
returns NUM_ROLLS otherwise.
"""
# BEGIN PROBLEM 10
return 0 if oink_points(score, opponent_score) >= threshold else num_rolls
# END PROBLEM 10
执行测试用例：
$ python3 ok -q 10 -u
Question 10 > Suite 1 > Case 1
? 0
---------------------------------------------------------------------
Question 10 > Suite 1 > Case 2
? 5
---------------------------------------------------------------------
Question 10 > Suite 1 > Case 3
? 0
---------------------------------------------------------------------
Question 10 > Suite 1 > Case 4
? 4
---------------------------------------------------------------------
Question 10 > Suite 1 > Case 5
? 0
$ python3 ok -q 10
Test summary
106 test cases passed! No cases failed.
Problem 11 (1 pt)
要求实现pigs_on_prime_strategy函数。
pigs_on_prime_strategy函数：
def pigs_on_prime_strategy(score, opponent_score, threshold=8, num_rolls=6):
"""This strategy returns 0 dice when this would result in Pigs on Prime taking
effect. It also returns 0 dice if it gives at least THRESHOLD points.
Otherwise, it returns NUM_ROLLS.
"""
# BEGIN PROBLEM 11
additional = oink_points(score, opponent_score)
return 0 if pigs_on_prime(score+additional, opponent_score) != 0 or additional >= threshold else num_rolls
# END PROBLEM 11
执行测试用例：
$ python3 ok -q 11 -u
Question 11 > Suite 1 > Case 1
? 0
---------------------------------------------------------------------
Question 11 > Suite 1 > Case 2
? 6
---------------------------------------------------------------------
Question 11 > Suite 1 > Case 3
? 0
---------------------------------------------------------------------
Question 11 > Suite 1 > Case 4
? 6
$ python3 ok -q 11
Test summary
105 test cases passed! No cases failed.
Optional: Problem 12 (0 pt)
要求实现final_strategy函数，该题为开放题，思考怎样结合oink_points或pigs_on_prime策略，让玩家赢的概率才能够更大。
参考资料
CS61A Project 1: The Game of Hog：https://cs61a.org/proj/hog/
cs61a公开课视频：https://www.bilibili.com/video/BV1s3411G7yM
