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

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

**Readings:** You might find the following references
useful:

- Question 1
- Question 2
- Question 3
- Question 4
- Question 5
- Question 6: Challenge Problem (optional)
- Question 7: Challenge Problem (optional)

Define a function `shuffle`

that takes a sequence 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 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 = ['♡', '♢', '♤', '♧']
>>> 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 ***"
```

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their integers that are equal in sum. A prefix is a slice that starts at index 0.

Write a function `trade`

that exchanges the first `m`

elements of list `first`

with the first `n`

elements of list `second`

, such that the sums of those
elements are equal, and the sum is as small as possible. If no such prefix
exists, return the string `'No deal!'`

and do not change either list. Otherwise
change both lists and return `'Deal!'`

. A partial implementation is provided.

```
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]
"""
m, n = 1, 1
equal_prefix = lambda: sum(first[:m]) == sum(second[:n])
"*** YOUR CODE HERE ***"
if equal_prefix():
first[:m], second[:n] = second[:n], first[:m]
return 'Deal!'
else:
return 'No deal!'
```

**Linked lists**

The linked list data abstraction, used below, contains the following functions.

```
################################
# Linked list data abstraction #
################################
empty = 'empty'
def is_link(s):
"""s is a linked list if it is empty or a (first, rest) pair."""
return s == empty or (len(s) == 2 and is_link(s[1]))
def link(first, rest):
"""Construct a linked list from its first element and the rest."""
assert is_link(rest), "rest must be a linked list."
return [first, rest]
def first(s):
"""Return the first element of a linked list s."""
assert is_link(s), "first only applies to linked lists."
assert s != empty, "empty linked list has no first element."
return s[0]
def rest(s):
"""Return the rest of the elements of a linked list s."""
assert is_link(s), "rest only applies to linked lists."
assert s != empty, "empty linked list has no rest."
return s[1]
def print_link(s):
"""Print elements of a linked list s.
>>> s = link(1, link(2, link(3, empty)))
>>> print_link(s)
1 2 3
"""
line = ''
while s != empty:
if line:
line += ' '
line += str(first(s))
s = rest(s)
print(line)
```

The mad scientist John Harvey Hilfinger has discovered a gene that compels people to enroll in CS 61A. You may be afflicted!

A DNA sequence is represented as a linked list of elements `A`

, `G`

, `C`

or
`T`

. This discovered gene has sequence `C A T C A T`

. Write a
function `has_61A_gene`

that takes a DNA sequence and returns whether it
contains the 61A gene as a sub-sequence.

First, write a function `has_prefix`

that takes two linked lists, `s`

and
`prefix`

, and returns whether `s`

starts with the elements of `prefix`

. Note
that `prefix`

may be larger than `s`

, in which case the function should return
`False`

.

```
def has_prefix(s, prefix):
"""Returns whether prefix appears at the beginning of linked list s.
>>> x = link(3, link(4, link(6, link(6, empty))))
>>> print_link(x)
3 4 6 6
>>> has_prefix(x, empty)
True
>>> has_prefix(x, link(3, empty))
True
>>> has_prefix(x, link(4, empty))
False
>>> has_prefix(x, link(3, link(4, empty)))
True
>>> has_prefix(x, link(3, link(3, empty)))
False
>>> has_prefix(x, x)
True
>>> has_prefix(link(2, empty), link(2, link(3, empty)))
False
"""
"*** YOUR CODE HERE ***"
```

Next, write a function `has_sublist`

that takes two linked lists, `s`

and
`sublist`

, and returns whether the elements of `sublist`

appear in order
anywhere within `s`

.

```
def has_sublist(s, sublist):
"""Returns whether sublist appears somewhere within linked list s.
>>> has_sublist(empty, empty)
True
>>> aca = link('A', link('C', link('A', empty)))
>>> x = link('G', link('A', link('T', link('T', aca))))
>>> print_link(x)
G A T T A C A
>>> has_sublist(x, empty)
True
>>> has_sublist(x, link(2, link(3, empty)))
False
>>> has_sublist(x, link('G', link('T', empty)))
False
>>> has_sublist(x, link('A', link('T', link('T', empty))))
True
>>> has_sublist(link(1, link(2, link(3, empty))), link(2, empty))
True
>>> has_sublist(x, link('A', x))
False
"""
"*** YOUR CODE HERE ***"
```

Finally, write `has_61A_gene`

to detect `C A T C A T`

within a linked list
`dna`

sequence.

```
def has_61A_gene(dna):
"""Returns whether linked list dna contains the CATCAT gene.
>>> dna = link('C', link('A', link('T', empty)))
>>> dna = link('C', link('A', link('T', link('G', dna))))
>>> print_link(dna)
C A T G C A T
>>> has_61A_gene(dna)
False
>>> end = link('T', link('C', link('A', link('T', link('G', empty)))))
>>> dna = link('G', link('T', link('A', link('C', link('A', end)))))
>>> print_link(dna)
G T A C A T C A T G
>>> has_61A_gene(dna)
True
>>> has_61A_gene(end)
False
"""
"*** YOUR CODE HERE ***"
```

Note: Subsequence matching is a problem of importance in computational biology. CS 176 goes into more detail on this topic, including methods that handle errors in the DNA (because DNA sequencing is not 100% correct).

In lecture, we saw how to use functions to create mutable objects.
Here, for example, is the function, `make_withdraw,`

which produces a
function that can withdraw money from an account:

```
def make_withdraw(balance):
"""Return a withdraw function with BALANCE as its starting balance.
>>> withdraw = make_withdraw(1000)
>>> withdraw(100)
900
>>> withdraw(100)
800
>>> withdraw(900)
'Insufficient funds'
"""
def withdraw(amount):
nonlocal balance
if amount > balance:
return 'Insufficient funds'
balance = balance - amount
return balance
return withdraw
```

Write a version of the `make_withdraw`

function 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 ***"
```

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 PROBLEMS ARE CHALLENGE PROBLEMS (OPTIONAL)**

Section 2.4.9 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.

Implement the function `triangle_area`

, which 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 ***"
```

The `multiplier`

constraint from the readings 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 ***"
```

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 ***"
```

Here is the equation solver implementation from the readings:

```
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)
```