Due by 11:59pm on Saturday, 07/26
Readings: You might find the following references useful:
Submission: See the online submission instructions. We have provided a hw9.py starter file for the questions below.
Implement the iterable interface for the Link class. Do not assume that we already have the __getitem__ method defined.
class Link:
"""A recursive list, with Python integration."""
empty = None
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is Link.empty:
rest = ''
else:
rest = ', ' + repr(self.rest)
return 'Link({}{})'.format(self.first, rest)
def __str__(self):
if self.rest is Link.empty:
rest = ''
else:
rest = ' ' + str(self.rest)[2:-2]
return '< {}{} >'.format(self.first, rest)
"""
Implement the iterable interface for the Link class.
You will need to return an instance of an iterator
object in the __iter__ method.
"""
def __iter__(self):
"""
>>> l = list_to_link([1, 2, 3, 4])
>>> i = iter(l)
>>> hasattr(i, '__next__')
True
>>> l2 = list_to_link([3, 1, 4, 1])
>>> for el in l2:
... print(el)
...
3
1
4
1
"""
"*** YOUR CODE HERE ***"
class LinkedListIterator:
"*** YOUR CODE HERE ***"
def list_to_link(lst):
"""
This is a convenience method which
converts a Python list into a linked list.
DO NOT USE THIS IN ANY OF YOUR SOLUTIONS.
"""
ll = Link.empty
for elem in lst[::-1]:
ll = Link(elem, ll)
return llRecall that an iterable object must have an __iter__ method which returns an iterator object. You will need to define a LinkedListIterator class to complete the implementation.
You should be able to do a for loop over the elements of a linked list once you have correctly implemented the interface.
Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].
Implement permutations, a function which takes in a lst and outputs a list of all permutations of lst (see doctest for examples).
def list_perms(lst):
"""
Returns a list of all permutations of lst.
>>> p = list_perms([1, 2, 3])
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> p1 = list_perms([0, 1])
>>> p1.sort()
>>> p1
[[0, 1], [1, 0]]
"""
if lst == []:
return None # REPLACE ME
prev_perms = list_perms(lst[1:])
result = []
for perm in prev_perms:
for i in range(len(lst)):
"*** YOUR CODE HERE ***"
return resultFeel free to replace the for loops with list comprehensions if you would rather use that.
One application of list permutations is in solving math puzzles like this one:
___ * ___ - ___ - ___ // ___ + ___ - ___ // ___ * ___ = 7The goal is to arrange the numbers from 1 to 9 in each of the blank spots such that the expression evaluates to 7. We have included a class MathPuzzle, which randomly generates a puzzle out of a given rng. In the example above, rng is 9. You can call print on the MathPuzzle object to get a representation like the one shown above.
The MathPuzzle class has a check_solution method, which takes in a list of numbers between 1 and the range of the puzzle and checks to see if they satisfy the expression. In this case, one solution would be
[1, 3, 2, 9, 5, 7, 4, 8, 6]Using your code for list_perms, write solve_list_perms, which takes in a MathPuzzle object and returns a solution to the puzzle. Note that a given MathPuzzle may have multiple possible solutions; your program only needs to return the first solution you encounter.
def solve_list_perms(puzzle):
"""
Solves a MathPuzzle using a list of permutations;
returns the first correct answer it encounters.
"""
"*** YOUR CODE HERE ***"We've provided a TestPuzzle class which creates a puzzle out of a pre-determined expression so you can test your code:
class TestPuzzle(MathPuzzle):
"""
Creates a MathPuzzle out of the given expression.
>>> test = TestPuzzle([1, '+', 2, '*', 3])
>>> print(test)
___ + ___ * ___ = 7
>>> test.check_solution([1, 2, 3])
True
>>> test.check_solution([1, 3, 2])
True
>>> test.check_solution([2, 3, 1])
False
"""
def __init__(self, expression):
self.expression = [str(el) for el in expression]
self.puzzle = [el for el in expression if el in MathPuzzle.ops]
self.value = eval(''.join(self.expression))
self.range = len(self.puzzle) + 1Be sure to make up puzzles yourself and load the file interactively. Your program may find a different solution from the one you inputted - this is fine as long as it still evaluates to the correct value.
You might have noticed that with larger puzzles, your code for solve_list_perms was quite slow. This is because list_perms computes and outputs all permutations at once, and we have to wait for that entire process to finish before we can start testing. This implementation was also space inefficient, because it had to store all permutations when only a handful would have been a valid solution to the puzzle.
To fix these issues, write generate_perms, a more efficient way to get permutations. generate_perms is a generator function which yields each permutation of lst one by one, so it never has to store the entire set of permutations in memory at one time.
def generate_perms(lst):
"""
Generates the permutations of lst one by one.
>>> perms = generate_perms([1, 2, 3])
>>> hasattr(perms, '__next__')
True
>>> p = list(perms)
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
"*** YOUR CODE HERE ***"See Lecture 16 for an example of converting a list-based solution to a generator solution (subsets).
To see the difference, write solve_gen_perms, which solves a MathPuzzle using generate_perms instead of list_perms.
def solve_gen_perms(puzzle):
"""
Solves a MathPuzzle by generating permutations;
returns the first correct answer it encounters.
"""
"*** YOUR CODE HERE ***"Try making a larger MathPuzzle (with a rng of 15 or so) and solve it using both methods. solve_gen_perms should be significantly faster.
Like functions, generators can also be higher-order. For this problem, we will be writing remainders_generator, which yields a series of generator objects.
def remainders_generator(m):
"""
Takes in an integer m, and yields m different remainder groups
of m.
>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
... for i in range(3):
... next(rem_group)
...
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"remainders_generator takes in an integer m, and yields m
different generators: a generator of multiples of m, a generator of
natural numbers which leave a remainder of 1 when divided by m, and
so on up to a remainder of m - 1.
Note that if you have implemented this correctly, each of the generators yielded by remainder_generator will be infinite - you can keep calling next on them forever without running into a StopIteration exception.
Hint: Consider defining an inner generator function. What arguments should it take in? Where should you call it?