PY-04: Dictionaries
Read the task files below or download the starter files. Use the Canvas assignment to open CodeGrade and submit your work.
Dictionaries
This assignment is designed to help you become familiar with dictionaries. Work through all 15 exercises below.
Learning objectives
By completing this assignment, you will be able to:
- Use
dictionariesto store key-value pairs. - Use
dictionariesto store different types of data (e.g., strings, integers, lists). - Loop
dictionariesto filter, transform, delete, or update data. - Use
dictionariesto store otherdictionaries(nested dictionaries).
Instructions
For offline practice, complete the functions in the downloaded files below. Each file states its inputs, output, rules, and examples. Replace the NotImplementedError line with your code. Keep the supplied filenames, function names, parameters, and docstrings.
For graded submissions, open the Canvas assignment and edit the files already supplied in CodeGrade. Match the exercises by their function names and keep the filenames supplied in that editor.
Select Auto Test, then Run AutoTest to check your work. Read the feedback, revise the relevant file, and run it again. AutoTest does not create a submission. Select Hand-in your work to submit your work before the Canvas due date.
Each exercise counts as complete when all its checks pass. The tests include cases beyond the examples.
Overview of the exercises
Consider approaching the exercises in the order below:
Dictionary Manipulation
The exercises in this section focus on basic dictionary operations, such as creating, updating, and deleting key-value pairs.
dict_squares.py: Generate squares of numbers in a range.
Create a dictionary where keys are numbers in a range and values are their squares.dict_count_letters.py: Count the frequency of letters in a string.
Count the occurrence of each letter in a string and store it in a dictionary.dict_delete_entry_from_nested_dict.py: Delete an entry from a nested dictionary.
Remove a specific key-value pair from a nested dictionary structure.dict_filter_by_key.py: Filter a dictionary by keys.
Extract a subset of a dictionary based on a list of keys.dict_from_lists.py: Create a dictionary from two lists.
Combine two lists, one for keys and one for values, to form a dictionary.dict_count_unique_values.py: Count unique values in a list.
Calculate the frequency of each unique value in a list.dict_invert.py: Invert keys and values in a dictionary.
Swap the keys and values of a dictionary.dict_deep_copy.py: Demonstrate shallow vs. deep copy.
Illustrate the difference between shallow and deep copies in nested dictionaries.dict_merge.py: Merge dictionaries and explore deep copy.
Combine multiple dictionaries and explore the use of deep copying for nested data.
Use Cases (Practical Applications)
The exercises in this section demonstrate practical applications of dictionaries in real-world scenarios.
dict_calculate_total_distance.py: Calculate the total distance of a route.
Compute the total distance of a journey based on distances between cities.
Useful for: Planning trips or analyzing travel routes.dict_simple_chatgpt.py: Predict the next word in a sentence.
Simulate a basic word predictor using dictionary-based probabilities.
Useful for: Building simple language models or autocomplete systems.dict_to_sorted_tuples.py: Sort dictionary as tuples by keys or values.
Return a sorted list of tuples based on dictionary keys or values.
Useful for: Sorting data in a dictionary before further processing.dict_filter_by_values.py: Filter a list of dictionaries by criteria.
Extract dictionaries from a list that match specified criteria.
Useful for: Searching structured data (e.g., finding customers by age and city).dict_graph_reachability.py: Analyze graph reachability.
Find the set of cities reachable from each city in a graph.
Useful for: Analyzing connectivity (e.g., city routes, social networks).dict_of_feature_combinations.py: Generate feature combinations.
Create a dictionary of all possible feature combinations for a list of products.
Useful for: Product recommendation systems (e.g., identifying shared features among frequently bought products).
Python files
dict_squares.py
Listing 1 shows the contents of dict_squares.py.
dict_squares.py
def dict_of_squares(
n: int
) -> dict[int, int]:
"""
Create a dictionary where the keys are numbers from 1 to n and the values
are their squares.
Parameters
----------
n : int
The upper limit of numbers.
Returns
-------
dict[int, int]
A dictionary containing numbers and their squares.
Examples
--------
>>> dict_of_squares(5)
{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
"""
raise NotImplementedError("Complete this function.")dict_count_letters.py
Download dict_count_letters.py.
Listing 2 shows the contents of dict_count_letters.py.
dict_count_letters.py
def count_letters(
string: str
) -> dict[str, int]:
"""
Count the occurrences of each letter in a string and store the counts
in a dictionary. The letter counts are case-insensitive.
Parameters
----------
string : str
The string to analyze.
If empty (i.e., ''), return an empty dictionary.
Returns
-------
dict[str, int]
A dictionary with letters as keys and their
occurrence counts as values. Numbers, punctuation, and whitespace are
not counted, only letters.
Examples
--------
>>> count_letters("hello world")
{'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}
>>> count_letters("")
{}
>>> count_letters("Hello, World!")
{'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}
>>> count_letters("aAaAaA")
{'a': 6}
>>> count_letters("1234")
{}
"""
raise NotImplementedError("Complete this function.")dict_delete_entry_from_nested_dict.py
Download dict_delete_entry_from_nested_dict.py.
Listing 3 shows the contents of dict_delete_entry_from_nested_dict.py.
dict_delete_entry_from_nested_dict.py
def delete_entry_from_nested_dict(
nested_dict: dict[str, dict[str, str | int]],
id_to_delete: str
) -> dict[str, dict[str, str | int]]:
"""
Delete an entry with a specified ID from a nested dictionary.
Parameters
----------
nested_dict : dict[str, dict[str, str | int]]
A nested dictionary where keys are IDs.
id_to_delete : str
The ID of the entry to delete.
Returns
-------
dict[str, dict[str, str | int]]
The nested dictionary after deleting the specified entry.
Examples
--------
>>> nested_dict = {
... '1': {'name': 'Alice', 'age': 30},
... '2': {'name': 'Bob', 'age': 25}
... }
>>> delete_entry_from_nested_dict(nested_dict, '1')
{'2': {'name': 'Bob', 'age': 25}}
>>> delete_entry_from_nested_dict(nested_dict, '3')
{'2': {'name': 'Bob', 'age': 25}}
>>> delete_entry_from_nested_dict(nested_dict, '2')
{}
"""
raise NotImplementedError("Complete this function.")dict_filter_by_key.py
Download dict_filter_by_key.py.
Listing 4 shows the contents of dict_filter_by_key.py.
dict_filter_by_key.py
def filter_dictionary_by_keys(
data_dict: dict,
keys: list
) -> dict:
"""
Filter a dictionary, keeping only specified keys.
Keys not found in the dictionary are ignored. If no requested keys are
found, an empty dictionary is returned.
Parameters
----------
data_dict : dict
The original dictionary.
keys : list
The keys to keep in the dictionary.
Returns
-------
dict
A filtered dictionary.
Examples
--------
>>> filter_dictionary_by_keys({'a': 1, 'b': 2, 'c': 3}, ['a', 'c'])
{'a': 1, 'c': 3}
>>> filter_dictionary_by_keys({'a': 1, 'b': 2, 'c': 3}, [1, 2])
{}
"""
raise NotImplementedError("Complete this function.")dict_from_lists.py
Listing 5 shows the contents of dict_from_lists.py.
dict_from_lists.py
def create_dict_from_lists(
keys: list[str | int],
values: list[str | int]
) -> dict[str | int, str | int]:
"""
Create a dictionary from two same-size lists, one for keys and one for values.
Parameters
----------
keys : list[str | int]
A list of keys (immutable type).
values : list[str | int]
A list of values.
Returns
-------
dict[str | int, str | int]
A dictionary created from the provided lists.
Examples
--------
>>> create_dict_from_lists(['a', 'b', 'c'], [1, 2, 3])
{'a': 1, 'b': 2, 'c': 3}
>>> create_dict_from_lists([1, 2, 3], ['a', 'b', 'c'])
{1: 'a', 2: 'b', 3: 'c'}
"""
raise NotImplementedError("Complete this function.")dict_count_unique_values.py
Download dict_count_unique_values.py.
Listing 6 shows the contents of dict_count_unique_values.py.
dict_count_unique_values.py
def count_unique_values(
lst: list
) -> dict:
"""
Count the occurrences of each unique value in a list.
Parameters
----------
lst : list
A list of values, which can be of any hashable type.
If empty, return an empty dictionary.
Returns
-------
dict
A dictionary with unique values from the list as keys and their
occurrence counts as values.
Examples
--------
>>> count_unique_values([1, 2, 2, 3, 3, 3])
{1: 1, 2: 2, 3: 3}
>>> count_unique_values(['a', 'b', 'a', 'c', 'c', 'c'])
{'a': 2, 'b': 1, 'c': 3}
>>> count_unique_values(['a', 'b', 'c'])
{'a': 1, 'b': 1, 'c': 1}
>>> count_unique_values([2.4])
{2.4: 1}
"""
raise NotImplementedError("Complete this function.")dict_invert.py
Listing 7 shows the contents of dict_invert.py.
dict_invert.py
def invert_dict(
data_dict: dict
) -> dict:
"""
Invert the keys and values of a dictionary.
Parameters
----------
data_dict : dict
The dictionary to invert. Keys and values are immutable types.
Returns
-------
dict
The inverted dictionary.
Examples
--------
>>> invert_dict({'a': 1, 'b': 2, 'c': 3})
{1: 'a', 2: 'b', 3: 'c'}
"""
raise NotImplementedError("Complete this function.")dict_deep_copy.py
Listing 8 shows the contents of dict_deep_copy.py.
dict_deep_copy.py
import copy
def deep_copy_nested_dict(
nested_dict: dict[str, dict[str, list]]
) -> dict[str, dict[str, list]]:
"""
Create a deep copy of a nested dictionary.
A deep copy is a new object that is created recursively, copying all
the collections found in the original dictionary.
This way, the new dictionary is independent of the original one: if you
modify the new dictionary, the original dictionary remains unchanged.
Parameters
----------
nested_dict : dict[str, dict[str, list]]
A nested dictionary where the inner dictionary may contain
other collections.
Returns
-------
dict[str, dict[str, list]]
A deep copy of the nested dictionary.
Examples
--------
>>> nested_dict = {
... 'key1': {'innerKey1': [1, 2, 3], 'innerKey2': [4, 5]},
... 'key2': {'innerKey3': [6, 7]}
... }
>>> copied_dict = deep_copy_nested_dict(nested_dict)
>>> assert copied_dict["key1"] is not nested_dict["key1"]
>>> assert copied_dict["key2"] is not nested_dict["key2"]
"""
raise NotImplementedError("Complete this function.")dict_merge.py
Listing 9 shows the contents of dict_merge.py.
dict_merge.py
import copy
def merge_dictionaries(
dict1: dict,
dict2: dict
) -> dict:
"""
Merge two dictionaries, with values from the second dictionary
overriding those from the first in case of key overlap.
The merged dictionary values must be deepcopied to avoid side effects.
Parameters
----------
dict1 : dict
The first dictionary.
dict2 : dict
The second dictionary.
Returns
-------
dict
The merged dictionary.
Examples
--------
>>> merge_dictionaries({'a': 1, 'b': 2}, {'b': 3, 'c': 4})
{'a': 1, 'b': 3, 'c': 4}
"""
raise NotImplementedError("Complete this function.")dict_calculate_total_distance.py
Download dict_calculate_total_distance.py.
Listing 10 shows the contents of dict_calculate_total_distance.py.
dict_calculate_total_distance.py
def calculate_total_distance(
distances: dict[str, dict[str, float]],
city_path: list[str]
) -> int:
"""
Calculate the total distance for a specified path of cities.
Distances are directed. Each leg must be stored from its origin to its
destination; a stored reverse leg does not make the leg feasible.
Parameters
----------
distances : dict[str, dict[str, float]]
A nested (non-empty) dictionary where keys are origin cities and
values are dictionaries with destination cities and their distances.
city_path : list[str]
A list of cities representing the travel path. The list has at least
two cities.
Returns
-------
int
The total distance for the path or -1 if the path is infeasible.
Examples
--------
>>> distances = {
... 'CityA': {'CityB': 10, 'CityC': 20},
... 'CityB': {'CityC': 30},
... 'CityC': {'CityA': 20},
... 'CityD': {'CityB': 20},
... }
>>> calculate_total_distance(distances, ['CityA', 'CityB', 'CityC'])
40
>>> calculate_total_distance(distances, ['CityA', 'CityD'])
-1
"""
raise NotImplementedError("Complete this function.")dict_simple_chatgpt.py
Download dict_simple_chatgpt.py.
Listing 11 shows the contents of dict_simple_chatgpt.py.
dict_simple_chatgpt.py
def predict_next_words(
probability_matrix: dict[str, dict[str, float]],
initial_words: list[str],
num_words: int
) -> list[str]:
"""
Predict the next words in a phrase using a given probability matrix.
Start from the last initial word. At each step, choose the next word with
the highest probability. For equal probabilities, choose the word that
appears first in the corresponding dictionary.
Parameters
----------
probability_matrix : dict[str, dict[str, float]]
A dictionary where each key is a word and its value is another
dictionary mapping subsequent words to probabilities.
initial_words : list[str]
The initial words of the phrase, containing at least one word.
num_words : int
The nonnegative number of words to predict.
Returns
-------
list[str]
The predicted `num_words` following the initial words.
If no next word is found, the prediction stops.
Examples
--------
>>> prob_matrix = {
... "I": {"am": 0.5, "have": 0.5},
... "am": {"a": 1.0},
... "a": {"developer": 0.6, "designer": 0.4}
... }
>>> predict_next_words(prob_matrix, ["I"], 3)
['am', 'a', 'developer']
"""
raise NotImplementedError("Complete this function.")dict_to_sorted_tuples.py
Download dict_to_sorted_tuples.py.
Listing 12 shows the contents of dict_to_sorted_tuples.py.
dict_to_sorted_tuples.py
def dict_to_sorted_tuples(
data_dict: dict[str, int],
sort_by_values: bool = False
) -> list[tuple]:
"""
Sort a dictionary and return its items as a list of tuples.
The sorting is based on keys by default.
If 'sort_by_values' is True, it sorts by values.
If 'sort_by_values' is True and two values are equal, it sorts by key.
Parameters
----------
data_dict : dict[str, int]
The dictionary to sort.
sort_by_values : bool, optional
Determines if sorting is done by values. Defaults to False.
Returns
-------
list[tuple]
A list of tuples: Sorted items of the dictionary.
Examples
--------
>>> dict_to_sorted_tuples({'x': 2, 'b': 2, 'a': 1, 'c': 3})
[('a', 1), ('b', 2), ('c', 3), ('x', 2)]
>>> dict_to_sorted_tuples({'x': 2, 'b': 2, 'a': 1, 'c': 3}, True)
[('a', 1), ('b', 2), ('x', 2), ('c', 3)]
"""
raise NotImplementedError("Complete this function.")dict_filter_by_values.py
Download dict_filter_by_values.py.
Listing 13 shows the contents of dict_filter_by_values.py.
dict_filter_by_values.py
def filter_student_data(
student_list: list[dict[str, str | int]],
filter_dict: dict[str, str | int]
) -> list[dict[str, str | int]]:
"""
Filter a list of student data dictionaries based on criteria specified
in a filter dictionary.
Parameters
----------
student_list : list[dict[str, str | int]]
A list of dictionaries, each representing a student's data.
filter_dict : dict[str, str | int]
A dictionary with criteria used to filter the student data.
Each key-value pair represents a field and the value to filter by.
Returns
-------
list[dict[str, str | int]]
A list of dictionaries, each representing a student's data that
matches the criteria in the filter dictionary.
Examples
--------
>>> students = [
... {"name": "Alice", "age": 25, "major": "Engineering"},
... {"name": "Bob", "age": 22, "major": "Arts"},
... {"name": "Charlie", "age": 25, "major": "Engineering"}
... ]
>>> filter_dict = {"age": 25, "major": "Engineering"}
>>> filter_student_data(students, filter_dict)
[{'name': 'Alice', 'age': 25, 'major': 'Engineering'},
{'name': 'Charlie', 'age': 25, 'major': 'Engineering'}]
"""
raise NotImplementedError("Complete this function.")dict_graph_reachability.py
Download dict_graph_reachability.py.
Listing 14 shows the contents of dict_graph_reachability.py.
dict_graph_reachability.py
def find_reachable_cities(
distances: dict[str, dict[str, float]]
) -> dict[str, set]:
"""
Find all reachable cities from each city in a connectivity graph.
The graph is represented by a dictionary where each key is a city and its
value is a dictionary of directly connected cities and the distances to them.
TIP: Use the depth-first search (DFS) algorithm:
https://en.wikipedia.org/wiki/Depth-first_search
Parameters
----------
distances : dict[str, dict[str, float]]
A dictionary representing the connectivity graph. Each connected city
also appears as a key, with an empty dictionary if it has no outgoing
connections.
Returns
-------
dict[str, set]
A dictionary where each key is a city, and the value is a set of
cities that can be reached from that city. The set does not include
the city itself (i.e., the starting city).
Examples
--------
>>> distances = {
... 'CityA': {'CityB': 10, 'CityC': 20},
... 'CityB': {'CityC': 30},
... 'CityC': {'CityA': 40}
... }
>>> find_reachable_cities(distances)
{'CityA': {'CityB', 'CityC'}, 'CityB': {'CityA', 'CityC'}, 'CityC': {'CityB', 'CityA'}}
"""
raise NotImplementedError("Complete this function.")dict_of_feature_combinations.py
Download dict_of_feature_combinations.py.
Listing 15 shows the contents of dict_of_feature_combinations.py.
dict_of_feature_combinations.py
# TIP: Use `itertools.combinations` to get all possible combinations.
# See https://docs.python.org/3/library/itertools.html#itertools.combinations.
import itertools
# TIP: Use a defaultdict to simplify the code (no need to check if a key
# exists before appending to the list).
from collections import defaultdict
def organize_products_by_all_feature_combinations(
product_data: dict[str, set]
) -> dict[frozenset, list[str]]:
"""
Organize products based on all possible combinations of their features
from a dictionary.
Parameters
----------
product_data : dict[str, set]
A dictionary where each key is a product name and its value
is a set of features. Note: The keys of dictionaries must be immutable.
Therefore, `frozenset` is used instead of `set`.
See: https://docs.python.org/3/library/stdtypes.html#frozenset.
Returns
-------
dict[frozenset, list[str]]
A dictionary where keys are frozensets of feature combinations
and values are lists of product names.
Examples
--------
>>> product_data = {
... "Product 1": {"Eco-Friendly", "Durable"},
... "Product 2": {"Eco-Friendly", "Compact"},
... "Product 3": {"Durable", "Compact"}
... }
>>> organize_products_by_all_feature_combinations(product_data)
{
frozenset({'Eco-Friendly'}): ['Product 1', 'Product 2'],
frozenset({'Durable'}): ['Product 1', 'Product 3'],
frozenset({'Compact'}): ['Product 2', 'Product 3'],
frozenset({'Eco-Friendly', 'Durable'}): ['Product 1'],
frozenset({'Eco-Friendly', 'Compact'}): ['Product 2'],
frozenset({'Durable', 'Compact'}): ['Product 3']
}
"""
raise NotImplementedError("Complete this function.")