A document from MCS 275 Spring 2022, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2022 Homework 3 Solutions

  • Course Instructor: David Dumas
  • Solutions prepared by: Johnny Joyce and David Dumas

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 1 February 2022.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Resources you may consult

The course materials you may refer to for this homework are:

Point distribution

This homework is a bit lighter than usual, because I know you're busy with Project 1.

This homework assignment has a single problem, number 2. The grading breakdown is:

Points Item
2 Autograder
4 Problem 2
6 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc.. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

Problem 2: Debugging a write-once dictionary

Below you'll find code that defines a class WriteOnceDict that is a subclass of dict which doesn't allow values associated to existing keys to be changed, nor even for an attempt to be made. That is, if an instance d of WriteOnceDict already contains a key k, then

d[k] = value

will raise an exception.

In [3]:
class WriteOnceDict(dict):
    """
    Dictionary where an existing value cannot be changed.
    """
    def __setitem__(self,k,v):
        "Create new key `k` with value `v`; if `k` is already a key, raise ValueError"
        if k in self:
            raise ValueError("Attempt to change value associated to existing key {}.  This is not allowed by {}.".format(
                k,
                self.__class__.__name__ # name of this class, as a string
            ))
        else:
            super().__setitem__(k,v) # Call `dict` class setitem method
                                     # Note: can't just say self[k]=v since that will call this method!
                                     # Also, super() doesn't allow item assignment, e.g. super()[k]=v fails.

Here's an example of how WriteOnceDict works:

In [4]:
d = WriteOnceDict() # new empty WriteOnceDict container
d["a"] = "Hello!"   # create key
d[15] = True        # create key
In [5]:
d["a"] = "This will not work!" # Attempt to change value of existing key
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-9d6a17f7a530> in <module>
----> 1 d["a"] = "This will not work!" # Attempt to change value of existing key

<ipython-input-3-054cc750dc74> in __setitem__(self, k, v)
      6         "Create new key `k` with value `v`; if `k` is already a key, raise ValueError"
      7         if k in self:
----> 8             raise ValueError("Attempt to change value associated to existing key {}.  This is not allowed by {}.".format(
      9                 k,
     10                 self.__class__.__name__ # name of this class, as a string

ValueError: Attempt to change value associated to existing key a.  This is not allowed by WriteOnceDict.

Can't change? Challenge accepted.

Unfortunately, the WriteOnceDict class doesn't quite work as promised. The dict class has another method called update that can also change values associated to keys. Specifically, if you call d.update(e), where e is another dictionary, then every key-value pair from e will be copied into d, overwriting existing values if necessary. And in the implementation of WriteOnceDict above, the inherited update method can still be used to make changes. Here's an example:

In [6]:
d = WriteOnceDict() # new empty WriteOnceDict container
d["asdf"] = "I should not change"
d.update( {"asdf":"And yet, here we are."} ) # No error!  It makes changes despite "write once" claim
In [7]:
# Let's check that the value associated to "asdf" has actually changed
d["asdf"]
Out[7]:
'And yet, here we are.'

Fix WriteOnceDict so you can't change values with .update(...) either

Take the code for WriteOnceDict above, copy it into a file hwk3prob2.py and fix the issue described above by adding an update method. This method should expect a single dictionary as its argument, and should copy the key-value pairs into self, but refuse to modify any existing keys while doing so. Below you'll find code showing the expected behavior of your revised WriteOnceDict class.

In [ ]:
# Demo of the desired behavior after your changes
d = WriteOnceDict()
d["asdf"] = "I should not change"
d.update( {"asdf":"And yet, here we are."} ) # Now, this line will raise ValueError!
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-57-454d90a0c660> in <module>
      2 d = WriteOnceDict()
      3 d["asdf"] = "I should not change"
----> 4 d.update( {"asdf":"And yet, here we are."} ) # Now, this line will raise ValueError!

[ ... part of output redacted because it shows the solution ... ]

ValueError: Attempt to change value associated to existing key asdf.  This is not allowed by WriteOnceDict.

Solution

Note the new method update() below.

In [8]:
class WriteOnceDict(dict):
    """
    Dictionary where an existing value cannot be changed.
    """
    def __setitem__(self,k,v):
        "Create new key `k` with value `v`; if `k` is already a key, raise ValueError"
        if k in self:
            raise ValueError("Attempt to change value associated to existing key {}.  This is not allowed by {}.".format(
                k,
                self.__class__.__name__ # name of this class, as a string
            ))
        else:
            super().__setitem__(k,v) # Call `dict` class setitem method
                                     # Note: can't just say self[k]=v since that will call this method!
                                     # Also, super() doesn't allow item assignment, e.g. super()[k]=v fails.

    def update(self, other):
        """Add key-value pairs from `other` to this dictionary, raising ValueError if any of those
        keys already exist"""
        for key in other:
            self[key] = other  # calls our __setitem__ method above, hence won't overwrite a key

Remarks:

  1. It is perhaps a bit surprising that dict.update does not call dict.__setitem__ itself. (If it did, then we wouldn't need to make any changes to get WriteOnceDict to work.)
  2. You could also add the logic to detect and report an attempt to overwrite a key to update, but the solution above has the advantage that the error message only appears in one place (hence is easier to change if needed).
In [9]:
d = WriteOnceDict() # new empty WriteOnceDict container
d["asdf"] = "I should not change"
d.update( {"asdf":"This attempt to change will be in vain."} ) # This line should now give us an error (which we want!)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-9-5e90f8720180> in <module>
      1 d = WriteOnceDict() # new empty WriteOnceDict container
      2 d["asdf"] = "I should not change"
----> 3 d.update( {"asdf":"This attempt to change will be in vain."} ) # This line should now give us an error (which we want!)

<ipython-input-8-a72cebf96b8b> in update(self, other)
     19         keys already exist"""
     20         for key in other:
---> 21             self[key] = other  # calls our __setitem__ method above, hence won't overwrite a key

<ipython-input-8-a72cebf96b8b> in __setitem__(self, k, v)
      6         "Create new key `k` with value `v`; if `k` is already a key, raise ValueError"
      7         if k in self:
----> 8             raise ValueError("Attempt to change value associated to existing key {}.  This is not allowed by {}.".format(
      9                 k,
     10                 self.__class__.__name__ # name of this class, as a string

ValueError: Attempt to change value associated to existing key asdf.  This is not allowed by WriteOnceDict.

Revision history

  • 2022-02-03 Initial publication of solutions