'''
15-110 Homework 4
Name:
Andrew ID:
'''
################################################################################
''' #1 - createAuthorMap(bookMap) - 10pts
Write the function createAuthorMap which takes bookMap, a dictionary that maps
book titles (strings) to their authors (also strings), and returns a new dictionary
that maps authors to lists of all the books they've written. Make sure not to
destructively modify bookMap as you generate the new dictionary!
'''
def createAuthorMap(bookMap):
return
''' #2 - findFile(t, name) - 10pts
We can represent a filesystem as a tree by making each folder a node with
children, where the children are the items in the folder. Files are then nodes
with no children. We'll use the general dictionary tree structure we demonstrated
in class for this problem, which maps the key "children" to a list of
dictionaries (child nodes).
Given a tree t that represents a file system and a filename name (a string),
write the function findFile(t, name) which returns True if that filename exists
in the file system, and False otherwise. Note that the filenames will be in the
values of the nodes.
Solving this problem for a tree with no children (a file) should be easy. To
solve the problem for a tree with children (a folder), consider this: if you can
find the filename in any of the child trees, then you can return True right away!
On the other hand, if you search all the children and the file is in none of them,
you can return False.
'''
def findFile(t, name):
return
''' #3 - nearestNeighbor(nodeList, edgeMatrix, node) - 10pts
We can represent cities in the United States as nodes in a graph, and use edges
to connect the cities that offer flights from one to the other. We can also give
those edges values- the distance from one city to another.
Write the function nearestNeighbor(nodeList, edgeMatrix, node) which takes a
graph in adjacency matrix format (nodeList and edgeMatrix) and a string,
node (a city name), and returns the closest neighbor to node. For example, in
the graph shown in the write-up, Pittsburgh's nearest neighbor would be Washington DC.
Recall that in adjacency matrix format, a graph's node list is a 1D list that
maps each index to a node value (in this case, the name of a city), and an edge
matrix is a 2D list, where matrix[i][j] represents the value of the edge between
nodeList[i] and nodeList[j], or None if they are not connected.
To write this function, you will need to take the following steps:
- Identify the index in nodeList of the given city, node.
- Keep track of two data values - the current closest city and the current
shortest distance. These can start as None and a very large number, like 1000.
- Iterate over each city index in the edge matrix.
-- If there exists an edge between that city index and our node city,
compare the distance between the two to the current shortest distance.
-- If the edge distance is smaller, update the current closest city and
current shortest distance.
- Once you have checked all the cities, return the current closest city.
'''
def nearestNeighbor(nodeList, edgeMatrix, node):
return
''' #4 - getAllFollowers(network, name) - 15pts
It's easy to determine the number of followers you have on a social media platform
like Twitter, but the displayed number does not account for people who follow your
followers, but do not (yet) follow you. We want to determine how many
eventual-followers a person has.
An eventual-follower of X is either
a) someone who follows X, or
b) someone other than X who is a follower of another person, Y, who is an
eventual-follower of X.
View the written starter file for an in-depth example of how eventual-followers work.
Write the function getAllFollowers(network, name) which takes a graph in the
dictionary format, network, and a string, name, and returns a list of all
eventual-followers of name.
Major Hint: This problem is a variant on the idea of searching a graph! Instead of
searching for an item, it's just searching for ALL the nodes connected to the start.
If you're lost, try starting with the breadth-first search or depth-first search
from the class notes, then modify it to return a list of followers instead of
True or False. You'll need to change two parts of the function: the part that
actually checks if an item has been found, and the value that is returned at the end.
'''
def getAllFollowers(network, name):
return
################################################################################
''' To check your work, click 'Run File as Script' to run the test function
shown below. You should also check the autograder results on Gradescope! '''
def testCreateAuthorMap():
print("Testing createAuthorMap()...")
assert(createAuthorMap({ "Test" : "Test" }) != None)
print("Check that " + str(createAuthorMap({ "The Hobbit" : "JRR Tolkein", "Harry Potter" : "JK Rowling", "Lord of the Rings" : "JRR Tolkein", "Casual Vacancy" : "JK Rowling", "A Game of Thrones" : "George RR Martin", "A Storm of Swords" : "George RR Martin" })) + " returns " + str({ "JRR Tolkein" : ["The Hobbit", "Lord of the Rings"], "JK Rowling" : ["Harry Potter", "Casual Vacancy"], "George RR Martin" : ["A Game of Thrones", "A Storm of Swords"] }))
print("Check that " + str(createAuthorMap({ "A Wrinkle in Time" : "Madeline L'Engle", "The Golden Compass" : "Phillip Pullman", "The Subtle Knife" : "Phillip Pullman", "The Amber Spyglass" : "Phillip Pullman" })) + " returns " + str({ "Madeline L'Engle" : ["A Wrinkle in Time"], "Phillip Pullman" : ["The Golden Compass", "The Subtle Knife", "The Amber Spyglass"]}))
print("Check that " + str(createAuthorMap({ "A Natural History of Dragons" : "Marie Brennan"})) + " returns " + str({ "Marie Brennan" : ["A Natural History of Dragons"] }))
print("Check that " + str(createAuthorMap({ })) + " returns " + str({ }))
print("... done!")
def testFindFile():
print("Testing findFile()...", end="")
t1 = { "value" : "FolderA", "children" :
[ { "value" : "FolderB", "children" :
[ { "value" : "File1", "children" : [ ] },
{ "value" : "File2", "children" : [ ] }
]
},
{ "value" : "File3", "children" : [ ] }
]
}
assert(findFile(t1, "File1") == True)
assert(findFile(t1, "File2") == True)
assert(findFile(t1, "File3") == True)
assert(findFile(t1, "File4") == False)
t2 = { "value" : "FolderJ", "children" :
[
{ "value" : "FolderK", "children" :
[
{ "value" : "FolderM", "children" :
[
{ "value" : "Folder0", "children" :
[
{ "value" : "File12", "children" : [ ] }
]
}
]
},
{ "value" : "File2", "children" : [ ] }
]
},
{ "value" : "File10", "children" : [ ] },
{ "value" : "File11", "children" : [ ] },
{ "value" : "FolderN", "children" :
[
{ "value" : "File13", "children" : [ ] },
{ "value" : "File14", "children" : [ ] }
]
},
{ "value" : "FolderL", "children" :
[
{ "value" : "Foobar", "children" : [ ] }
]
}
]
}
assert(findFile(t2, "File10") == True)
assert(findFile(t2, "File12") == True)
assert(findFile(t2, "File14") == True)
assert(findFile(t2, "Foobar") == True)
assert(findFile(t2, "File9") == False)
assert(findFile(t2, "Secret") == False)
t3 = { "value" : "File1", "children" : [ ] }
assert(findFile(t3, "File1") == True)
assert(findFile(t3, "File2") == False)
print("... done!")
def testNearestNeighbor():
print("Testing nearestNeighbor()...", end="")
nodeList = ["Detroit", "New York City", "Pittsburgh", "Philadelphia", "Baltimore", "Washington DC"]
matrix = [
[ None, 587, 277, None, None, 499 ],
[ 587, None, None, 88, None, None ],
[ 277, None, None, 289, 224, 223 ],
[ None, 88, 289, None, 99, None ],
[ None, None, 224, 99, None, 36 ],
[ 499, None, 223, None, 36, None ]
]
assert(nearestNeighbor(nodeList, matrix, "Pittsburgh") == "Washington DC")
assert(nearestNeighbor(nodeList, matrix, "Detroit") == "Pittsburgh")
assert(nearestNeighbor(nodeList, matrix, "Washington DC") == "Baltimore")
assert(nearestNeighbor(nodeList, matrix, "Baltimore") == "Washington DC")
assert(nearestNeighbor(nodeList, matrix, "New York City") == "Philadelphia")
assert(nearestNeighbor(nodeList, matrix, "Philadelphia") == "New York City")
print("... done!")
def testGetAllFollowers():
print("Testing getAllFollowers()...", end="")
d1 = { "Jasnah" : [ "Shallan", "Dalinar" ],
"Dalinar" : [ "Shallan", "Adolin", "Kaladin" ],
"Kaladin" : [ "Adolin" ], "Adolin" : [ "Shallan" ],
"Shallan" : [ "Adolin", "Veil", "Radiant" ],
"Veil" : [ "Shallan", "Radiant" ], "Radiant" : [ "Shallan", "Veil" ],
"Sadaes" : [ ] }
assert(getAllFollowers(d1, "Kaladin") != None)
result1 = getAllFollowers(d1, "Jasnah")
assert(sorted(result1) == [ "Adolin", "Dalinar", "Kaladin", "Radiant", "Shallan", "Veil" ])
result2 = getAllFollowers(d1, "Dalinar")
assert(sorted(result2) == [ "Adolin", "Kaladin", "Radiant", "Shallan", "Veil" ])
result3 = getAllFollowers(d1, "Kaladin")
assert(sorted(result3) == [ "Adolin", "Radiant", "Shallan", "Veil" ])
result4 = getAllFollowers(d1, "Adolin")
assert(sorted(result4) == [ "Radiant", "Shallan", "Veil" ])
result5 = getAllFollowers(d1, "Shallan")
assert(sorted(result5) == [ "Adolin", "Radiant", "Veil" ])
result6 = getAllFollowers(d1, "Veil")
assert(sorted(result6) == [ "Adolin", "Radiant", "Shallan" ])
result7 = getAllFollowers(d1, "Radiant")
assert(sorted(result7) == [ "Adolin", "Shallan", "Veil" ])
assert(getAllFollowers(d1, "Sadaes") == [ ])
print("... done!")
def testAll():
testCreateAuthorMap()
testFindFile()
testNearestNeighbor()
testGetAllFollowers()
testAll()