CMPSC 442: Homeworks 1 to 6 solutions

Description

CMPSC 442: Homework 1

In this assignment, you will answer some conceptual questions about Python and write a collection of
basic algorithms and data structures.
A skeleton file homework1-cmpsc442.py containing empty definitions for each question has been
provided. Since portions of this assignment will be graded automatically, none of the names or
function signatures in this file should be modified. However, you are free to introduce additional
variables or functions if needed.
Unless explicitly stated otherwise, you may not import any of the standard Python modules, meaning
your solutions should not include any lines of the form import x or from x import y. Accordingly,
you may find it helpful to refresh yourself on Python’s built-in functions and data types.
You will find that in addition to a problem specification, each programming question also includes a
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
1 of 9 1/11/20, 9:34 AM
pair of examples from the Python interpreter. These are meant to illustrate typical use cases to clarify
the assignment, and are not comprehensive test suites. In addition to performing your own testing,
you are strongly encouraged to verify that your code gives the expected output for these examples
before submitting.
You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was
written in part by the creator of Python. However, your code will not be graded for style.
Once you have completed the assignment, you should submit your file in Canvas.
1. Python Concepts (6 points) [6 points]
For each of the following questions, write your answers as triply-quoted strings using the indicated
variables in the provided file.
1. [2 points] [2 points] Explain what it means for Python to be both strongly and dynamically
typed, and give a concrete example of each.
2. [2 points] [2 points] You would like to create a dictionary that maps some 2-dimensional points
to their associated names. As a first attempt, you write the following code:
points_to_names = {[0, 0]: “home”, [1, 2]: “school”, [-1, 1]: “market”}
However, this results in a type error. Describe what the problem is, and propose a solution.
3. [2 points] [2 points] Consider the following two functions, each of which concatenates a list of
strings.
def concatenate1(strings):
result = “”
for s in strings:
result += s
return result
def concatenate2(strings):
return “”.join(strings)
One of these approaches is significantly faster than the other for large inputs. Which version is
better, and what is the reason for the discrepancy?
2. Working with Lists (15 points) [15 points]
1. [5 points] [5 points] Consider the function extract_and_apply(l, p, f) shown below, which
extracts the elements of a list l satisfying a boolean predicate p, applies a function f to each
such element, and returns the result.
def extract_and_apply(l, p, f):
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
2 of 9 1/11/20, 9:34 AM
result = []
for x in l:
if p(x):
result.append(f(x))
return result
Rewrite extract_and_apply(l, p, f) in one line using a list comprehension.
2. [5 points] [5 points] Write a function concatenate(seqs) that returns a list containing the
concatenation of the elements of the input sequences. Your implementation should consist of a
single list comprehension, and should not exceed one line.
>>> concatenate([[1, 2], [3, 4]])
[1, 2, 3, 4]
>>> concatenate([“abc”, (0, [0])])
[‘a’, ‘b’, ‘c’, 0, [0]]
3. [5 points] [5 points] Write a function transpose(matrix) that returns the transpose of the input
matrix, which is represented as a list of lists. Recall that the transpose of a matrix is obtained by
swapping its rows with its columns. More concretely, the equality
matrix[i][j] == transpose(matrix)[j][i] should hold for all valid indices i and j. You may
assume that the input matrix is well-formed, i.e., that each row is of equal length. You may
further assume that the input matrix is non-empty. Your function should not modify the input.
>>> transpose([[1, 2, 3]])
[[1], [2], [3]]
>>> transpose([[1, 2], [3, 4], [5, 6]])
[[1, 3, 5], [2, 4, 6]]
3. Sequence Slicing (6 points) [6 points]
The functions in this section should be implemented using sequence slices. Recall that the slice
parameters take on sensible default values when omitted. In some cases, it may be necessary to use
the optional third parameter to specify a step size.
1. [2 points] [2 points] Write a function copy(seq) that returns a new sequence containing the
same elements as the input sequence.
>>> copy(“abc”)
‘abc’
>>> copy((1, 2, 3))
(1, 2, 3)
>>> x = [0, 0, 0]; y = copy(x)
>>> print(x, y); x[0] = 1; print(x, y)
[0, 0, 0] [0, 0, 0]
[1, 0, 0] [0, 0, 0]
2. [2 points] [2 points] Write a function all_but_last(seq) that returns a new sequence
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
3 of 9 1/11/20, 9:34 AM
containing all but the last element of the input sequence. If the input sequence is empty, a new
empty sequence of the same type should be returned.
>>> all_but_last(“abc”)
‘ab’
>>> all_but_last((1, 2, 3))
(1, 2)
>>> all_but_last(“”)
”
>>> all_but_last([])
[]
3. [2 points] [2 points] Write a function every_other(seq) that returns a new sequence containing
every other element of the input sequence, starting with the first. Hint: This function can be
written in one line using the optional third parameter of the slice notation.
>>> every_other([1, 2, 3, 4, 5])
[1, 3, 5]
>>> every_other(“abcde”)
‘ace’
>>> every_other([1, 2, 3, 4, 5, 6])
[1, 3, 5]
>>> every_other(“abcdef”)
‘ace’
4. Combinatorial Algorithms (11 points) [11 points]
The functions in this section should be implemented as generators. You may generate the output in
any order you find convenient, as long as the correct elements are produced. However, in some cases,
you may find that the order of the example output hints at a possible implementation.
Although generators in Python can be used in a variety of ways, you will not need to use any of their
more sophisticated features here. Simply keep in mind that where you might normally return a list of
elements, you should instead yield the individual elements.
Since the contents of a generator cannot be viewed without employing some form of iteration, we
wrap all function calls in this section’s examples with the list function for convenience.
1. [6 points] [6 points] The prefixes of a sequence include the empty sequence, the first element,
the first two elements, etc., up to and including the full sequence itself. Similarly, the suffixes of
a sequence include the empty sequence, the last element, the last two elements, etc., up to and
including the full sequence itself. Write a pair of functions prefixes(seq) and suffixes(seq)
that yield all prefixes and suffixes of the input sequence.
>>> list(prefixes([1, 2, 3]))
[[], [1], [1, 2], [1, 2, 3]]
>>> list(suffixes([1, 2, 3]))
[[1, 2, 3], [2, 3], [3], []]
>>> list(prefixes(“abc”))
[”, ‘a’, ‘ab’, ‘abc’]
>>> list(suffixes(“abc”))
[‘abc’, ‘bc’, ‘c’, ”]
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
4 of 9 1/11/20, 9:34 AM
2. [5 points] [5 points] Write a function slices(seq) that yields all non-empty slices of the input
sequence.
>>> list(slices([1, 2, 3]))
[[1], [1, 2], [1, 2, 3], [2], [2, 3],
[3]]
>>> list(slices(“abc”))
[‘a’, ‘ab’, ‘abc’, ‘b’, ‘bc’, ‘c’]
5. Text Processing (20 points) [20 points]
1. [5 points] [5 points] A common preprocessing step in many natural language processing tasks
is text normalization, wherein words are converted to lowercase, extraneous whitespace is
removed, etc. Write a function normalize(text) that returns a normalized version of the input
string, in which all words have been converted to lowercase and are separated by a single space.
No leading or trailing whitespace should be present in the output.
>>> normalize(“This is an example.”)
‘this is an example.’
>>> normalize(” EXTRA SPACE “)
‘extra space’
2. [5 points] [5 points] Write a function no_vowels(text) that removes all vowels from the input
string and returns the result. For the purposes of this problem, the letter ‘y’ is not considered to
be a vowel.
>>> no_vowels(“This Is An Example.”)
‘Ths s n xmpl.’
>>> no_vowels(“We love Python!”)
‘W lv Pythn!’
3. [5 points] [5 points] Write a function digits_to_words(text) that extracts all digits from the
input string, spells them out as lowercase English words, and returns a new string in which they
are each separated by a single space. If the input string contains no digits, then an empty string
should be returned.
>>> digits_to_words(“Zip Code: 19104”)
‘one nine one zero four’
>>> digits_to_words(“Pi is 3.1415…”)
‘three one four one five’
4. [5 points] [5 points] Although there exist many naming conventions in computer programming,
two of them are particularly widespread. In the first, words in a variable name are separated
using underscores. In the second, words in a variable name are written in mixed case, and are
strung together without a delimiter. By mixed case, we mean that the first word is written in
lowercase, and that subsequent words have a capital first letter. Write a function
to_mixed_case(name) that converts a variable name from the former convention to the latter.
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
5 of 9 1/11/20, 9:34 AM
Leading and trailing underscores should be ignored. If the variable name consists solely of
underscores, then an empty string should be returned.
>>> to_mixed_case(“to_mixed_case”)
‘toMixedCase’
>>> to_mixed_case(“__EXAMPLE__NAME__”)
‘exampleName’
6. Polynomials (37 points) [37 points]
In this section, you will implement a simple Polynomial class supporting basic arithmetic,
simplification, evaluation, and pretty-printing. An example demonstrating these capabilities is shown
below.
>>> p, q = Polynomial([(2, 1), (1, 0)]), Polynomial([(2, 1), (-1, 0)])
>>> print(p); print(q)
2x + 1
2x – 1
>>> r = (p * p) + (q * q) – (p * q); print(r)
4x^2 + 2x + 2x + 1 + 4x^2 – 2x – 2x + 1 – 4x^2 + 2x – 2x + 1
>>> r.simplify(); print(r)
4x^2 + 3
>>> [(x, r(x)) for x in range(-4, 5)]
[(-4, 67), (-3, 39), (-2, 19), (-1, 7), (0, 3), (1, 7), (2, 19), (3, 39), (4, 67)]
1. [2 points] [2 points] In this problem, we will think of a polynomial as an immutable object,
represented internally as a tuple of coefficient-power pairs. For instance, the polynomial 2x + 1
would be represented internally by the tuple ((2, 1), (1, 0)). Write an initialization method
__init__(self, polynomial) that converts the input sequence polynomial of coefficient-power
pairs into a tuple and saves it for future use. Also write a corresponding method
get_polynomial(self) that returns this internal representation.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> p.get_polynomial()
((2, 1), (1, 0))
>>> p = Polynomial(((2, 1), (1, 0)))
>>> p.get_polynomial()
((2, 1), (1, 0))
2. [4 points] [4 points] Write a __neg__(self) method that returns a new polynomial equal to the
negation of self. This method will be used by Python for unary negation.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = -p; q.get_polynomial()
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = -(-p); q.get_polynomial()
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
6 of 9 1/11/20, 9:34 AM
((-2, 1), (-1, 0)) ((2, 1), (1, 0))
3. [3 points] [3 points] Write an __add__(self, other) method that returns a new polynomial
equal to the sum of self and other. This method will be used by Python for addition. No
simplification should be performed on the result.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = p + p; q.get_polynomial()
((2, 1), (1, 0), (2, 1), (1, 0))
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = Polynomial([(4, 3), (3, 2)])
>>> r = p + q; r.get_polynomial()
((2, 1), (1, 0), (4, 3), (3, 2))
4. [3 points] [3 points] Write a __sub__(self, other) method that returns a new polynomial
equal to the difference between self and other. This method will be used by Python for
subtraction. No simplification should be performed on the result.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = p – p; q.get_polynomial()
((2, 1), (1, 0), (-2, 1), (-1, 0))
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = Polynomial([(4, 3), (3, 2)])
>>> r = p – q; r.get_polynomial()
((2, 1), (1, 0), (-4, 3), (-3, 2))
5. [5 points] [5 points] Write a __mul__(self, other) method that returns a new polynomial
equal to the product of self and other. This method will be used by Python for multiplication.
No simplification should be performed on the result. Your result does not need to match the
examples below exactly, as long as the same terms are present in some order.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = p * p; q.get_polynomial()
((4, 2), (2, 1), (2, 1), (1, 0))
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = Polynomial([(4, 3), (3, 2)])
>>> r = p * q; r.get_polynomial()
((8, 4), (6, 3), (4, 3), (3, 2))
6. [3 points] [3 points] Write a __call__(self, x) method that returns the result of evaluating the
current polynomial at the point x. This method will be used by Python when a polynomial is
called as a function. Hint: This method can be written in one line using Python’s exponentiation
operator, **, and the built-in sum function.
>>> p = Polynomial([(2, 1), (1, 0)])
>>> [p(x) for x in range(5)]
[1, 3, 5, 7, 9]
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = -(p * p) + p
>>> [q(x) for x in range(5)]
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
7 of 9 1/11/20, 9:34 AM
[0, -6, -20, -42, -72]
7. [8 points] [8 points] Write a simplify(self) method that replaces the polynomial’s internal
representation with an equivalent, simplified representation. Unlike the previous methods,
simplify(self) does not return a new polynomial, but rather acts in place. However, because
the fundamental character of the polynomial is not changing, we do not consider this to violate
the notion that polynomials are immutable.
The simplification process should begin by combining terms with a common power. Then,
terms with a coefficient of zero should be removed, and the remaining terms should be sorted in
decreasing order based on their power. In the event that all terms have a coefficient of zero after
the first step, the polynomial should be simplified to the single term 0 · x0, i.e. (0, 0).
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = -p + (p * p); q.get_polynomial()
((-2, 1), (-1, 0), (4, 2), (2, 1),
(2, 1), (1, 0))
>>> q.simplify(); q.get_polynomial()
((4, 2), (2, 1))
>>> p = Polynomial([(2, 1), (1, 0)])
>>> q = p – p; q.get_polynomial()
((2, 1), (1, 0), (-2, 1), (-1, 0))
>>> q.simplify(); q.get_polynomial()
((0, 0),)
8. [9 points] [9 points] Write a __str__(self) method that returns a human-readable string
representing the polynomial. This method will be used by Python when the str function is
called on a polynomial, or when a polynomial is printed.
In general, your function should render polynomials as a sequence of signs and terms each
separated by a single space, i.e. “sign1 term1 sign2 term2 … signN termN”, where signs can
be “+” or “-“, and terms have the form “ax^b” for coefficient a and power b. However, in
adherence with conventional mathematical notation, there are a few exceptional cases that
require special treatment:
The first sign should not be separated from the first term by a space, and should be left
blank if the first term has a positive coefficient.
The variable and power portions of a term should be omitted if the power is 0, leaving
only the coefficient.
The power portion of a term should be omitted if the power is 1.
Coefficients with magnitude 0 should always have a positive sign.
Coefficients with magnitude 1 should be omitted, unless the power is 0.
You may assume that all polynomials have integer coefficients and non-negative integer
powers.
Homework 1 file:///home/kaivan/cmpsc442/homeworks/homew…
8 of 9 1/11/20, 9:34 AM
>>> p = Polynomial([(1, 1), (1, 0)])
>>> qs = (p, p + p, -p, -p – p, p * p)
>>> for q in qs: q.simplify(); str(q)
…
‘x + 1’
‘2x + 2’
‘-x – 1’
‘-2x – 2’
‘x^2 + 2x + 1’
>>> p = Polynomial([(0, 1), (2, 3)])
>>> str(p); str(p * p); str(-p * p)
‘0x + 2x^3’
‘0x^2 + 0x^4 + 0x^4 + 4x^6’
‘0x^2 + 0x^4 + 0x^4 – 4x^6’
>>> q = Polynomial([(1, 1), (2, 3)])
>>> str(q); str(q * q); str(-q * q)
‘x + 2x^3’
‘x^2 + 2x^4 + 2x^4 + 4x^6’
‘-x^2 – 2x^4 – 2x^4 – 4x^6’
7. Feedback (5 points) [5 points]
1. [1 point] [1 point] Approximately how long did you spend on this assignment?
2. [2 points] [2 points] Which aspects of this assignment did you find most challenging? Were
there any significant stumbling blocks?
3. [2 points] [2 points] Which aspects of this assignment did you like? Is there anything you
would have changed?

CMPSC 442: Homework 2

In this assignment, you will explore three classic puzzles from the perspective of uninformed
search.
A skeleton file homework2-cmpsc442.py containing empty definitions for each question has been
provided. Since portions of this assignment will be graded automatically, none of the names or
function signatures in this file should be modified. However, you are free to introduce additional
variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in cases
where you find yourself reinventing the wheel. If you are unsure where to start, consider taking a
look at the data structures and functions defined in the collections, itertools, math, and
random modules.
You will find that in addition to a problem specification, most programming questions also include
a pair of examples from the Python interpreter. These are meant to illustrate typical use cases to
clarify the assignment, and are not comprehensive test suites. In addition to performing your own
testing, you are strongly encouraged to verify that your code gives the expected output for these
examples before submitting.
You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was
written in part by the creator of Python. However, your code will not be graded for style.
1. N-Queens [25 points]
In this section, you will develop a solver for the n-queens problem, wherein n queens are to be
placed on an n x n chessboard so that no pair of queens can attack each other. Recall that in chess, a
queen can attack any piece that lies in the same row, column, or diagonal as itself.
A brief treatment of this problem for the case where n = 8 is given in Section 3.2 of the textbook,
which you may wish to consult for additional information.
1. [5 points] Rather than performing a search over all possible placements of queens on the
board, it is sufficient to consider only those configurations for which each row contains
exactly one queen. Without taking any of the chess-specific constraints between queens into
account, implement the pair of functions num_placements_all(n) and
num_placements_one_per_row(n) that return the number of possible placements of n queens
on an n x n board without or with this additional restriction. Think carefully about why this
restriction is valid, and note the extent to which it reduces the size of the search space. You
should assume that all queens are indistinguishable for the purposes of your calculations.
2. [5 points] With the answer to the previous question in mind, a sensible representation for a
board configuration is a list of numbers between 0 and n – 1, where the ith number designates
the column of the queen in row i for 0 ≤ i < n. A complete configuration is then specified by a list containing n numbers, and a partial configuration is specified by a list containing fewer than n numbers. Write a function n_queens_valid(board) that accepts such a list and returns True if no queen can attack another, or False otherwise. Note that the board size need not be included as an additional argument to decide whether a particular list is valid. >>> n_queens_valid([0, 0])
False
>>> n_queens_valid([0, 1])
False
Homework 2 1/29/20, 8:12 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework2-cmpsc442.html Page 3 of 7
>>> n_queens_valid([0, 2])
True
>>> n_queens_valid([0, 3, 1])
True
3. [15 points] Write a function n_queens_solutions(n) that yields all valid placements of n
queens on an n x n board, using the representation discussed above. The output may be
generated in any order you see fit. Your solution should be implemented as a depth-first
search, where queens are successively placed in empty rows until all rows have been filled.
Hint: You may find it helpful to define a helper function n_queens_helper(n, board) that
yields all valid placements which extend the partial solution denoted by board.
Though our discussion of search in class has primarily covered algorithms that return just a
single solution, the extension to a generator which yields all solutions is relatively simple.
Rather than using a return statement when a solution is encountered, yield that solution
instead, and then continue the search.
>>> solutions = n_queens_solutions(4)
>>> next(solutions)
[1, 3, 0, 2]
>>> next(solutions)
[2, 0, 3, 1]
2. Lights Out [40 points]
The Lights Out puzzle consists of an m x n grid of lights, each of which has two states: on and off.
The goal of the puzzle is to turn all the lights off, with the caveat that whenever a light is toggled, its
neighbors above, below, to the left, and to the right will be toggled as well. If a light along the edge
of the board is toggled, then fewer than four other lights will be affected, as the missing neighbors
will be ignored.
In this section, you will investigate the behavior of Lights Out puzzles of various sizes by
implementing a LightsOutPuzzle class. Once you have completed the problems in this section, you
can test your code in an interactive setting using the provided GUI. See the end of the section for
more details.
1. [2 points] A natural representation for this puzzle is a two-dimensional list of Boolean
values, where True corresponds to the on state and False corresponds to the off state. In the
LightsOutPuzzle class, write an initialization method __init__(self, board) that stores
an input board of this form for future use. Also write a method get_board(self) that returns
this internal representation. You additionally may wish to store the dimensions of the board
as separate internal variables, though this is not required.
>>> list(n_queens_solutions(6))
[[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3],
[3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]]
>>> len(list(n_queens_solutions(8)))
92
Homework 2 1/29/20, 8:12 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework2-cmpsc442.html Page 4 of 7
>>> b = [[True, False], [False, True]]
>>> p = LightsOutPuzzle(b)
>>> p.get_board()
[[True, False], [False, True]]
>>> b = [[True, True], [True, True]]
>>> p = LightsOutPuzzle(b)
>>> p.get_board()
[[True, True], [True, True]]
2. [3 points] Write a top-level function create_puzzle(rows, cols) that returns a new
LightsOutPuzzle of the specified dimensions with all lights initialized to the off state.
>>> p = create_puzzle(2, 2)
>>> p.get_board()
[[False, False], [False, False]]
>>> p = create_puzzle(2, 3)
>>> p.get_board()
[[False, False, False],
[False, False, False]]
3. [5 points] In the LightsOutPuzzle class, write a method perform_move(self, row, col)
that toggles the light located at the given row and column, as well as the appropriate
neighbors.
>>> p = create_puzzle(3, 3)
>>> p.perform_move(1, 1)
>>> p.get_board()
[[False, True, False],
[True, True, True ],
[False, True, False]]
>>> p = create_puzzle(3, 3)
>>> p.perform_move(0, 0)
>>> p.get_board()
[[True, True, False],
[True, False, False],
[False, False, False]]
4. [5 points] In the LightsOutPuzzle class, write a method scramble(self) which scrambles
the puzzle by calling perform_move(self, row, col) with probability 1/2 on each location
on the board. This guarantees that the resulting configuration will be solvable, which may not
be true if lights are flipped individually. Hint: After importing the random module with the
statement import random, the expression random.random() < 0.5 generates the values True and False with equal probability. 5. [2 points] In the LightsOutPuzzle class, write a method is_solved(self) that returns whether all lights on the board are off. >>> b = [[True, False], [False, True]]
>>> p = LightsOutPuzzle(b)
>>> p.is_solved()
False
>>> b = [[False, False], [False, False]]
>>> p = LightsOutPuzzle(b)
>>> p.is_solved()
True
Homework 2 1/29/20, 8:12 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework2-cmpsc442.html Page 5 of 7
6. [3 points] In the LightsOutPuzzle class, write a method copy(self) that returns a new
LightsOutPuzzle object initialized with a deep copy of the current board. Changes made to
the original puzzle should not be reflected in the copy, and vice versa.
>>> p = create_puzzle(3, 3)
>>> p2 = p.copy()
>>> p.get_board() == p2.get_board()
True
>>> p = create_puzzle(3, 3)
>>> p2 = p.copy()
>>> p.perform_move(1, 1)
>>> p.get_board() == p2.get_board()
False
7. [5 points] In the LightsOutPuzzle class, write a method successors(self) that yields all
successors of the puzzle as (move, new-puzzle) tuples, where moves themselves are (row,
column) tuples. The second element of each successor should be a new LightsOutPuzzle
object whose board is the result of applying the corresponding move to the current board. The
successors may be generated in whichever order is most convenient.
>>> p = create_puzzle(2, 2)
>>> for move, new_p in p.successors():
… print(move, new_p.get_board())
…
(0, 0) [[True, True], [True, False]]
(0, 1) [[True, True], [False, True]]
(1, 0) [[True, False], [True, True]]
(1, 1) [[False, True], [True, True]]
8. [15 points] In the LightsOutPuzzle class, write a method find_solution(self) that
returns an optimal solution to the current board as a list of moves, represented as (row,
column) tuples. If more than one optimal solution exists, any of them may be returned. Your
solver should be implemented using a breadth-first graph search, which means that puzzle
states should not be added to the frontier if they have already been visited, or are currently in
the frontier. If the current board is not solvable, the value None should be returned instead.
You are highly encouraged to reuse the methods defined in the previous exercises while
developing your solution.
Hint: For efficient testing of duplicate states, consider using tuples representing the boards
of the LightsOutPuzzle objects being explored rather than their internal list-based
representations. You will then be able to use the built-in set data type to check for the
presence or absence of a particular state in near-constant time.
>>> for i in range(2, 6):
… p = create_puzzle(i, i + 1)
… print(len(list(p.successors())))
…
6
12
20
30
Homework 2 1/29/20, 8:12 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework2-cmpsc442.html Page 6 of 7
>>> p = create_puzzle(2, 3)
>>> for row in range(2):
… for col in range(3):
… p.perform_move(row, col)
…
>>> p.find_solution()
[(0, 0), (0, 2)]
>>> b = [[False, False, False],
… [False, False, False]]
>>> b[0][0] = True
>>> p = LightsOutPuzzle(b)
>>> p.find_solution() is None
True
Once you have implemented the functions and methods described in this section, you can play with
an interactive version of the Lights Out puzzle using the provided GUI by running the following
command:
python homework2_lights_out_gui.py rows cols
The arguments rows and cols are positive integers designating the size of the puzzle.
In the GUI, you can click on a light to perform a move at that location, and use the side menu to
scramble or solve the puzzle. The GUI is merely a wrapper around your implementations of the
relevant functions, and may therefore serve as a useful visual tool for debugging.
3. Linear Disk Movement [30 points]
In this section, you will investigate the movement of disks on a linear grid.
The starting configuration of this puzzle is a row of L cells, with disks located on cells 0 through n –
1. The goal is to move the disks to the end of the row using a constrained set of actions. At each step,
a disk can only be moved to an adjacent empty cell, or to an empty cell two spaces away, provided
another disk is located on the intervening cell. Given these restrictions, it can be seen that in many
cases, no movements will be possible for the majority of the disks. For example, from the starting
position, the only two options are to move the last disk from cell n – 1 to cell n, or to move the
second-to-last disk from cell n – 2 to cell n.
1. [15 points] Write a function solve_identical_disks(length, n) that returns an optimal
solution to the above problem as a list of moves, where length is the number of cells in the
row and n is the number of disks. Each move in the solution should be a two-element tuple of
the form (from, to) indicating a disk movement from the first cell to the second. As suggested
by its name, this function should treat all disks as being identical.
Your solver for this problem should be implemented using a breadth-first graph search. The
exact solution produced is not important, as long as it is of minimal length.
Unlike in the previous two sections, no requirement is made with regards to the manner in
which puzzle configurations are represented. Before you begin, think carefully about which
Homework 2 1/29/20, 8:12 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework2-cmpsc442.html Page 7 of 7
data structures might be best suited for the problem, as this choice may affect the efficiency of
your search.
>>> solve_identical_disks(4, 2)
[(0, 2), (1, 3)]
>>> solve_identical_disks(5, 2)
[(0, 2), (1, 3), (2, 4)]
>>> solve_identical_disks(4, 3)
[(1, 3), (0, 1)]
>>> solve_identical_disks(5, 3)
[(1, 3), (0, 1), (2, 4), (1, 2)]
2. [15 points] Write a function solve_distinct_disks(length, n) that returns an optimal
solution to the same problem with a small modification: in addition to moving the disks to the
end of the row, their final order must be the reverse of their initial order. More concretely, if
we abbreviate length as L, then a desired solution moves the first disk from cell 0 to cell L – 1,
the second disk from cell 1 to cell L – 2, . . . , and the last disk from cell n – 1 to cell L – n.
Your solver for this problem should again be implemented using a breadth-first graph search.
As before, the exact solution produced is not important, as long as it is of minimal length.
>>> solve_distinct_disks(4, 2)
[(0, 2), (2, 3), (1, 2)]
>>> solve_distinct_disks(5, 2)
[(0, 2), (1, 3), (2, 4)]
4. Feedback [5 points]
1. [1 point] Approximately how long did you spend on this assignment?
2. [2 points] Which aspects of this assignment did you find most challenging? Were there any
significant stumbling blocks?
3. [2 points] Which aspects of this assignment did you like? Is there anything you would have
changed?
>>> solve_distinct_disks(4, 3)
[(1, 3), (0, 1), (2, 0), (3, 2), (1, 3),
(0, 1)]
>>> solve_distinct_disks(5, 3)
[(1, 3), (2, 1), (0, 2), (2, 4), (1, 2)]

CMPSC 442: Homework 3

In this assignment, you will explore a number of games and puzzles from the perspectives of
informed and adversarial search.
A skeleton file homework3-cmpsc442.py containing empty definitions for each question has been
provided. Since portions of this assignment will be graded automatically, none of the names or
function signatures in this file should be modified. However, you are free to introduce additional
variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in case
you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at
the data structures and functions defined in the collections, itertools, Queue, and random
modules.
You will find that in addition to a problem specification, most programming questions also include
a pair of examples from the Python interpreter. These are meant to illustrate typical use cases to
clarify the assignment, and are not comprehensive test suites. In addition to performing your own
testing, you are strongly encouraged to verify that your code gives the expected output for these
examples before submitting.
You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was
written in part by the creator of Python. However, your code will not be graded for style.
1. Tile Puzzle [40 points]
Recall from class that the Eight Puzzle consists of a 3 x 3 board of sliding tiles with a single empty
space. For each configuration, the only possible moves are to swap the empty tile with one of its
neighboring tiles. The goal state for the puzzle consists of tiles 1-3 in the top row, tiles 4-6 in the
middle row, and tiles 7 and 8 in the bottom row, with the empty space in the lower-right corner.
In this section, you will develop two solvers for a generalized version of the Eight Puzzle, in which
the board can have any number of rows and columns. We have suggested an approach similar to the
one used to create a Lights Out solver in Homework 2, and indeed, you may find that this pattern
can be abstracted to cover a wide range of puzzles. If you wish to use the provided GUI for testing,
described in more detail at the end of the section, then your implementation must adhere to the
recommended interface. However, this is not required, and no penalty will imposed for using a
different approach.
A natural representation for this puzzle is a two-dimensional list of integer values between 0 and r ·
c – 1 (inclusive), where r and c are the number of rows and columns in the board, respectively. In
this problem, we will adhere to the convention that the 0-tile represents the empty space.
1. [0 points] In the TilePuzzle class, write an initialization method __init__(self, board)
that stores an input board of this form described above for future use. You additionally may
wish to store the dimensions of the board as separate internal variables, as well as the location
of the empty tile.
2. [0 points] Suggested infrastructure.
In the TilePuzzle class, write a method get_board(self) that returns the internal
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 3 of 11
representation of the board stored during initialization.
>>> p = TilePuzzle([[1, 2], [3, 0]])
>>> p.get_board()
[[1, 2], [3, 0]]
>>> p = TilePuzzle([[0, 1], [3, 2]])
>>> p.get_board()
[[0, 1], [3, 2]]
Write a top-level function create_tile_puzzle(rows, cols) that returns a new TilePuzzle
of the specified dimensions, initialized to the starting configuration. Tiles 1 through r · c – 1
should be arranged starting from the top-left corner in row-major order, and tile 0 should be
located in the lower-right corner.
>>> p = create_tile_puzzle(3, 3)
>>> p.get_board()
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
>>> p = create_tile_puzzle(2, 4)
>>> p.get_board()
[[1, 2, 3, 4], [5, 6, 7, 0]]
In the TilePuzzle class, write a method perform_move(self, direction) that attempts to
swap the empty tile with its neighbor in the indicated direction, where valid inputs are limited
to the strings “up”, “down”, “left”, and “right”. If the given direction is invalid, or if the
move cannot be performed, then no changes to the puzzle should be made. The method
should return a Boolean value indicating whether the move was successful.
>>> p = create_tile_puzzle(3, 3)
>>> p.perform_move(“up”)
True
>>> p.get_board()
[[1, 2, 3], [4, 5, 0], [7, 8, 6]]
>>> p = create_tile_puzzle(3, 3)
>>> p.perform_move(“down”)
False
>>> p.get_board()
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
In the TilePuzzle class, write a method scramble(self, num_moves) which scrambles the
puzzle by calling perform_move(self, direction) the indicated number of times, each time
with a random direction. This method of scrambling guarantees that the resulting
configuration will be solvable, which may not be true if the tiles are randomly permuted.
Hint: The random module contains a function random.choice(seq) which returns a random
element from its input sequence.
In the TilePuzzle class, write a method is_solved(self) that returns whether the board is
in its starting configuration.
>>> p = TilePuzzle([[1, 2], [3, 0]]) >>> p = TilePuzzle([[0, 1], [3, 2]])
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 4 of 11
>>> p.is_solved()
True
>>> p.is_solved()
False
In the TilePuzzle class, write a method copy(self) that returns a new TilePuzzle object
initialized with a deep copy of the current board. Changes made to the original puzzle should
not be reflected in the copy, and vice versa.
>>> p = create_tile_puzzle(3, 3)
>>> p2 = p.copy()
>>> p.get_board() == p2.get_board()
True
>>> p = create_tile_puzzle(3, 3)
>>> p2 = p.copy()
>>> p.perform_move(“left”)
>>> p.get_board() == p2.get_board()
False
In the TilePuzzle class, write a method successors(self) that yields all successors of the
puzzle as (direction, new-puzzle) tuples. The second element of each successor should be a
new TilePuzzle object whose board is the result of applying the corresponding move to the
current board. The successors may be generated in whichever order is most convenient, as
long as successors corresponding to unsuccessful moves are not included in the output.
>>> p = create_tile_puzzle(3, 3)
>>> for move, new_p in p.successors():
… print move, new_p.get_board()
…
up [[1, 2, 3], [4, 5, 0], [7, 8, 6]]
left [[1, 2, 3], [4, 5, 6], [7, 0, 8]]
>>> b = [[1,2,3], [4,0,5], [6,7,8]]
>>> p = TilePuzzle(b)
>>> for move, new_p in p.successors():
… print move, new_p.get_board()
…
up [[1, 0, 3], [4, 2, 5], [6, 7, 8]]
down [[1, 2, 3], [4, 7, 5], [6, 0, 8]]
left [[1, 2, 3], [0, 4, 5], [6, 7, 8]]
right [[1, 2, 3], [4, 5, 0], [6, 7, 8]]
3. [20 points] In the TilePuzzle class, write a method find_solutions_iddfs(self) that
yields all optimal solutions to the current board, represented as lists of moves. Valid moves
include the four strings “up”, “down”, “left”, and “right”, where each move indicates a
single swap of the empty tile with its neighbor in the indicated direction. Your solver should
be implemented using an iterative deepening depth-first search, consisting of a series of
depth-first searches limited at first to 0 moves, then 1 move, then 2 moves, and so on. You
may assume that the board is solvable. The order in which the solutions are produced is
unimportant, as long as all optimal solutions are present in the output.
Hint: This method is most easily implemented using recursion. First define a recursive
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 5 of 11
helper method iddfs_helper(self, limit, moves) that yields all solutions to the current
board of length no more than limit which are continuations of the provided move list. Your
main method will then call this helper function in a loop, increasing the depth limit by one at
each iteration, until one or more solutions have been found.
4. [20 points] In the TilePuzzle class, write a method find_solution_a_star(self) that
returns an optimal solution to the current board, represented as a list of direction strings. If
multiple optimal solutions exist, any of them may be returned. Your solver should be
implemented as an A* search using the Manhattan distance heuristic, which is reviewed
below. You may assume that the board is solvable. During your search, you should take care
not to add positions to the queue that have already been visited. It is recommended that you
use the PriorityQueue class from the Queue module.
Recall that the Manhattan distance between two locations (r_1, c_1) and (r_2, c_2) on a
board is defined to be the sum of the componentwise distances: |r_1 – r_2| + |c_1 – c_2|. The
Manhattan distance heuristic for an entire puzzle is then the sum of the Manhattan distances
between each tile and its solved location.
If you implemented the suggested infrastructure described in this section, you can play with an
interactive version of the Tile Puzzle using the provided GUI by running the following command:
python homework3_tile_puzzle_gui.py rows cols
The arguments rows and cols are positive integers designating the size of the puzzle.
In the GUI, you can use the arrow keys to perform moves on the puzzle, and can use the side menu
to scramble or solve the puzzle. The GUI is merely a wrapper around your implementations of the
>>> b = [[4,1,2], [0,5,3], [7,8,6]]
>>> p = TilePuzzle(b)
>>> solutions = p.find_solutions_iddfs()
>>> next(solutions)
[‘up’, ‘right’, ‘right’, ‘down’, ‘down’]
>>> b = [[1,2,3], [4,0,8], [7,6,5]]
>>> p = TilePuzzle(b)
>>> list(p.find_solutions_iddfs())
[[‘down’, ‘right’, ‘up’, ‘left’, ‘down’,
‘right’], [‘right’, ‘down’, ‘left’,
‘up’, ‘right’, ‘down’]]
>>> b = [[4,1,2], [0,5,3], [7,8,6]]
>>> p = TilePuzzle(b)
>>> p.find_solution_a_star()
[‘up’, ‘right’, ‘right’, ‘down’, ‘down’]
>>> b = [[1,2,3], [4,0,5], [6,7,8]]
>>> p = TilePuzzle(b)
>>> p.find_solution_a_star()
[‘right’, ‘down’, ‘left’, ‘left’, ‘up’,
‘right’, ‘down’, ‘right’, ‘up’, ‘left’,
‘left’, ‘down’, ‘right’, ‘right’]
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 6 of 11
relevant functions, and may therefore serve as a useful visual tool for debugging.
2. Grid Navigation [15 points]
In this section, you will investigate the problem of navigation on a two-dimensional grid with
obstacles. The goal is to produce the shortest path between a provided pair of points, taking care to
maneuver around the obstacles as needed. Path length is measured in Euclidean distance. Valid
directions of movement include up, down, left, right, up-left, up-right, down-left, and down-right.
Your task is to write a function find_path(start, goal, scene) which returns the shortest path
from the start point to the goal point that avoids traveling through the obstacles in the grid. For this
problem, points will be represented as two-element tuples of the form (row, column), and scenes
will be represented as two-dimensional lists of Boolean values, with False values corresponding
empty spaces and True values corresponding to obstacles. Your output should be the list of points
in the path, and should explicitly include both the start point and the goal point. Your
implementation should consist of an A* search using the straight-line Euclidean distance heuristic.
If multiple optimal solutions exist, any of them may be returned. If no optimal solutions exist, or if
the start point or goal point lies on an obstacle, you should return the sentinal value None.
>>> scene = [[False, False, False],
… [False, True , False],
… [False, False, False]]
>>> find_path((0, 0), (2, 1), scene)
[(0, 0), (1, 0), (2, 1)]
>>> scene = [[False, True, False],
… [False, True, False],
… [False, True, False]]
>>> print find_path((0, 0), (0, 2), scene)
None
Once you have implemented your solution, you can visualize the paths it produces using the
provided GUI by running the following command:
python homework3_grid_navigation_gui.py scene_path
The argument scene_path is a path to a scene file storing the layout of the target grid and
obstacles. We use the following format for textual scene representation: “.” characters correspond
to empty spaces, and “X” characters correspond to obstacles.
3. Linear Disk Movement, Revisited [15 points]
Recall the Linear Disk Movement section from Homework 2. The starting configuration of this
puzzle is a row of L cells, with disks located on cells 0 through n – 1. The goal is to move the disks to
the end of the row using a constrained set of actions. At each step, a disk can only be moved to an
adjacent empty cell, or to an empty cell two spaces away, provided another disk is located on the
intervening square.
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 7 of 11
In a variant of the problem, the disks were distinct rather than identical, and the goal state was
amended to stipulate that the final order of the disks should be the reverse of their initial order.
Implement an improved version of the solve_distinct_disks(length, n) function from
Homework 2 that uses an A* search rather than an uninformed breadth-first search to find an
optimal solution. As before, the exact solution produced is not important so long as it is of minimal
length. You should devise a heuristic which is admissible but informative enough to yield significant
improvements in performance.
4. Dominoes Game [25 points]
In this section, you will develop an AI for a game in which two players take turns placing 1 x 2
dominoes on a rectangular grid. One player must always place his dominoes vertically, and the
other must always place his dominoes horizontally. The last player who successfully places a
domino on the board wins.
As with the Tile Puzzle, an infrastructure that is compatible with the provided GUI has been
suggested. However, only the search method will be tested, so you are free to choose a different
approach if you find it more convenient to do so.
The representation used for this puzzle is a two-dimensional list of Boolean values, where True
corresponds to a filled square and False corresponds to an empty square.
1. [0 points] In the DominoesGame class, write an initialization method
__init__(self, board) that stores an input board of the form described above for future
use. You additionally may wish to store the dimensions of the board as separate internal
variables, though this is not required.
2. [0 points] Suggested infrastructure.
In the DominoesGame class, write a method get_board(self) that returns the internal
representation of the board stored during initialization.
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[True, False], [True, False]]
Write a top-level function create_dominoes_game(rows, cols) that returns a new
DominoesGame of the specified dimensions with all squares initialized to the empty state.
>>> g = create_dominoes_game(2, 2) >>> g = create_dominoes_game(2, 3)
>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[False, False], [False, False]]
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 8 of 11
>>> g.get_board()
[[False, False], [False, False]]
>>> g.get_board()
[[False, False, False],
[False, False, False]]
In the DominoesGame class, write a method reset(self) which resets all of the internal
board’s squares to the empty state.
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[True, False], [True, False]]
>>> g.reset()
>>> g.get_board()
[[False, False], [False, False]]
In the DominoesGame class, write a method is_legal_move(self, row, col, vertical)
that returns a Boolean value indicating whether the given move can be played on the current
board. A legal move must place a domino fully within bounds, and may not cover squares
which have already been filled.
If the vertical parameter is True, then the current player intends to place a domino on
squares (row, col) and (row + 1, col). If the vertical parameter is False, then the
current player intends to place a domino on squares (row, col) and (row, col + 1). This
convention will be followed throughout the rest of the section.
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.is_legal_move(0, 0, False)
False
>>> g.is_legal_move(0, 1, True)
True
>>> g.is_legal_move(1, 1, True)
False
In the DominoesGame class, write a method legal_moves(self, vertical) which yields the
legal moves available to the current player as (row, column) tuples. The moves should be
generated in row-major order (i.e. iterating through the rows from top to bottom, and within
rows from left to right), starting from the top-left corner of the board.
>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[False, False], [False, False]]
>>> g.reset()
>>> g.get_board()
[[False, False], [False, False]]
>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.is_legal_move(0, 0, True)
True
>>> g.is_legal_move(0, 0, False)
True
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 9 of 11
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> list(g.legal_moves(True))
[(0, 1)]
>>> list(g.legal_moves(False))
[]
In the DominoesGame class, write a method perform_move(self, row, col, vertical)
which fills the squares covered by a domino placed at the given location in the specified
orientation.
>>> g = create_dominoes_game(3, 3)
>>> g.perform_move(0, 1, True)
>>> g.get_board()
[[False, True, False],
[False, True, False],
[False, False, False]]
>>> g = create_dominoes_game(3, 3)
>>> g.perform_move(1, 0, False)
>>> g.get_board()
[[False, False, False],
[True, True, False],
[False, False, False]]
In the DominoesGame class, write a method game_over(self, vertical) that returns
whether the current player is unable to place any dominoes.
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.game_over(True)
False
>>> g.game_over(False)
True
In the DominoesGame class, write a method copy(self) that returns a new DominoesGame
object initialized with a deep copy of the current board. Changes made to the original puzzle
should not be reflected in the copy, and vice versa.
>>> g = create_dominoes_game(4, 4)
>>> g2 = g.copy()
>>> g.get_board() == g2.get_board()
True
>>> g = create_dominoes_game(4, 4)
>>> g2 = g.copy()
>>> g.perform_move(0, 0, True)
>>> g.get_board() == g2.get_board()
False
>>> g = create_dominoes_game(3, 3)
>>> list(g.legal_moves(True))
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1),
(1, 2)]
>>> list(g.legal_moves(False))
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0),
(2, 1)]
>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.game_over(True)
False
>>> g.game_over(False)
False
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 10 of 11
In the DominoesGame class, write a method successors(self, vertical) that yields all
successors of the puzzle for the current player as (move, new-game) tuples, where moves
themselves are (row, column) tuples. The second element of each successor should be a new
DominoesGame object whose board is the result of applying the corresponding move to the
current board. The successors should be generated in the same order in which moves are
produced by the legal_moves(self, vertical) method.
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> for m, new_g in g.successors(True):
… print m, new_g.get_board()
…
(0, 1) [[True, True], [True, True]]
Optional.
In the DominoesGame class, write a method get_random_move(self, vertical) which
returns a random legal move for the current player as a (row, column) tuple. Hint: The
random module contains a function random.choice(seq) which returns a random element
from its input sequence.
3. [25 points] In the DominoesGame class, write a method
get_best_move(self, vertical, limit) which returns a 3-element tuple containing the
best move for the current player as a (row, column) tuple, its associated value, and the
number of leaf nodes visited during the search. Recall that if the vertical parameter is True,
then the current player intends to place a domino on squares (row, col) and
(row + 1, col), and if the vertical parameter is False, then the current player intends to
place a domino on squares (row, col) and (row, col + 1). Moves should be explored rowmajor order, described in further detail above, to ensure consistency.
Your search should be a faithful implementation of the alpha-beta search given on page 170 of
the course textbook, with the restriction that you should look no further than limit moves
into the future. To evaluate a board, you should compute the number of moves available to the
current player, then subtract the number of moves available to the opponent.
>>> b = [[False] * 3 for i in range(3)]
>>> g = DominoesGame(b)
>>> g.get_best_move(True, 1)
((0, 1), 2, 6)
>>> b = [[False] * 3 for i in range(3)]
>>> g = DominoesGame(b)
>>> g.perform_move(0, 1, True)
>>> g.get_best_move(False, 1)
>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> for m, new_g in g.successors(True):
… print m, new_g.get_board()
…
(0, 0) [[True, False], [True, False]]
(0, 1) [[False, True], [False, True]]
Homework 3 2/6/20, 11:04 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework3-cmpsc442.html Page 11 of 11
>>> g.get_best_move(True, 2)
((0, 1), 3, 10)
((2, 0), -3, 2)
>>> g.get_best_move(False, 2)
((2, 0), -2, 5)
If you implemented the suggested infrastructure described in this section, you can play with an
interactive version of the dominoes board game using the provided GUI by running the following
command:
python homework3_dominoes_game_gui.py rows cols
The arguments rows and cols are positive integers designating the size of the board.
In the GUI, you can click on a square to make a move, press ‘r’ to perform a random move, or press
a number between 1 and 9 to perform the best move found according to an alpha-beta search with
that limit. The GUI is merely a wrapper around your implementations of the relevant functions, and
may therefore serve as a useful visual tool for debugging.
5. Feedback [5 points]
1. [1 point] Approximately how long did you spend on this assignment?
2. [2 points] Which aspects of this assignment did you find most challenging? Were there any
significant stumbling blocks?
3. [2 points] Which aspects of this assignment did you like? Is there anything you would have
changed?

CMPSC442: Homework 4

In this assignment, you will implement a basic spam filter using naive Bayes classification.
A skeleton file homework4-cmpsc442.py containing empty definitions for each question has been
provided. A zip file called homework4_data.zip has also been provided that contains the input train
and test data (both are on Canvas in the folder called Files/Homework Templates and Pdfs).
Since portions of this assignment will be graded automatically, none of the names or function
signatures in the skeleton template file should be modified. However, you are free to introduce
additional variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in case
you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at the
data structures and functions defined in the collections, email, math, and os modules.
You will find that in addition to a problem specification, most programming questions also include
one or two examples from the Python interpreter. These are meant to illustrate typical use cases to
clarify the assignment, and are not comprehensive test suites. In addition to performing your own
testing, you are strongly encouraged to verify that your code gives the expected output for these
examples before submitting.
It is highly recommended that you follow the Python style guidelines set forth in PEP 8, which was
written in part by the creator of Python. However, your code will not be graded for style.
1. Spam Filter [95 points]
In this section, you will implement a minimal system for spam filtering. You should unzip the
homework4_data.zip file in the same location as your skeleton file; this will create a
homework4_data/train folder and a homework4_data/dev folder. You will begin by processing the
raw training data. Next, you will proceed by estimating the conditional probability distributions of
the words in the vocabulary determined by each document class. Lastly, you will use a naive Bayes
model to make predictions on the publicly available test set, located in homework4_data/dev.
1. [5 points] Making use of the email module, write a function load_tokens(email_path) that
reads the email at the specified path, extracts the tokens from its message, and returns them as
a list.
Specifically, you should use the email.message_from_file(file_obj) function to create a
message object from the contents of the file, and the
email.iterators.body_line_iterator(message) function to iterate over the lines in the
message. Here, tokens are considered to be contiguous substrings of non-whitespace
characters.
>>> ham_dir = “homework4_data/train/ham/”
>>> load_tokens(ham_dir+”ham1″)[200:204]
[‘of’, ‘my’, ‘outstanding’, ‘mail’]
>>> load_tokens(ham_dir+”ham2″)[110:114]
[‘for’, ‘Preferences’, ‘-‘, “didn’t”]
>>> spam_dir = “homework4_data/train/spam/”
>>> load_tokens(spam_dir+”spam1″)[1:5]
[‘You’, ‘are’, ‘receiving’, ‘this’]
>>> load_tokens(spam_dir+”spam2″)[:4]
[”, ”, ‘

‘]
Homework 4 2/26/20, 3:18 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework4-cmpsc442.html Page 3 of 5
2. [30 points] Write a function log_probs(email_paths, smoothing) that returns a dictionary
from the words contained in the given emails to their Laplace-smoothed log-probabilities.
Specifically, if the set V denotes the vocabulary of words in the emails, then the probabilities
should be computed by taking the logarithms of
where w is a word in the vocabulary V, α is the smoothing constant (typically in the range 0 < α
≤ 1), and denotes a special word that will be substituted for unknown tokens at test
time.
>>> paths = [“homework4_data/train/ham/ham%d” % i
… for i in range(1, 11)]
>>> p = log_probs(paths, 1e-5)
>>> p[“the”]
-3.6080194731874062
>>> p[“line”]
-4.272995709320345
>>> paths = [“homework4_data/train/spam/spam%d” % i
… for i in range(1, 11)]
>>> p = log_probs(paths, 1e-5)
>>> p[“Credit”]
-5.837004641921745
>>> p[“”]
-20.34566288044584
3. [10 points] Write an initialization method
__init__(self, spam_dir, ham_dir, smoothing) in the SpamFilter class that creates two
log-probability dictionaries corresponding to the emails in the provided spam and ham
directories, then stores them internally for future use. Also compute the class probabilities
P(spam) and P(¬spam) based on the number of files in the input directories.
4. [25 points] Write a method is_spam(self, email_path) in the SpamFilter class that
returns a Boolean value indicating whether the email at the given file path is predicted to be
spam. Tokens which were not encountered during the training process should be converted
into the special word “” in order to avoid zero probabilities.
Recall from the lecture slides that for a given class c ∈ {spam, ¬spam},
P(w) = , count(w) + α
(∑ count( )) + α(|V| + 1) w ∈V ′ w′
P(⟨UNK⟩) = α
(∑ count( )) + α(|V| + 1) w ∈V ′ w′
P(c ∣ document) ∼ P(c) ∏P(w ∣ c , count(w)
Homework 4 2/26/20, 3:18 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework4-cmpsc442.html Page 4 of 5
where the normalization constant 1 / P(document) is the same for both classes and can
therefore be ignored. Here, the count of a word is computed over the input document to be
classified.
These computations should be computed in log-space to avoid underflow.
>>> sf = SpamFilter(“homework4_data/train/spam”,
… “homework4_data/train/ham”, 1e-5)
>>> sf.is_spam(“homework4_data/train/spam/spam1”)
True
>>> sf.is_spam(“homework4_data/train/spam/spam2”)
True
>>> sf = SpamFilter(“homework4_data/train/spam”,
… “homework4_data/train/ham”, 1e-5)
>>> sf.is_spam(“homework4_data/train/ham/ham1”)
False
>>> sf.is_spam(“homework4_data/train/ham/ham2”)
False
5. [25 points] Suppose we define the spam indication value of a word w to be the quantity
Similarly, define the ham indication value of a word w to be
Write a pair of methods most_indicative_spam(self, n) and
most_indicative_ham(self, n) in the SpamFilter class which return the n most indicative
words for each category, sorted in descending order based on their indication values. You
should restrict the set of words considered for each method to those which appear in at least
one spam email and one ham email. Hint: The probabilities computed within the
__init__(self, spam_dir, ham_dir, smoothing) method are sufficient to calculate these
quantities.
>>> sf = SpamFilter(“homework4_data/train/spam”,
P(c ∣ document) ∼ P(c) ∏P(w ∣ c ,
w∈V
)
count(w)
log( ). P(w ∣ spam)
P(w)
log( ). P(w ∣ ¬spam)
P(w)
Homework 4 2/26/20, 3:18 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework4-cmpsc442.html Page 5 of 5
… “homework4_data/train/ham”, 1e-5)
>>> sf.most_indicative_spam(5)
[‘<a’, ‘<input’, ”, ‘<meta’,”]>>> sf = SpamFilter(“homework4_data/train/spam”,… “homework4_data/train/ham”, 1e-5)>>> sf.most_indicative_ham(5)[‘Aug’, ‘ilug@linux.ie’, ‘install’,’spam.’, ‘Group:’]2. Feedback [5 points]1. [1 point] Approximately how long did you spend on this assignment?2. [2 points] Which aspects of this assignment did you find most challenging? Were there anysignificant stumbling blocks?3. [2 points] Which aspects of this assignment did you like? Is there anything you would havechanged?

CMPSC 442: Homework 5

In this assignment, you will gain experience working with Markov models on text.
A skeleton file homework5-cmpsc442.py containing empty definitions for each question has been provided.
Since portions of this assignment will be graded automatically, none of the names or function signatures in this
file should be modified. However, you are free to introduce additional variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in case you find
yourself reinventing the wheel.
You will find that in addition to a problem specification, most programming questions also include a pair of
examples from the Python interpreter. These are meant to illustrate typical use cases to clarify the assignment,
and are not comprehensive test suites. In addition to performing your own testing, you are strongly encouraged
to verify that your code gives the expected output for these examples before submitting.
You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was written in part
by the creator of Python. However, your code will not be graded for style.
1. Markov Models [95 points]
In this section, you will build a simple language model that can be used to generate random text resembling a
source document. Your use of external code should be limited to built-in Python modules, which excludes, for
example, NumPy and NLTK.
1. [10 points] Write a simple tokenization function tokenize(text) which takes as input a string of text
and returns a list of tokens derived from that text. Here, we define a token to be a contiguous sequence of
non-whitespace characters, with the exception that any punctuation mark should be treated as an
individual token. Hint: Use the built-in constant string.punctuation, found in the string module.
>>>tokenize(” This is an example. “)
[‘This’, ‘is’, ‘an’, ‘example’, ‘.’]
>>>tokenize(“‘Medium-rare,’ she said.”)
[“‘”, ‘Medium’, ‘-‘, ‘rare’, ‘,’, “‘”,
‘she’, ‘said’, ‘.’]
2. [10 points] Write a function ngrams(n, tokens) that produces a list of all n-grams of the specified size
from the input token list. Each n-gram should consist of a 2-element tuple (context, token), where the
context is itself an (n-1)-element tuple comprised of the n-1 words preceding the current token. The
sentence should be padded with n-1 “” tokens at the beginning and a single “” token at the
end. If n = 1, all contexts should be empty tuples. You may assume that n ≥ 1.
>>>ngrams(1, [“a”, “b”, “c”])
[((), ‘a’), ((), ‘b’), ((), ‘c’),
((), ”)]
>>>ngrams(2, [“a”, “b”, “c”])
[((”,), ‘a’), ((‘a’,), ‘b’),
((‘b’,), ‘c’), ((‘c’,), ”)]
>>>ngrams(3, [“a”, “b”, “c”])
[((”, ”), ‘a’),
((”, ‘a’), ‘b’),
((‘a’, ‘b’), ‘c’),
((‘b’, ‘c’), ”)]
3. [15 points] In the NgramModel class, write an initialization method __init__(self, n) which stores the
order n of the model and initializes any necessary internal variables. Then write a method
update(self, sentence) which computes the n-grams for the input sentence and updates the internal
counts. Lastly, write a method prob(self, context, token) which accepts an (n-1)-tuple representing a
context and a token, and returns the probability of that token occuring, given the preceding context.
>>>m = NgramModel(1)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>m.prob((), “a”)
0.3
>>>m.prob((), “c”)
0.1
>>>m.prob((), “”)
>>>m = NgramModel(2)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>m.prob((“”,), “a”)
1.0
>>>m.prob((“b”,), “c”)
0.3333333333333333
>>>m.prob((“a”,), “x”)
Homework 5 3/22/20, 9:31 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework5-cmpsc442.html Page 3 of 4
0.2 0.0
4. [20 points] In the NgramModel class, write a method random_token(self, context) which returns a
random token according to the probability distribution determined by the given context. Specifically, let T
= < t1, t2, . . . , tn > be the set of tokens which can occur in the given context, sorted according to Python’s
natural lexicographic ordering, and let 0 ≤ r < 1 be a random number between 0 and 1. Your method should return the token ti such that You should use a single call to the random.random() function to generate r. >>>m = NgramModel(1)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>random.seed(1)
>>>[m.random_token(())
for i in range(25)]
[”, ‘c’, ‘b’, ‘a’, ‘a’, ‘a’, ‘b’,
‘b’, ”, ”, ‘c’, ‘a’, ‘b’,
”, ‘a’, ‘b’, ‘a’, ‘d’, ‘d’,
”, ”, ‘b’, ‘d’, ‘a’, ‘a’]
>>>m = NgramModel(2)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>random.seed(2)
>>>[m.random_token((“”,))
for i in range(6)]
[‘a’, ‘a’, ‘a’, ‘a’, ‘a’, ‘a’]
>>>[m.random_token((“b”,))
for i in range(6)]
[‘c’, ”, ‘a’, ‘a’, ‘a’, ”]
5. [20 points] In the NgramModel class, write a method random_text(self, token_count) which returns
a string of space-separated tokens chosen at random using the random_token(self, context) method.
Your starting context should always be the (n-1)-tuple (“”, …, “”), and the context
should be updated as tokens are generated. If n = 1, your context should always be the empty tuple.
Whenever the special token “” is encountered, you should reset the context to the starting context.
>>>m = NgramModel(1)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>random.seed(1)
>>>m.random_text(13)
‘ c b a a a b b c a b’
>>>m = NgramModel(2)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>random.seed(2)
>>>m.random_text(15)
‘a b a b c d a b a b a b c’
6. [10 points] Write a function create_ngram_model(n, path) which loads the text at the given path and
creates an n-gram model from the resulting data. Each line in the file should be treated as a separate
sentence.
# No random seeds, so your results may vary
Homework 5 3/22/20, 9:31 PM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework5-cmpsc442.html Page 4 of 4
>>>m = create_ngram_model(1, “frankenstein.txt”); m.random_text(15)
‘beat astonishment brought his for how , door his . pertinacity to I felt’
>>>m = create_ngram_model(2, “frankenstein.txt”); m.random_text(15)
‘As the great was extreme during the end of being . Fortunately the sun’
>>>m = create_ngram_model(3, “frankenstein.txt”); m.random_text(15)
‘I had so long inhabited . You were thrown , by returning with greater’
>>>m = create_ngram_model(4, “frankenstein.txt”); m.random_text(15)
‘We were soon joined by Elizabeth . At these moments I wept bitterly and’
7. [10 points] Suppose we define the perplexity of a sequence of m tokens < w1, w2, . . . , wm > to be
For example, in the case of a bigram model under the framework used in the rest of the assignment, we
would generate the bigrams < (w0 = < START >, w1), (w1, w2), . . . , (wm-1, wm), (wm, wm+1 = ) >,
and would then compute the perplexity as
Intuitively, the lower the perplexity, the better the input sequence is explained by the model. Higher values
indicate the input was “perplexing” from the model’s point of view, hence the term perplexity.
In the NgramModel class, write a method perplexity(self, sentence) which computes the n-grams for
the input sentence and returns their perplexity under the current model. Hint: Consider performing an
intermediate computation in log-space and re-exponentiating at the end, so as to avoid numerical
overflow.
>>>m = NgramModel(1)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>m.perplexity(“a b”)
3.815714141844439
>>>m = NgramModel(2)
>>>m.update(“a b c d”)
>>>m.update(“a b a b”)
>>>m.perplexity(“a b”)
1.4422495703074083
2. Feedback [5 points]
1. [1 point] Approximately how long did you spend on this assignment?
2. [2 points] Which aspects of this assignment did you find most challenging? Were there any significant
stumbling blocks?
3. [2 points] Which aspects of this assignment did you like? Is there anything you would have changed?

CMPSC 442: Homework 6

In this assignment, you will gain experience working with hidden Markov models for part-of-speech
tagging.
A skeleton file homework6-cmpsc442.py containing empty definitions for each question has been
provided. Since portions of this assignment will be graded automatically, none of the names or
function signatures in this file should be modified. However, you are free to introduce additional
variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in case
you find yourself reinventing the wheel.
You will find that in addition to a problem specification, most programming questions also include
a pair of examples from the Python interpreter. These are meant to illustrate typical use cases to
clarify the assignment, and are not comprehensive test suites. In addition to performing your own
testing, you are strongly encouraged to verify that your code gives the expected output for these
examples before submitting.
You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was
written in part by the creator of Python. However, your code will not be graded for style.
1. Hidden Markov Models [95 points]
In this section, you will develop a hidden Markov model for part-of-speech (POS) tagging, using the
Brown corpus as training data. The tag set used in this assignment will be the universal POS tag set,
which is composed of the twelve POS tags NOUN (noun), VERB (verb), ADJ (adjective), ADV (adverb),
PRON (pronoun), DET (determiner or article), ADP (preposition or postposition), NUM (numeral),
CONJ (conjunction), PRT (particle), ‘.’ (punctuation mark), and X (other).
As in previous assignments, your use of external code should be limited to built-in Python modules,
which excludes packages such as NumPy and NLTK.
1. [10 points] Write a function load_corpus(path) that loads the corpus at the given path and
returns it as a list of POS-tagged sentences. Each line in the file should be treated as a
separate sentence, where sentences consist of sequences of whitespace-separated strings of
the form “token=POS”. Your function should return a list of lists, with individual entries
being 2-tuples of the form (token, POS).
>>> c = load_corpus(“brown_corpus.txt”)
>>> c[1402]
[(‘It’, ‘PRON’), (‘made’, ‘VERB’),
(‘him’, ‘PRON’), (‘human’, ‘NOUN’),
(‘.’, ‘.’)]
>>> c = load_corpus(“brown_corpus.txt”)
>>> c[1799]
[(‘The’, ‘DET’), (‘prospects’, ‘NOUN’),
(‘look’, ‘VERB’), (‘great’, ‘ADJ’),
(‘.’, ‘.’)]
2. [20 points] In the Tagger class, write an initialization method
__init__(self, sentences) which takes a list of sentences in the form produced by
load_corpus(path) as input and initializes the internal variables needed for the POS tagger.
In particular, if { t1, t2, . . . , tn } denotes the set of tags and { w1, w2, . . . , wm } denotes the set
of tokens found in the input sentences, you should at minimum compute:
Homework 6 4/9/20, 11:55 AM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework6-cmpsc442.html Page 3 of 4
The initial tag probabilities π(ti
) for 1 ≤ i ≤ n, where π(ti
) is the probability that a
sentence begins with tag ti
.
The transition probabilities a(ti → tj
) for 1 ≤ i, j ≤ n, where a(ti → tj
) is the probability
that tag tj
occurs after tag ti
.
The emission probabilities b(ti → wj
) for 1 ≤ i ≤ n and 1 ≤ j ≤ m, where b(ti → wj
) is the
probability that token wj
is generated given tag ti
.
It is imperative that you use Laplace smoothing where appropriate to ensure that your system
can handle novel inputs, but the exact manner in which this is done is left up to you as a
design decision. Your initialization method should take no more than a few seconds to
complete when given the full Brown corpus as input.
3. [25 points] In the Tagger class, write a method most_probable_tags(self, tokens)
which returns the list of the most probable tags corresponding to each input token. In
particular, the most probable tag for a token wj
is defined to be the tag with index i
* =
argmaxi
b(ti → wj
).
>>> c = load_corpus(“brown_corpus.txt”)
>>> t = Tagger(c)
>>> t.most_probable_tags(
… [“The”, “man”, “walks”, “.”])
[‘DET’, ‘NOUN’, ‘VERB’, ‘.’]
>>> c = load_corpus(“brown_corpus.txt”)
>>> t = Tagger(c)
>>> t.most_probable_tags(
… [“The”, “blue”, “bird”, “sings”])
[‘DET’, ‘ADJ’, ‘NOUN’, ‘VERB’]
4. [40 points] In the Tagger class, write a method viterbi_tags(self, tokens) which
returns the most probable tag sequence as found by Viterbi decoding. Recall from lecture that
Viterbi decoding is a modification of the Forward algorithm, adapted to find the path of
highest probability through the trellis graph containing all possible tag sequences.
Computation will likely proceed in two stages: you will first compute the probability of the
most likely tag sequence, and will then reconstruct the sequence which achieves that
probability from end to beginning by tracing backpointers.
>>> c = load_corpus(“brown_corpus.txt”)
>>> t = Tagger(c)
>>> s = “I am waiting to reply”.split()
>>> t.most_probable_tags(s)
[‘PRON’, ‘VERB’, ‘VERB’, ‘PRT’, ‘NOUN’]
>>> t.viterbi_tags(s)
[‘PRON’, ‘VERB’, ‘VERB’, ‘PRT’, ‘VERB’]
>>> c = load_corpus(“brown_corpus.txt”)
>>> t = Tagger(c)
>>> s = “I saw the play”.split()
>>> t.most_probable_tags(s)
[‘PRON’, ‘VERB’, ‘DET’, ‘VERB’]
>>> t.viterbi_tags(s)
[‘PRON’, ‘VERB’, ‘DET’, ‘NOUN’]
Homework 6 4/9/20, 11:55 AM
file:///Users/kxk302/Documents/cmpsc442/cmpsc442-homework-tempates-html-data/homework6-cmpsc442.html Page 4 of 4
2. Feedback [5 points]
1. [1 point] Approximately how long did you spend on this assignment?
2. [2 points] Which aspects of this assignment did you find most challenging? Were there any
significant stumbling blocks?
3. [2 points] Which aspects of this assignment did you like? Is there anything you would have
changed?