Module assignment: Python catalog with safe copies

Why this assignment

This assignment puts the four lessons of the module into one program. You will build a small book catalog as a linked list, which means every book is a node that refers to the next one. You will write __eq__ and __hash__ so that the catalog can count distinct books. You will reverse the list in place. You will take a deep copy so that a saved copy does not change when the live catalog changes.

Every part of the program depends on a rule from this module. If you remember that a copy of a reference is the same object, that a function must return a new head, and that a deep copy must copy each node, the assignment is mostly a matter of careful typing. If one of those rules is missing, the program prints the wrong line, and the examples show you which one.

Work through it in the order given. Each command adds one feature, and the checks in the middle of the lesson let you test a feature before you build on it.

The spec

A small library keeps its catalog in a singly linked list. Each node is a Book with a title (a single word with no spaces), a year (an integer), and a next reference, which is None at the end of the list. The front of the list is the most recently added book.

The program reads a number q on the first line, then q commands. It prints output only for the commands that have output. The table lists every command.

Three rules need care.

Two books are the same when their title and year both match. Two copies of Dune published in 1965 count as one distinct book, but a Dune from 1966 is a different book.

copy must be a deep copy. After copy, a rename or a reverse on the live catalog must not change the saved copy. A copy that points at the same nodes breaks this rule, and the examples catch it.

A copy of an empty catalog is still a copy. If copy runs when the catalog is empty, showcopy prints (empty), not no copy. The words no copy appear only before the first copy command.

Input and output examples

The first example uses every command that prints output. Study it before you write any code, and trace it by hand with a picture of the list.

Input:

11
add Dune 1965
add Emma 1815
add Dune 1965
show
count
copy
rename Dune Messiah
show
showcopy
reverse
show

Output:

Dune, Emma, Dune
2
Messiah, Emma, Dune
Dune, Emma, Dune
Dune, Emma, Messiah

Trace the first three add commands. After the first, the list is Dune. After the second, the list is Emma -> Dune, because Emma is now at the front. After the third, the list is Dune(1965) -> Emma -> Dune(1965). The first show prints the list from the front, so it prints Dune, Emma, Dune. The count command finds two distinct books, because the two Dune nodes are equal.

The copy command saves a separate chain of three new nodes. The rename command changes the front Dune, which is the most recent one, so the live list becomes Messiah, Emma, Dune. The saved copy still reads Dune, Emma, Dune, which is the showcopy output. The reverse command turns the live list around, so the last show prints Dune, Emma, Messiah.

The second example checks the edge cases. It uses an empty catalog and a missing title.

Input:

8
showcopy
show
rename Ghost Phantom
copy
add Ulysses 1922
count
showcopy
reverse

Output:

no copy
(empty)
no such book: Ghost
1
(empty)

The first showcopy prints no copy, because no copy exists yet. The show on the empty catalog prints (empty). The rename finds nothing, so it prints a message. The copy of the empty catalog saves an empty copy. After add Ulysses 1922, the live catalog has one book, but the saved copy is still empty, so the next showcopy prints (empty).

To test the examples, save each input in a file, such as example1.txt, and run python3 catalog.py < example1.txt in a terminal. The < sends the file to the program as standard input. Compare the output with the text above, line by line.

Requirements checklist

Tick each item when your program does it, and test it before you tick it.

• The program reads q, then exactly q commands from standard input.
• add pushes a new Book at the front, and the head is updated with the value that the function returns.
• show prints the list from front to back, with the separator , , and prints (empty) for an empty list.
• count uses a set and prints the number of distinct books.
• __eq__ and __hash__ compare only the title and the year.
• rename changes the first match from the front, and prints no such book: OLD when there is no match.
• reverse returns the new head, and the caller stores it.
• copy builds a deep copy, so no node in the saved copy is shared with the live list.
• showcopy prints no copy before the first copy, and prints the saved copy afterwards, even when that copy is empty.
• Your program passes both examples exactly, including the spaces and the line breaks.

Grading rubric

Your grade depends on how many of the features work across the examples and a set of hidden test inputs. The hidden tests use the same commands in different orders, with empty catalogs, missing titles and long lists.

A 60% solution builds the catalog with add, prints it with show, and handles (empty) correctly. Its count may be wrong, or it may raise an error on some commands. It usually fails the first example at the count line or the copy line, and the program prints the wrong number of lines.

An 80% solution runs every command and matches the first example exactly. Its copy shares nodes with the live list, which is the most common mistake. The example still prints Messiah, Emma, Dune for showcopy, not Dune, Emma, Dune, so this solution fails the example. It also fails the hidden tests that rename or reverse after a copy.

A 100% solution passes both examples and every hidden test. Its functions return the new head where the head can change, its __eq__ and __hash__ agree with each other, and its copy is deep. Its code is split into small functions, one for each job, so that a reader can see the commands in main at a glance.

Starter program

Save the starter below as catalog.py. Create a file empty.txt that holds the single line 0, then run python3 catalog.py < empty.txt. The starter runs, reads the count and prints nothing. Fill in the TODO lines, and test your work with the examples.

import sys
 
 
class Book:
    def __init__(self, title, year, next=None):
        self.title = title
        self.year = year
        self.next = next
 
    # TODO: deep_copy(), __eq__ and __hash__
 
 
def push_front(head, title, year):
    # TODO
    pass
 
# TODO: reverse, find_by_title, count_distinct and show
 
def main():
    tokens = sys.stdin.read().split()
    q = int(tokens[0])
    # TODO: read q commands and print the results
 
main()

Check your building blocks

Before you write main, check the two hardest parts on their own. The first program checks __eq__ and __hash__. Type nothing into the Input box.

Type nothing into the Input box for this program.

2
False
True

The set holds two books, because the two Dune copies are equal. The second line is False, because the years differ. The last line is True, because equal books must have equal hash values.

The second program checks the deep copy. Type nothing into the Input box.

Type nothing into the Input box for this program.

Dune Emma
Messiah Persuasion
False

The copy has new nodes, so changing its titles leaves the original alone. The last line is False, because the two second nodes are different objects. A shallow copy would print True on that line, and that is the test to remember.

Step-by-step hints

Try the step before a hint first, and read one hint at a time. Each hint names one feature.

Hint 1: adding at the front

push_front takes the current head and a new title and year, creates a Book whose next is the old head, and returns the new Book. In the loop of main, write head = push_front(head, title, year). If you forget the assignment, the new book is created and then lost.

Hint 2: printing the list

Start with cur = head, and move with cur = cur.next. Stop when cur is None. Put the separator between titles, not after the last one, so check cur.next is not None before you add , . Return the text from a function and print it in main, so the same function can print both the live list and the saved copy. Joining a list of titles with ", ".join(titles) does the separator for you.

Hint 3: reversing

Use the three-name loop from lesson 4. Inside the loop, save cur.next into a name before you change cur.next. The function returns prev, the new head. Remember to store the result in main, or the show after reverse prints the old order.

Hint 4: the deep copy

Use a head and a tail name. Each pass of the loop creates a new Book with the same title and year and None as its next. The first node becomes head. Each later node is attached with tail.next = node, and then tail moves to it. The copy must never use the existing node objects. The title is a string, and a string is safe to share, so it may be copied by reference.

Hint 5: eq and hash

Compare the year first, because it is a number, and then the titles with ==. Make __hash__ use the same two fields, with hash((self.title, self.year)). If the two methods use different fields, the set in count gives wrong answers.

Hint 6: rename and the first match

Walk the list from the head and stop at the first book whose title equals the old title. Change that book's title attribute. Do not create a new node, and do not move the book to the front. If the walk reaches None without a match, print the message.

Hint 7: the copy that does not exist yet

Use a boolean such as has_copy that becomes True after the first copy. A saved copy of an empty catalog is still a copy. Testing saved is None alone cannot tell the two cases apart, because an empty copy is also None.

Reference solution

Try the whole assignment before you read this. The solution is a complete program. Save it as catalog.py, run it on the first example's input, and check that the output matches the example exactly.

import sys
 
 
class Book:
    def __init__(self, title, year, next=None):
        self.title = title
        self.year = year
        self.next = next
 
    def __eq__(self, other):
        if self is other:
            return True
        if not isinstance(other, Book):
            return NotImplemented
        return self.year == other.year and self.title == other.title
 
    def __hash__(self):
        return hash((self.title, self.year))
 
    def deep_copy(self):
        head = None
        tail = None
        cur = self
        while cur is not None:
            node = Book(cur.title, cur.year)
            if head is None:
                head = node
            else:
                tail.next = node
            tail = node
            cur = cur.next
        return head
 
 
def push_front(head, title, year):
    return Book(title, year, head)
 
 
def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    return prev
 
 
def find_by_title(head, title):
    cur = head
    while cur is not None:
        if cur.title == title:
            return cur
        cur = cur.next
    return None
 
 
def count_distinct(head):
    seen = set()
    cur = head
    while cur is not None:
        seen.add(cur)
        cur = cur.next
    return len(seen)
 
 
def show(head):
    if head is None:
        return "(empty)"
    titles = []
    cur = head
    while cur is not None:
        titles.append(cur.title)
        cur = cur.next
    return ", ".join(titles)
 
 
def main():
    tokens = sys.stdin.read().split()
    pos = 0
    q = int(tokens[pos])
    pos += 1
    head = None
    saved = None
    has_copy = False
    out = []
    for _ in range(q):
        cmd = tokens[pos]
        pos += 1
        if cmd == "add":
            title = tokens[pos]
            year = int(tokens[pos + 1])
            pos += 2
            head = push_front(head, title, year)
        elif cmd == "rename":
            old_title = tokens[pos]
            new_title = tokens[pos + 1]
            pos += 2
            found = find_by_title(head, old_title)
            if found is None:
                out.append("no such book: " + old_title)
            else:
                found.title = new_title
        elif cmd == "reverse":
            head = reverse(head)
        elif cmd == "copy":
            saved = None if head is None else head.deep_copy()
            has_copy = True
        elif cmd == "show":
            out.append(show(head))
        elif cmd == "showcopy":
            out.append("no copy" if not has_copy else show(saved))
        elif cmd == "count":
            out.append(str(count_distinct(head)))
    sys.stdout.write("".join(line + "\n" for line in out))
 
 
main()

Extend it yourself

When the checklist is complete, add one command of your own, such as remove TITLE, which deletes the first book with that title. Deleting from a linked list means changing the next reference of the node before the one you delete. If the first book is the one to delete, the head changes, so the function must return the new head. Test the command on an empty list, on a list where the first book matches, and on a list where the last book matches. Those three cases cover the main edge cases, and they are the cases interviewers ask about.

Test your program before you submit

Examples are only two inputs, so the hidden tests will try more. Write your own input files that cover the cases most likely to break, and check each output by hand before you trust it. Good test inputs are short, so that you can trace them on paper.

Here are four inputs to try. For each one, write the expected output on paper first, then run your program and compare.

• A catalog with one book, then reverse, then show. The output should be the one title.
• Two copy commands with a change between them. The showcopy after the second copy must show the state at the second copy, not the first.
• rename on a title that appears three times. Only the first from the front should change.
• count after add of the same title and year twice, then add of the same title with a different year. The answer is 2.

If your output differs from your hand prediction, do not change the program at random. Trace the first line that differs, using the picture of the list, and find the command that changed the wrong node or reference. Most failures in this assignment come from a reference that was not stored after a function returned a new head, or from a copy that shares nodes with the list it came from.

What this module covered

• Names and objects live in different memory areas, and a name is a reference that leads to an object.
• None is an empty reference, and a check for it must come before an attribute is read from it.
• == compares content as the class defines it, and is compares identity. Every class that defines __eq__ needs __hash__ too.
• Python passes a copy of each reference, so a function that changes the head of a list must return the new head.
• An object is garbage when nothing reaches it, and a copy is deep only when every node is copied.