← CS50 Problem Sets

Problem 9

Lineup (more comfortable)

The same song request line, rebuilt with deque, plus a history stack behind a BACK command.

BACK walks up the stack: most recently played first.

Background

This is the more comfortable version of Lineup (less comfortable): same DJ booth, same song request line. If you haven’t done that yet, start there; this problem assumes you already have working ADD and PLAY commands, just rebuilt here with a different tool.

Two things are new. First, the lineup itself moves from a plain list to deque, the queue class built into Python’s collections module. Second, you’re adding a running history of everything that’s already played, so you can answer the question that always comes up at a dance: “wait, what was that song two songs ago?” History works backwards from the lineup: the answer you want first is the most recent song, then the one before that, and so on. Something that comes out most-recently-added-first instead of first-in-first-out is called a stack, and its two operations are push (add to the top) and pop (remove from the top).

Song request:

This shows the idea: the lineup itself behaves exactly like it did in Lineup, and Back walks backwards through what already played, most recent first. It doesn’t match your program’s exact commands or wording; see the specification below for those.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir lineup_more
cd lineup_more
code lineup_more.py

That creates a new folder called lineup_more, moves into it, and opens a new, empty file called lineup_more.py for you to edit.

Starter Code

Paste this into lineup_more.py to start from. enqueue and dequeue are already filled in for you this time, the same logic as Lineup, just working on a deque instead of a list. push and pop are the new parts, stubbed out with pass and doctest examples; run python3 -m doctest lineup_more.py from inside your lineup_more folder to check them.

main is left as a comment on purpose, same as always: the command loop is the actual point of this problem, and a docstring can’t check a loop the way it can check a pure function. Yes, that means rewriting the ADD/PLAY handling you already built in Lineup; this time it also has to handle BACK.

# Student Initials:
"""
Lineup (more comfortable)

Slug: porttack/cs50/problems/py/lineup_more
Doctests: python3 -m doctest lineup_more.py
"""

from collections import deque


CAPACITY = 5


def main():
    # Loop, prompting "Command: " each time, until the input is
    # "DONE". Same ADD and PLAY behavior as Lineup, plus BACK. On a
    # successful PLAY, also call push to add that song to history.
    # See the specification below for exactly what to print for each
    # case.
    pass


def enqueue(lineup, song):
    """
    Adds song to the back of lineup if there's room (fewer than
    CAPACITY songs already waiting). Returns True if song was added,
    False if lineup was already full and song was not added.

    >>> lineup = deque()
    >>> enqueue(lineup, "Sunroof")
    True
    >>> list(lineup)
    ['Sunroof']
    """
    if len(lineup) >= CAPACITY:
        return False
    lineup.append(song)
    return True


def dequeue(lineup):
    """
    Removes and returns the song at the front of lineup. Returns
    None, and leaves lineup unchanged, if lineup is empty.

    >>> lineup = deque(["Sunroof", "Flowers"])
    >>> dequeue(lineup)
    'Sunroof'
    >>> list(lineup)
    ['Flowers']
    """
    if not lineup:
        return None
    return lineup.popleft()


def push(history, song):
    """
    Adds song to the top of history, a plain list.

    >>> history = ["Anti-Hero"]
    >>> push(history, "Flowers")
    >>> history
    ['Anti-Hero', 'Flowers']
    """
    pass


def pop(history):
    """
    Removes and returns the song on top of history (the one played
    most recently). Returns None, and leaves history unchanged, if
    history is empty.

    >>> history = ["Anti-Hero", "Flowers"]
    >>> pop(history)
    'Flowers'
    >>> history
    ['Anti-Hero']
    >>> pop([])
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, lineup_more.py, that runs the song request line for the dance, same as Lineup, plus a history of what already played.

• Keep the lineup itself in a deque, starting empty. CAPACITY is already defined as 5. enqueue and dequeue are already implemented for you above.
• Keep a second collection, history, a plain list, also starting empty, for songs that have already played.
• Loop, prompting exactly "Command: " each time.
• If the input is exactly DONE, stop looping. Print nothing else.
• If the input starts with ADD followed by at least one more character, everything after that first space is the song title, spaces and all.
  • If the lineup has fewer than 5 songs waiting, call enqueue and print Added: <song>.
  • If the lineup is already full, print Lineup is full and don’t add the song.
• If the input is exactly PLAY:
  • If the lineup isn’t empty, call dequeue, print Now playing: <song>, and call push to add that same song to history.
  • If the lineup is empty, print Nothing to play.
• If the input is exactly BACK:
  • If history isn’t empty, call pop and print Last played: <song>.
  • If history is empty, print Nothing has played yet.
  • BACK only reports what already played; it never changes the lineup, and a song popped off history doesn’t go back on it.
• Anything else, a blank line, ADD with nothing after it, a misspelled command, lowercase input, prints Huh? and prompts again. Don’t crash on unexpected input.
• push and pop should never print anything or read input themselves. All the printing happens in main, based on what they return.

Usage

Your program should behave like the demo below.

$ python lineup_more.py
Command: ADD Anti-Hero
Added: Anti-Hero
Command: ADD Flowers
Added: Flowers
Command: PLAY
Now playing: Anti-Hero
Command: PLAY
Now playing: Flowers
Command: BACK
Last played: Flowers
Command: BACK
Last played: Anti-Hero
Command: BACK
Nothing has played yet
Command: PLAY
Nothing to play
Command: DONE

$ python lineup_more.py
Command: ADD A
Added: A
Command: ADD B
Added: B
Command: ADD C
Added: C
Command: ADD D
Added: D
Command: ADD E
Added: E
Command: ADD F
Lineup is full
Command: DONE

Hints

The Python docs for collections.deque are a solid reference if the note above left you curious: collections.deque. The hints below are specific to this problem.

Need a hint?

• main needs the same command-parsing shape as Lineup: "ADD Anti Hero".split(" ", 1) gives you ['ADD', 'Anti Hero'], and command.startswith("ADD ") (note the trailing space) is the cleanest way to check before splitting.
• An empty list is falsy, same as an empty deque: if history: is True only when there’s something in it. That’s the cleanest way to check before calling pop.
• Don’t reach for deque inside push/pop. history only ever grows and shrinks from one end, so a plain list’s .append() and .pop() (called with no argument, which removes from the end) are exactly what you want. See the note above the Usage section for why.
• push and pop don’t need try/except. They’re not parsing user input, just managing history and reporting back what happened, so a plain if covering the empty case is all pop needs, and push needs no check at all.

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Fill in push and pop with real code, and add one more >>> example of your own to each docstring covering a case not already shown. Both are pure enough to doctest cleanly, same as enqueue and dequeue above them. Don’t try to doctest main; a loop that reads input doesn’t fit the format.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Style and Submission

Run these one at a time, from inside your lineup_more folder.

Check your style:

style50 lineup_more.py

Check your correctness:

check50 porttack/cs50/problems/py/lineup_more

Submit your work:

submit50 porttack/cs50/problems/py/lineup_more

---

Glossary

• queue — A data structure where items come out in the same order they went in: first in, first out (FIFO). A line of people works the same way.
• enqueue — Adding an item to the back of a queue.
• dequeue — Removing and returning the item at the front of a queue.
• FIFO — “First in, first out.” The rule that makes a queue a queue: whatever’s been waiting longest comes out first.
• deque — Short for “double-ended queue,” and the name of the class in Python’s collections module built to add or remove items from either end quickly, no matter how long it gets.
• stack — A data structure where the most recently added item comes out first: last in, first out (LIFO). A stack of trays in a cafeteria works the same way; you take from the top, not the bottom.
• push — Adding an item to the top of a stack.
• pop — Removing and returning the item on top of a stack.
• LIFO — “Last in, first out.” The rule that makes a stack a stack, the opposite of a queue’s FIFO.