Assignment 5
Due Tues, Oct 9
Please create a single zip file named
<userid>-hw5.zip (i.e. kay-hw5.zip) that contains these files:
hw5-1.py (the solution of question 1)
hw5-2.py (the solution of question 2)
hw5-3.py (the solution of question 3)
Email your solutions to kay <at> ischool. Include comments in each script stating your name, the name of any collaborators, and approximate time it took you to complete the exercise.
To assist with grading, please name all your functions exactly as they are specified below, and use the same list of arguments.
1. Matrix Rotation
Tuples can be used to represent a 2x2 matrix. First, place each row in a tuple, then create a third tuple that contains the top row and then the bottom row. For example, the matrix,
1 2
3 4
should be expressed as the tuple, ((1,2), (3,4)). Write a function that takes a 2x2 matrix in this format and rotates it 90 degrees counter-clockwise. Please name your function exactly as below:
def rotate_90(matrix):
"""Takes a 2x2 matrix in tuple format and returns the matrix rotated 90 degrees counter-clockwise"""
For example, rotating the matrix above should give
2 4
1 3
Your function should return the rotated matrix in the same tuple format, so this example should be returned as the tuple, ((2,4), (1,3)).
2. String Rearrangement
a) Write a function that takes two strings and returns True if they are anagrams – that is, if rearranging the letters of one string can transform it into the other. Name your function as follows:
def are_anagrams(str_1, str_2):
"""returns True or False (boolean value) whether two strings are anagrams"""
For this problem, use s_str.lower() to compare lowercase letters. Hint: sorted(s_str) returns a list of the characters in s_str in alphabetical order.
b) Write a second function that takes two strings as arguments, changes them to lowercase, turns them into lists, and returns true if they are the same string, but backwards. Name your function as follows:
def is_backwards(str_1, str_2):
"""returns True or False (boolean value) whether two strings are the same but backwards (ignores case)"""
3. Stepping into Lists
Let’s call a list numerical if it only contains numbers (type int or float) and other lists, and any path we take stepping into the list (by following list references, or in other words, always moving from a list to an object contained in that list) ends with a number or an empty list. These are the lists that can be written down using just numbers and brackets, for example,
[0.5], [2,[3],[1,3]], [[[[]]]]
a) Write the following function,
def sum_numerical( l_list ):
that takes a numerical list and finds the total of all the numbers that can be reached by stepping into l_list. These are the numbers that appear when the list is printed. Hint: this is a sensible place to use recursion. To check the type of a list item, you may use a statement like
if isinstance(item, int):
b) Write the following function,
def flatten( l_list, flat ):
to create a list of all the objects that can be reached by stepping into l_list. This function should use the same recursive structure as your sum_numerical function, but add an argument, flat, to hold a list of all the objects you reach (initially, assume that flat will be []). Each time you reach a new object, instead of adding it to a sum, append it to flat. Do this for both lists and numbers. Your function should not return anything, because all the information we're interested in is already being appended to flat.
In the end, you will have a flat list containing all the objects that can be reached through references from your original list.
Finally, a warning: remember that lists can contain themselves, or their references can have cycles. Before you append an item to flat, if it's a list, check to see if it’s already in flat. This means you have to check if flat has a reference to the actual list object in the object space. Please use the following function to check this:
def contains_list(outer_list, inner_list):
"""Returns True if outer_list directly contains
(has a direct reference to) inner_list"""
for i in outer_list:
if i is inner_list:
return True
return False
Then call the function using a statement like
if isinstance(item, list) and contains_list(flat, item):
return
If the list is already in flat, don’t append it to flat again, and don’t keep stepping into the list – doing so will result in an infinite loop!
c) Write the following function,
def has_cycles( l_list, flat):
that checks to see if stepping into a list can lead to any infinite cycles. Use the same structure as your flatten function, but return True if you encounter an object that is already in flat.
d) Finally, write a function,
def is_numerical(l_list):
that returns True if l_list has no cycles, and any object you can reach by stepping into l_list is a list or a number.