Computer Science 15-112, Fall 2012
Class Notes: Practice (through week 7)
2d-List and Sets/Dictionaries Problems
Do not use recursion
Make all your functions non-destructive unless explicitly indicated otherwise.
isMagicSquare
Write the function isMagicSquare(a) that takes a 2d list and returns
True if it is a
magic
square and False otherwise.
makeMagicSquare
Write the function makeMagicSquare(n) that takes a positive odd integer
n and returns an nxn magic square by following De La Loubere's Method
as described
here. If n is not a positive odd integer, return None.
isLatinSquare
Write the function isLatinSquare(a) that takes a 2d list and returns
True if it is a
Latin
square and False otherwise.
matrixAdd
Write the function matrixAdd(m1, m2) that takes two 2d lists (that we
will consider to be matrices, in the linear algebra sense) and returns a new
2d list that is the result of
adding the two matrices. Return None if the two matrices cannot be
added for any reason.
matrixMultiply
Write the function matrixMultiply(m1, m2) that takes two 2d lists (that
we will consider to be matrices, in the linear algebra sense) and returns a
new 2d list that is the result of
multiplying the two matrices. Return None if the two matrices
cannot be multiplied for any reason.
removeRowAndCol
Write the function removeRowAndCol(A, row, col) that takes a 2d list A,
a row index and a col index, and non-destructively returns a new 2d list
with the given row and column removed. So, if:
A = [ [ 2, 3, 4, 5],
[ 8, 7, 6, 5],
[ 0, 1, 2, 3]
]
Then removeRowAndCol(A, 1, 2) returns:
[ [ 2, 3, 5],
[ 0, 1, 3]
]
Also, A remains unchanged.
destructiveRemoveRowAndCol
Rewrite the previous function so it is destructive. In this case, the
return value is None and instead the 2d list A is destructively modified to
remove the given row and column. Thought question:
In general, how might you have to change a test function when
dealing with destructive function calls rather than non-destructive calls?
isKnightsTour
Background: A "knight's
tour" in chess is a sequence of legal knight moves such that the knight
visits every square exactly once. We can represent a (supposed)
knight's tour as an NxN list of the integers from 1 to N^{2} listing
the positions in order that the knight occupied on the tour. If it is
a legal knight's tour, then all the numbers from 1 to N^{2} will be
included and each move from k to (k+1) will be a legal knight's move.
With this in mind, write the function isKnightsTour(board) that takes such a
2d list of integers and returns True if it represents a legal knight's tour
and False otherwise.
nQueensChecker
Background: The "N Queens" problem asks if we can place N queens
on an NxN chessboard such that no two queens are attacking each other.
For most values of N, there are many ways to solve this problem. Here,
you will write the function nQueensChecker(board) that takes a 2d list of
booleans where True indicates a queen is present and False indicates a blank
cell, and returns True if this NxN board contains N queens all of which do
not attack any others, and False otherwise.
makeOthelloMove
Background: read about the game of
Othello
(also known as Reversi). Maybe even play it briefly (say,
here). We can represent an Othello board as an NxN list of values
-- 'w' for white, 'b' for black, and the empty string for empty (of course).
If we number the rows from the top and columns from the left, write the
function makeOthelloMove(board, row, col, player) that takes such a board, a
row, a col, and a player ('w' or 'b'), and, if it is legal for the given
player to place a piece at the given position, the function destructively
modifies the board to reflect this move (flipping pieces as needed), and it
returns the number of pieces flipped. If the move is not legal,
the function does not modify the board and returns 0.
playCheckers
Write the function playCheckers(N) that manages a 2-person NxN game of
checkers. You should display the board before each turn. Ask the
current player for their move. If the move is illegal, say so, and ask
for a legal move. When you get a legal move, make the move and switch
players. Keep going until a player does not have a legal move, in
which case they lose. To make it more fun and more challenging,
include handling kings properly.
invertDictionary
Write the function invertDictionary(d) that takes a dictionary d that
maps keys to values and returns a dictionary of its inverse, that maps the
original values back to their keys. One complication: there can be
duplicate values in the original dictionary. That is, there can be keys k1
and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v. In
that case, what should inverseD[v] equal? Answer: map the original values
back to the set of keys that originally mapped to them. Thus, in
this example, inverseD[v] maps to a set containing both s1 and s2. Some
thought questions:
What happens if the original dictionary d contains mutable values?
Is it always true that
invertDictionary(invertDictionary(d)) == d? Explain.
sparseMatrixAdd
A "sparse" matrix is mostly filled with 0's. It may be quite
large, with very few non-zero entries. As such, it is very wasteful to
represent it using a 2d list. Instead, we can use a dictionary where
we only store the non-zero values. Write the function
sparseMatrixAdd(m1, m2) that takes two sparse matrices represented in this
way and returns a third sparse matrix that is the result of adding the two
matrices. Return None if the two matrices cannot be added for any
reason.
getPairSum
Write the function getPairSum(a, target) that takes a list of numbers and a
target value (also a number), and if there is a pair of numbers in the given
list that add up to the given target number, returns that pair, and
otherwise returns an empty list. If there is more than one valid pair,
you can return any of them. This can be done in O(n) time. For
example:
getPairSum([1],1) == []
getPairSum([5,2],7) == [5,2]
getPairSum([10,-1,1,-8,3,1], 2) == [10,-8] (can also return [-1,3] or [1,1])
getPairSum([10,-1,1,-8,3,1],10) == []
carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem