*Due by 11:59pm on Tuesday, 10/15*

**Submission.** See the online submission instructions.
We have provided a hw5.py starter file for the questions below.

**Q1.** Define a function `reverse_list` that takes a list as an argument and
returns `None`, but reverses the elements in the list as a side effect.
Do not use any built-in `list` methods (especially not `reverse`) or
slicing, but element assignment statements are fine:

def reverse_list(s): """Reverse the contents of list s and return None. >>> digits = [6, 2, 9, 5, 1, 4, 1, 3] >>> reverse_list(digits) >>> digits [3, 1, 4, 1, 5, 9, 2, 6] >>> d = digits >>> reverse_list(d) >>> digits [6, 2, 9, 5, 1, 4, 1, 3] """ "*** YOUR CODE HERE ***"

*Hint*: This question was also asked in discussion 5, so you get a freebie. You
should try to implement it on your own before looking up the answer, though!

**Q2.** Define a function `shuffle` that takes a list with an even number of
elements (cards) and creates a new list that interleaves the elements of the
first half with the elements of the second half:

def card(n): """Return the playing card type 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. >>> suits = ['♡', '♢', '♤', '♧'] >>> cards = [card(n) + suit for n in range(1,14) for suit in suits] >>> cards[:12] ['A♡', 'A♢', 'A♤', 'A♧', '2♡', '2♢', '2♤', '2♧', '3♡', '3♢', '3♤', '3♧'] >>> cards[26:30] ['7♤', '7♧', '8♡', '8♢'] >>> shuffle(cards)[:12] ['A♡', '7♤', 'A♢', '7♧', 'A♤', '8♡', 'A♧', '8♢', '2♡', '8♤', '2♢', '8♧'] >>> shuffle(shuffle(cards))[:12] ['A♡', '4♢', '7♤', '10♧', 'A♢', '4♤', '7♧', 'J♡', 'A♤', '4♧', '8♡', 'J♢'] >>> cards[:12] # Should not be changed ['A♡', 'A♢', 'A♤', 'A♧', '2♡', '2♢', '2♤', '2♧', '3♡', '3♢', '3♤', '3♧'] """ assert len(cards) % 2 == 0, 'len(cards) must be even' "*** YOUR CODE HERE ***"

**Q3.** Write a version of the mutable `make_withdraw` function from lecture
that returns password-protected withdraw functions. That is, `make_withdraw`
should take a password argument (a string) in addition to an initial balance.
The returned function should take two arguments: an amount to withdraw and a
password.

A password-protected `withdraw` function should only process withdrawals that
include a password that matches the original. Upon receiving an incorrect
password, the function should:

- Store that incorrect password in a list, and
- Return the string 'Incorrect password'.

If a withdraw function has been called three times with incorrect passwords
`p1`, `p2`, and `p3`, then it is locked. All subsequent calls to the
function should return:

`"Your account is locked. Attempts: [<p1>, <p2>, <p3>]"`

The incorrect passwords may be the same or different:

def make_withdraw(balance, password): """Return a password-protected withdraw function. >>> w = make_withdraw(100, 'hax0r') >>> w(25, 'hax0r') 75 >>> w(90, 'hax0r') 'Insufficient funds' >>> w(25, 'hwat') 'Incorrect password' >>> w(25, 'hax0r') 50 >>> w(75, 'a') 'Incorrect password' >>> w(10, 'hax0r') 40 >>> w(20, 'n00b') 'Incorrect password' >>> w(10, 'hax0r') "Your account is locked. Attempts: ['hwat', 'a', 'n00b']" >>> w(10, 'l33t') "Your account is locked. Attempts: ['hwat', 'a', 'n00b']" """ "*** YOUR CODE HERE ***"

**Q4.** Suppose that our banking system requires the ability to make joint
accounts. Define a function `make_joint` that takes three arguments.

- A password-protected
`withdraw`function, - The password with which that
`withdraw`function was defined, and - A new password that can also access the original account.

The `make_joint` function returns a `withdraw` function that provides
additional access to the original account using *either* the new or old
password. Both functions draw down the same balance. Incorrect passwords
provided to either function will be stored and cause the functions to be locked
after three wrong attempts.

*Hint*: The solution is short (less than 10 lines) and contains no string
literals! The key is to call `withdraw` with the right password and
interpret the result. You may assume that all failed attempts to withdraw will
return some string (for incorrect passwords, locked accounts, or insufficient
funds), while successful withdrawals will return a number.

Use `type(value) == str` to test if some `value` is a string:

def make_joint(withdraw, old_password, new_password): """Return a password-protected withdraw function that has joint access to the balance of withdraw. >>> w = make_withdraw(100, 'hax0r') >>> w(25, 'hax0r') 75 >>> make_joint(w, 'my', 'secret') 'Incorrect password' >>> j = make_joint(w, 'hax0r', 'secret') >>> w(25, 'secret') 'Incorrect password' >>> j(25, 'secret') 50 >>> j(25, 'hax0r') 25 >>> j(100, 'secret') 'Insufficient funds' >>> j2 = make_joint(j, 'secret', 'code') >>> j2(5, 'code') 20 >>> j2(5, 'secret') 15 >>> j2(5, 'hax0r') 10 >>> j2(25, 'password') 'Incorrect password' >>> j2(5, 'secret') "Your account is locked. Attempts: ['my', 'secret', 'password']" >>> j(5, 'secret') "Your account is locked. Attempts: ['my', 'secret', 'password']" >>> w(5, 'hax0r') "Your account is locked. Attempts: ['my', 'secret', 'password']" >>> make_joint(w, 'hax0r', 'hello') "Your account is locked. Attempts: ['my', 'secret', 'password']" """ "*** YOUR CODE HERE ***"

**ALL FOLLOWING QUESTIONS ARE EXTRA FOR EXPERTS (OPTIONAL)**

Section 2.4.8 describes a system for solving equations with multiple free parameters using constraint programming, a declarative style of programming that asserts constraints and then applies a general method of constraint satisfaction. The following questions ask you to extend that system. The code for the system appears at the end of this homework.

**Q5.** (Extra for experts) Implement the function `triangle_area` that
defines a relation among three connectors, the
base `b`, height `h`, and area `a` of a triangle, so that `a = 0.5 * b *
h`:

def triangle_area(a, b, h): """Connect a, b, and h so that a is the area of a triangle with base b and height h. >>> a, b, h = [connector(n) for n in ('area', 'base', 'height')] >>> triangle_area(a, b, h) >>> a['set_val']('user', 75.0) area = 75.0 >>> b['set_val']('user', 15.0) base = 15.0 height = 10.0 """ "*** YOUR CODE HERE ***"

**Q6.** (Extra for experts) The `multiplier` constraint from the lecture
notes is insufficient to model equations that include squared quantities
because constraint networks must not include loops. Implement a new constraint
`squarer` that represents the squaring relation:

def squarer(a, b): """The constraint that a*a=b. >>> x, y = connector('X'), connector('Y') >>> s = squarer(x, y) >>> x['set_val']('user', 10) X = 10 Y = 100 >>> x['forget']('user') X is forgotten Y is forgotten >>> y['set_val']('user', 16) Y = 16 X = 4.0 """ "*** YOUR CODE HERE ***"

**Q7.** (Extra for experts) Use your `squarer` constraint to build a
constraint network for the Pythagorean theorem: `a` squared plus `b`
squared equals `c` squared:

def pythagorean(a, b, c): """Connect a, b, and c into a network for the Pythagorean theorem: a*a + b*b = c*c >>> a, b, c = [connector(name) for name in ('A', 'B', 'C')] >>> pythagorean(a, b, c) >>> a['set_val']('user', 5) A = 5 >>> c['set_val']('user', 13) C = 13 B = 12.0 """ "*** YOUR CODE HERE ***"

The equation solver implementation from the lecture notes:

def connector(name=None): """A connector between constraints. >>> celsius = connector('Celsius') >>> fahrenheit = connector('Fahrenheit') >>> converter(celsius, fahrenheit) >>> celsius['set_val']('user', 25) Celsius = 25 Fahrenheit = 77.0 >>> fahrenheit['set_val']('user', 212) Contradiction detected: 77.0 vs 212 >>> celsius['forget']('user') Celsius is forgotten Fahrenheit is forgotten >>> fahrenheit['set_val']('user', 212) Fahrenheit = 212 Celsius = 100.0 """ informant = None # The source of the current val constraints = [] # A list of connected constraints def set_value(source, value): nonlocal informant val = connector['val'] if val is None: informant, connector['val'] = source, value if name is not None: print(name, '=', value) inform_all_except(source, 'new_val', constraints) else: if val != value: print('Contradiction detected:', val, 'vs', value) def forget_value(source): nonlocal informant if informant == source: informant, connector['val'] = None, None if name is not None: print(name, 'is forgotten') inform_all_except(source, 'forget', constraints) connector = {'val': None, 'set_val': set_value, 'forget': forget_value, 'has_val': lambda: connector['val'] is not None, 'connect': lambda source: constraints.append(source)} return connector def inform_all_except(source, message, constraints): """Inform all constraints of the message, except source.""" for c in constraints: if c != source: c[message]() def ternary_constraint(a, b, c, ab, ca, cb): """The constraint that ab(a,b)=c and ca(c,a)=b and cb(c,b)=a.""" def new_value(): av, bv, cv = [connector['has_val']() for connector in (a, b, c)] if av and bv: c['set_val'](constraint, ab(a['val'], b['val'])) elif av and cv: b['set_val'](constraint, ca(c['val'], a['val'])) elif bv and cv: a['set_val'](constraint, cb(c['val'], b['val'])) def forget_value(): for connector in (a, b, c): connector['forget'](constraint) constraint = {'new_val': new_value, 'forget': forget_value} for connector in (a, b, c): connector['connect'](constraint) return constraint from operator import add, sub, mul, truediv def adder(a, b, c): """The constraint that a + b = c.""" return ternary_constraint(a, b, c, add, sub, sub) def multiplier(a, b, c): """The constraint that a * b = c.""" return ternary_constraint(a, b, c, mul, truediv, truediv) def constant(connector, value): """The constraint that connector = value.""" constraint = {} connector['set_val'](constraint, value) return constraint def converter(c, f): """Connect c to f to convert from Celsius to Fahrenheit.""" u, v, w, x, y = [connector() for _ in range(5)] multiplier(c, w, u) multiplier(v, x, u) adder(v, y, f) constant(w, 9) constant(x, 5) constant(y, 32)