Classwork 1

Here's a nice data-structures review assignment to make sure that everyone is comfortable with the essentials for this course!

This is a rare individual Classwork exercise just to make sure everyone is set up!

In particular, this exercise will make sure you:

Understand all of the course's policies and tools that we'll be using
Have your Python development environment set up
Review all necessary Python and Data Structures concepts to succeed in this class

Solution Skeleton

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

PostCommit

Included in the skeleton are:

review_exercises.py containing the skeletons of all exercises you'll need for the programmatic component of this classwork. Read on for more specifications on what to do herein.
review_tests.py to validate your solutions to the review exercises. These will serve as a checklist for when you've successfully completed a component!
mypy.ini, pytest.ini configuration files for mypy, pytest respectively. Do not change these!
.gitignore a set of patterns for git to avoid committing. You may modify this file if your commit attempts to add any project files to the repo (e.g., VSCode .project files or pycache folders, which should not be submitted).

Intro and Review

Note: please read this section carefully -- to get full credit for this assignment, there are some components both within and outside of the provided skeleton above!

Some Light Reading

Make sure you're apprised of all of the class' mechanics and policies!

Read through the class' syllabus.

Course Syllabus
Read through the CMSI Academic Honesty slides:

LMU CMSI Academic Honesty

Much Ado About You

Let's get to know each other a bit! Especially because...

This class will have a variety of classwork activities that can be completed in teams of up to 3 people; you are welcome to work alone or seek a group if you don't have one in mind already. Groups are fluid: you may always change or leave groups between assignments at will!

On Brightspace, under the class' Discussion tab, you'll find a forum Topic for Introductions. Make a new Thread here with the following information:

Required: List your name in the Thread title, any nicknames or pronunciation you want in the thread itself, any background information you'd like me and your classmates to know about you, and what your interests are in computer science.
Optional: feel free to also include your picture / pictures of pets or other important parts of your life, hometown, hobbies, if you're working on or want to work on side projects with anyone in the class, etc. just keep everything appropriate and polite.

An example post from yours truly has been made on the forum for your illustrative pleasure.

Remembering the Taste of Py

If you are already familiar with Python Development Environment, Git, Dependencies like mypy, pytest and Python style, you may skip this task--but be warned that you will be graded on all of the above!

Note: All of the following setup guides are available as references in the course page's Materials tab!

Let's make sure you're ready to hit the ground running with the Python development in this course!

Make sure you understand how to use Git + GitHub (which will be employed in all assignments on the course):

PostCommit
Read through the Python Development Environment Setup guide and install an IDE or setup a new workspace for this course.

Python Development Setup
Read through the minimal Python programming style expectations for this class (though know that this is an *additive* guide to be included atop all of the good style habits you've learned from previous courses):

Python Style Guide
Although many of you may be familiar with dynamically typed Python, this course will push you to think about types and data structures very carefully and instead uses statically typed Python, as through the mypy syntax.

A later part of this introduction exercise will walk you through more of this paradigm, but you should first acquaint yourself with the mypy documentation.

Read the "Getting started", "Type hints cheat sheet", and "Built-in types" pages located at the following link (about a 10-15 minute read):

mypy Docs

No Lax Lexicons

One of the easiest ways to prepare for the coming semester is making sure that you understand some important vocabulary! Make sure you recall all of the following and look up anything you've forgotten from your prerequisite classes! (The checkboxes don't do anything and are just to help you tick off what you recall or don't)

For anything that looks unfamiliar, feel free to stop by TA or Professor office hours for review -- the first TA recitation will also review some of this!

Data Structures vs. Data Types

Classes vs. Objects

Attributes in Python classes and the self keyword

Functions vs. Methods vs. Static Methods

Parameters vs. Arguments

Overriding Methods, esp. __eq__, __hash__, __lt__, __str__

References and Aliasing vs. Values and Literals

Asymptotic Runtime Analysis and Big-O Notation

Property vs. Identity Equivalence

Data Types: Lists, Sets, Dictionaries/Maps

Linked vs. Array Lists

Unbounded Trees vs. Binary Trees vs. Binary Search Trees

Hash Table Properties, viz., hash functions and collisions

Hash vs. Tree Sets + Maps

FILO Stacks vs. FIFO Queues

Priority Queues

Test-driven Development, Unit Tests, Assert Statements

Tutorials

[Optional] Need a refresher on some Python and data structures topics? Take a look at a few video tutorials below! They contain everything you'll need for the exercises that follow.

Classes and Mypy Typing

Equivalence

Hashing

Priority

Specifications

	GenAI use for the entirety of this assignment is BANNED for code production as it will shortcut your learning and generalizable skills (besides, there's not much code to write) though is always OK for understanding error messages, interpreting skeleton code, etc. as outlined in the syllabus.

A Link(ed-List) to the Past

Finally, time for a little Python and Data Structures review! Head on over to the PostCommit assignment linked in the Solution Skeleton above.

Note: even if you had Data Structures in a language other than Python, most of the same concepts will apply to this class!

Warmup

Let's start with a simple function, is_sublist as defined below, with a truly horrendous solution that should already throw some red flags

  def is_sublist(list1, list2):
      """
      Returns a bool designating whether or not all ints in list1 also appear
      in list2
      
      Parameters:
          list1 (list[int]):
              A list of ints for whom membership is being checked against list2
          list2 (list[int]):
              A list of ints against which list1's members are being checked
      
      Returns:
          bool:
              True if all of list1's ints are also in list2 without needing the
              reverse to be true
          
      Examples:
          is_sublist([1, 3, 2, 1, 3], [1, 2, 3]) => True
          is_sublist([1, 3, 2, 1, 3], [1, 2]) => False
      """
      # [!] Warning: this method is implemented VERY POORLY at the moment
      for item1 in list1:
          contained = False
          for item2 in list2:
              if item1 == item2:
                  contained = True
                  break
          if not contained: return False
      return True

There are a few things that we need to fix above.

Missing Type Hints: If we navigate into the folder containing review_exercises.py and execute the mypy type checker via the command mypy review_exercises.py, we'll notice a couple of errors complaining that error: Function is missing a type annotation.

This is because, although we are specifying the types of parameters and the return of the is_sublist function in the docstring, we have yet to provide type hints to the function signature that will allow static type checking for more robust code.

To fix this:
- Add the type hints to the function signature, specifying the parameter and return types as given in the docstring. For review of this syntax, see the reading materials and video above.
- After successfully completing the above, if you re-run mypy review_exercises.py, there will now be only 1 error (that you'll fix in the next exercise) instead of 2 -- progress!
Inefficient Solution: At present, the implementation of is_sublist has quadratic complexity: \(O(n^2)\) for input lists of size \(n\).

To witness the effects of this inefficient approach, in the terminal (while in the project directory), execute the pytest -k "test_is_sublist" command, which will run the unit tests in review_tests.py that test this particular method: test_is_sublist_basic will pass because the current implementation *does* provide the proper outputs, but test_is_sublist_efficiency will fail because it does not finish in a tractable amount of time (1s timeout).

To fix this:
- Modify the implementation of the is_sublist method so that the runtime efficiency is linear, \(O(n)\).
  
  Hint: the real inefficiency is from how the current implementation performs membership checks for items in list1 that are also in list2. A better data structure choice *that is good at membership checks* will improve performance.
- Once you've implemented your changes, rerun pytest -k "test_is_sublist". You can continue when both tests pass!
- Once both tests are passing and you've added your type hints, make a Git commit and then progress to the next section.
Warning: make sure you've installed the pytest-timeout package before testing, otherwise your tests may appear to pass when they shouldn't! Simply: pip install pytest-timeout

The Return of Forneymon

Help stub the Forneymon class, the prototype for the hit new collectible pocket monster game that will in no way shape or form encounter copyright infringement from a certain Nintendo franchise.

In particular, we have the following small stub of a class consisting of 3 attributes that we'll use to get a (very) minimum viable product.

  class Forneymon:
      """
      Skeleton class outline for hit new blockbuster game: Forneymon.
  
      Attributes:
          _name (str):
              The Forneymon's name like "Burneymon" or "Dampymon"
          _health (int):
              The Forneymon's remaining hit points
          _friends (set["Forneymon"]):
              A set of Forneymon references that point to other Forneymon with
              whom this one is friends
      """
      
      def __init__(self, name, health, friends):
          # ...docstring omitted for brevity...
          # FIXME: Add type hints to the attributes of the Forneymon class
          self._name = name
          self._health = health
          self._friends = friends
      
      # other methods omitted

We've got a long way to go from the above, but let's start with some good house-keeping by fleshing out some of the methods and fixing some of what we have from the above, located in the same file: review_exercises.py.

Missing Attribute Types: Gotta add some type hints to the attributes of our Forneymon class and its constructor, just like in the is_sublist method! The types are already given in the docstring, it's up to you to add the syntax for the type hints where appropriate.

Recall: attributes are variables that belong to an instance / object of a class. Internal to a class' methods, attributes are accessed via the syntax self.attr_name.
- If you again try the following command in the terminal, you'll see the last complaint that mypy offers for the missing type declarations: mypy review_exercises.py
- Add your type hints to the (1) Forneymon constructor's parameters (i.e., __init__ method) and (2) to the attributes declared within. The syntax for declaring an attribute's type in the constructor is: attr_name: attr_type = attr_value
- Re-run mypy review_exercises.py in the terminal and... look at that! Everything's resolved! In fact, if you now run mypy . (i.e., check mypy against all files in the current directory) you should see all green.
Override __eq__: what should happen when we compare two Forneymon like fm1 == fm2? I.e., what does it mean for two Forneymon to be considered "equal" and what should we expect the == operator to do?

Recall from data structures that there is a difference between property vs. identity equivalence between objects: property equivalence means that two objects can be considered equal if they share equivalent attributes whereas identity equivalence means that they are considered equal if they are the same object in memory, regardless of whether or not their attributes are equivalent.

For our project, we want Forneymon to be considered property equivalent if they have the same _name, _health, though they may have different _friends.

This demands that we override the __eq__(self, other) method that is called any time a Forneymon is compared to some other thing using the == operator. If a class does NOT override the __eq__ method, it uses identity equivalence by default.

The following unit test demonstrates what we want to happen:
```
  def test_forneymon_equal(self) -> None:
      fm1 = Forneymon("Dampymon", 42, set())
      fm2 = Forneymon("Dampymon", 42, set())
      fm3 = Forneymon("Dampymon", 24, set())
      fm4 = Forneymon("Zappymon", 42, set())
      equal_err = "[X] Ensure that your equal method properly checks for the Forneymon type and then compares attributes."
      self.assertEqual(fm1, fm2, equal_err)
      self.assertNotEqual(fm1, fm3, equal_err)
      self.assertNotEqual(fm1, fm4, equal_err)
      self.assertNotEqual(fm1, "poop", equal_err)
```
Note from the above: self.assertEqual(fm1, fm2, equal_err) ensures that fm1 and fm2 are considered equal because they share the same name and health. The same is true for fm1 and fm5 even though they have different sets of friends.

Lastly, note that a fully-functional __eq__(self, other) override should account for other (the thing being compared) being of any type; we will always return False if a Forneymon is compared to anything that isn't another Forneymon. You can use the isinstance(other, Forneymon) builtin method to check for this.

Given the above, and because an equivalence test will always return a bool, the full method signature will look like: def __eq__(self, other: Any) -> bool:

Once you implement the above, run pytest -k test_forneymon_equal in your project folder and note that the test_forneymon_equal should now pass!
Override __hash__: remember Hash Tables? Well, turns out that they're used to implement Python set()s, which are really important data structures to make use of!

Recall: in order to store items in a hash table, those items must be hashable, i.e., define a __hash__(self) method that provides a semi-unique integer value for the object based on the attributes used to test equivalence (i.e., in the __eq__ method above). A hash function tells the hash table the index of its buckets the item will "hash" into.

Before you make any changes, the following unit test will not be happy:
```
  def test_forneymon_hash(self) -> None:
      fm_collection = set()
      fm1 = Forneymon("Dampymon", 42, set())
      fm2 = Forneymon("Dampymon", 42, {fm1})
      fm3 = Forneymon("Dampymon", 24, set())
      hash_err = "[X] Ensure that your __hash__ method hashes only the _name and _health attributes."
      fm_collection.add(fm1)
      fm_collection.add(fm2)
      self.assertEqual(1, len(fm_collection), hash_err)
      fm_collection.add(fm3)
      self.assertEqual(2, len(fm_collection), hash_err)
      
      # The hashing allows you to also store Forneymon in sets, as is expected for the friends
      # attribute, which we can now check that the equas method ignores
      equal_err = "[X] Ensure that your equal method properly checks for the Forneymon type and then compares attributes."
      fm4 = Forneymon("Dampymon", 42, {fm1})
      fm5 = Forneymon("Dampymon", 42, {fm2})
      self.assertEqual(fm2, fm4, equal_err)
      self.assertEqual(fm1, fm4, equal_err)
      self.assertNotEqual(fm3, fm4, equal_err)
```
As such, we need to:
- Override the def __hash__(self) -> int method in the Forneymon class
- Since our __eq__ method compares the _name, _health attributes for equivalence, our hash method must also use these attributes to return a hash value.
- Luckily, there's a hash function builtin that we can use to do this work for us, of the format: hash((self.attr1, self.attr2)) (note that to hash multiple attributes, the hash function accepts a tuple containing each). Just choose the correct attributes to hash in this syntax and return them -- one line solution!
Once you implement the above, run pytest -k test_forneymon_hash in your project folder and note that the test_forneymon_hash should now pass!
Fixing _friends: Note the _friends attribute that our Forneymon have, which is apparently some effort from the higher-ups to make a Forneymon social-network down the line because that's exactly what the world needs right now: another social network.

Notably: _friends is a set["Forneymon"], i.e. a set containing references to other Forneymon with whom the current one is friends.

The problem: note the line in the constructor that assigns the attribute self._friends to the argument friends.
```
  def __init__(self, name, health, friends):
      self._name = name
      self._health = health
      # Problem below:
      self._friends = friends
```
Recall: this is a referencing problem called aliasing in which the argument friends and the attribute self._friends are references that point to the same set in memory.

Aliasing can make for very buggy and unsecure code, because, as we see in the following unit test, fm_collection is a set of Forneymon that, if modified, would also modify the _friends set of fm3 outside of the control of the Forneymon class (and vice versa). Not good!
```
  def test_forneymon_friends(self) -> None:
      fm_collection: set["Forneymon"] = set()
      fm1 = Forneymon("Dampymon", 42, set())
      fm2 = Forneymon("Zappymon", 42, {fm1})
      fm_collection.add(fm1)
      fm_collection.add(fm2)
      fm3 = Forneymon("Friendimon", 101, fm_collection)
      fm3.lose_friend(fm2)
      aliasing_err = "[X] Ensure that your _friends attribute is not an alias of the constructor's argument."
      self.assertEqual(2, len(fm_collection), aliasing_err)
      self.assertIn(fm1, fm_collection, aliasing_err)
      self.assertIn(fm2, fm_collection, aliasing_err)
      self.assertIn(fm1, fm3.get_friends(), aliasing_err)
      self.assertEqual(1, len(fm3.get_friends()), aliasing_err)
```
The solution is simple:
- The copy.deepcopy(some_object) method will return a NEW object with all of the same data as some_object, which can be used to avoid aliasing.
- Use this method in the Forneymon's __init__ constructor to avoid the aliasing issue on the _friends attribute.
Once you implement the above, run pytest -k test_forneymon_friends in your project folder and note that the test_forneymon_friends should now pass!
Override __lt__: plainly, as with any game involving Pokemon-adjacent creatures, they'll be locked in some pseudo-humane combat for the entertainment of millions of children, but here at Forneymon, we take good medical care of our Forneymon and want to develop a Triage system where Forneymon who are most injured can be treated sooner than the others.

This endeavor represents a task in which we can say that certain Forneymon are prioritized/ordered over others based on how much _health they have remaining, which suggests a companion data structure...

Recall: A priority queue is a data structure implemented using a heap that is good for retrieving stored orderable objects in order of highest-to-lowest priority.

Ideally, we'd like behavior like in the following unit test to be accomplished, where 3 Forneymon enter into a Priority Queue of Forneymon named fm_triage with various amounts of health, but when we retrieve them using the priority queue's get() method, we'd expect to get them in order of least-to-greatest health (i.e., highest-to-lowest priority).
```
  def test_forneymon_triage(self) -> None:
      fm1 = Forneymon("Ouch", 3, set())
      fm2 = Forneymon("Im", 1, set())
      fm3 = Forneymon("Hurt", 2, set())
      compare_err = "[X] Ensure that your __lt__ method compares the Forneymon's _health attributes."
      fm_triage: "queue.PriorityQueue[Forneymon]" = queue.PriorityQueue()
      for fm in [fm1, fm2, fm3]: fm_triage.put(fm)
      self.assertEqual(fm2, fm_triage.get(), compare_err)
      self.assertEqual(fm3, fm_triage.get(), compare_err)
      self.assertEqual(fm1, fm_triage.get(), compare_err)
```
The problem: in order to store Forneymon in a Priority Queue, we have to specify how they should be ranked, which can be done quite easily!
- Overriding the def __lt__(self, other: "Forneymon") -> bool method defines how one Forneymon should be prioritized vs. another (__lt__ here standing for "less than", which returns True if the current Forneymon should be considered "less than" another by ranking). This can be used to rank on any attributes, e.g., by return self.attr1 < other.attr1.
- One bit of trivia: priority queues are, by default, implemented using a min-heap, which, if you recall from data structures, means that the highest priority item at the root of the heap is actually the object ranked "least" by the __lt__ method.
- As such, with the hints above, implement the __lt__ method comparing the current Forneymon's _health to the other's.
Once you implement the above, run pytest -k test_forneymon_triage in your project folder and note that the test_forneymon_triage should now pass!
Override __str__: Sometimes, for debugging or other purposes, it's nice to have a convenient way to "print out" a custom object like a Forneymon, e.g., saying print(some_forneymon).

However, when we supply an object of type Forneymon where a str is expected (i.e., to the print method), Python will be unhappy.

Luckily, the fix is simple: to define a so-called "to string" method that defines how an object is to be converted into some string representation.

Recall: the __str__(self) method can be used to convert an object into a string in some formatted way, usually as a function of one or more of its attributes.

For our purposes, we'll start just by having our Forneymon repeat their name twice for the implementation of their __str__ method, satisfying the following simple unit test:
```
  def test_forneymon_name(self) -> None:
      fm1 = Forneymon("Doublemon", 3, set())
      self.assertEqual("DoublemonDoublemon", str(fm1))
```
Namely, when asked to be converted to a string through the syntax str(fm1), we return a string that is simply double its assigned name at construction; in the above case, this was the name "Doublemon"

To do so:
- Override the def __str__(self) -> str method so that we return a string that is simply the Forneymon's _name attribute repeated twice (hint: remember you can multiply strings in Python).
Once you implement the above, run pytest -k test_forneymon_name in your project folder and note that the test_forneymon_name should now pass!
Double Check! Whew! We're almost done, let's just verify that everything's working before we finish this exercise!
- Run mypy . in the project directory one last time to make sure that all of your type hints have been written correctly. If not, verify that your class attributes and overridden method signatures conform to their proper type hints as listed above.
- Run pytest to make sure that all of your unit tests are passing! You should see all green at this point.
Enjoy the sweet sweet dose of dopamine from seeing a clean and functional project. It never gets old, and you're now all set with the prereqs for this class (well, the big ones anyways!)

Signing a Few Things in Blood (i.e., a Git Commit)

Once you have completed the review, head on over to the README.md file to acknowledge several last items requiring your initials.

Most README files are in Markdown (.md) format, which is a handy language for generating quick documentation and will render on your repository page on GitHub. If you're unfamiliar, begin by reading a bit about Markdown here:

Markdown Quick Reference
Commit your final changes to the review_exercises.py and README.md files and then push to your GitHub repository to submit!

Notes & Hints

Classworks are *typically* group assignments, but this one is solo to make sure everyone is comfortable with their development environment before continuing.
Remember that you're always free to consult me by Slack, email, or office hours (as well as our helpful TAs!) if you get stuck!
Since the above are primarily syntax-related tasks, feel free to ask ChatGPT for help reviewing; here are some acceptable queries you might use to get unstuck:
- Show me an example of parameters vs. arguments in Python.
- How do I give type hints for attributes in a Python class constructor?
- How do I override the __eq__ method in Python?
- What does the __hash__ method do in Python?

Submission

You will be submitting your assignments through PostCommit!

What

Push your modified review_exercises.py and README.md to your GitHub repository and ensure that you've made your introduction on Brightspace.

How

To clone this assignment (if you need a refresher), consult the guide here:

GitHub Tutorial

To submit this assignment:

Place your name at the designated spot in README.md.
Simply push your final, submission copy to the GitHub repository associated with your account.