Chapter 9: Sets and Dictionaries (Solutions to Even-Numbered Exercises)

Question 2

Note that the question is ambiguous: it does not specify whether each male and female is to be used once, or whether every male is to be paired with every female. This solution assumes the former.

def mating_pairs(males, females):
    '''Return matched pairs from the input sets.  Assumes that
    the input sets are of the same size.'''

    result = set()
    while males and females:
        result.add((males.pop(), females.pop()))
    return result

Question 4

TODO: diagram

Question 6

def find_least_likely(probs):
    '''Return the particle that is least likely to be observed, or
    None if no particles have been observed at all.'''

    least_name = None
    least_prob = None
    for key in probs:
        # If this is the first particle seen, it must have the lowest
        # probability.
        if least_name is None:
            least_name = key
            least_prob = probs[key]

        # Otherwise, compare this particle's probability with the
        # current least.
        elif probs[key] < least_prob:
            least_name = key
            least_prob = probs[key]

    return least_name

Note that the two tests inside the loop can be combined as:

if (least_name is None) or (probs[key] < least_prob):
    least_name = key
    least_prob = probs[key]

The advantage of this is that the code to reset
least_name and least_prob isn't duplicated.
The disadvantage is that the condition is harder to read.

Question 8

def fetch_and_set(dictionary, key, new_value):
    '''Replace the value associated with key, returning the old
    value, or raise a KeyError if the key is not present.'''

    if key not in dictionary:
        raise KeyError('Unable to replace value for nonexistent key')

    old_value = dictionary[key]
    dictionary[key] = new_value
    return old_value


Question 10

def dict_intersect(left, right):
    '''Return a dictionary containing the key/value pairs common
    to the two input dictionaries.'''

    result = {}
    for key in left:
        if (key in right) and (left[key] == right[key]):
            result[key] = left[key]

    return result


Question 12

def db_consistent(dict_of_dicts):
    '''Check whether all the subdictionaries in a dictionary of
    dictionaries have the same keys.'''

    # If the dictionary of dictionaries is empty, there are no
    # inconsistent keys, so return True.
    if not dict_of_dicts:
        return True

    # Get one of the sub-dictionaries and use its keys as a
    # reference set.
    outer_keys = dict_of_dicts.keys()
    arbitrary_key = outer_keys[0]
    inner_dict = dict_of_dicts[arbitrary_key]
    inner_keys = inner_dict.keys()
    reference_set = set(inner_keys)

    # Now check all of the inner dictionaries' keys against the keys
    # in the reference set.  Note that this method checks the
    # dictionary used for the reference set against itself.  Figuring
    # out how to avoid this is left as a further exercise.
    for outer_key in dict_of_dicts:
        inner_dict = dict_of_dict[outer_key]
        inner_keys = set(inner_dict.keys())
        if inner_keys != reference_set:
            return False

    # No inconsistencies found, so everything is OK.
    return True


Question 14

a)

def sparse_add(left, right):
    '''Add two sparse vectors.'''

    # Result contains everything in left.
    result = left.copy()

    # Now add contents of right.
    for key in right:
        if key in result:
            result[key] = result[key] + right[key]
        else:
            result[key] = right[key]

    return result


b)

def sparse_dot(left, right):
    '''Calculate the dot product of two sparse vectors.'''

    result = 0
    for key in left:
        if key in right:
            result += left[key] * right[key]

    return result


c) Is the length of a sparse vector the number of (non-zero)
entries, or one more than largest index?  For example, should the
"length" of {0:1, 6:3} be 2 or 7?