Skip to content

PA2: Magazine Collage

A store-bought card says what everyone else's card says. A collage card is all yours: flip through an old magazine, snip out the letters you need, and glue them down one by one, every letter a different size, color, and font. "Happy birthday!" has never looked so loud.

There is a catch, though, and anyone who has made one hits it eventually. Each letter on the page can be cut out once. If your message needs three es and the page has only two, you are stuck, and a capital M will not do for a small m.

In this PA, you write the scissors. Your code counts the letters on a page, then pastes up a message one character at a time, using a letter up each time it cuts one out, and leaving a _ gap wherever the page has run out. And then you write the tests that prove it handles the tricky cases.

This is one of the two PA2 options; do this one or Hot Letters, not both.

What you'll practice

  • Looping through a string one character at a time.
  • Counting letters in a dictionary: adding a key the first time you see it, and adding 1 to it after that.
  • Checking whether a key is in a dictionary before you look it up.
  • Building a new string one character at a time, and returning two results as a tuple.
  • Writing pytest tests with assert, for ordinary inputs and for the edge cases.

Get set up

Download both files and save them in the Week08 folder inside ~/CS149:

Open collage.py and look around. Both functions are already there, each with type hints and a docstring that says exactly what it takes and what it returns, and each body is just pass. Your job is to replace those pass lines with real code. Read each docstring all the way through, example included, before you start that function. The main block at the bottom is written for you; leave it alone.

Put your name and today's date in place of YOUR NAME and THE DATE at the top of both files. Gradescope checks.

Submit early to Gradescope

If you don't submit to Gradescope and get a nonzero score, you will receive a reflection grade of no higher than 15/30 points.

Upload both files, every time

Gradescope needs both files in every submission, or it gives you 0 points. If you haven't started your tests yet, upload the test file just as you downloaded it; your functions still get graded.

How cutting out works

Only letters get cut out. Spaces, digits, and punctuation are drawn in by hand, so a note can have as many of them as it likes, and they never count against the page. Python can tell you whether a character is a letter: char.isalpha() is True for "a" and "Q", and False for " ", "7", and "!".

Uppercase and lowercase are different letters, because they look different on the page. A T cut from a headline is no use for a t in the middle of a word.

Here is the note meet at noon cut from a page that says the moon is out tonight. That page has one e, no a, and plenty of m, t, n, and o:

Note m e e t (space) a t (space) n o o n
Pasted m e _ t _ t n o o n

The first e uses up the page's only e, so the second one is a gap. There is no a on the page at all. That gives me_t _t noon, with 2 letters missing.

Quick check: how many letters of Hi! can you cut from a page that says hi?

One. The i is there, but the page has only a lowercase h, and the note needs an H. The ! is drawn in by hand, so it doesn't count.

Part A: count the page with letter_counts

letter_counts(page) goes through the page one character at a time and counts each letter in a dictionary. Anything that is not a letter is skipped.

>>> letter_counts("Go, go!")
{'G': 1, 'o': 2, 'g': 1}
>>> letter_counts("a b, a!")
{'a': 2, 'b': 1}
>>> letter_counts("7 - 2")
{}
Predict it: what does letter_counts("Pie at 7 pm.") return?

{'P': 1, 'i': 1, 'e': 1, 'a': 1, 't': 1, 'p': 1, 'm': 1}. The capital P and the small p are separate keys, and the spaces, the 7, and the . are skipped.

Counting is the pattern from class

For each character that is a letter: if it is already a key in the dictionary, add 1 to it; otherwise set it to 1.

Part B: paste up the note with cut_out

cut_out(note, page) calls your letter_counts on the page, then builds the pasted note one character at a time, starting from an empty string. Each character of the note is one of three cases, in this order:

  1. It is not a letter: keep it as it is.
  2. The counts have one of it to spare (it is a key, and its count is more than 0): keep it, and take 1 off its count.
  3. Anything else: a _, and one more letter missing.

It returns a tuple of the pasted note and the number missing.

>>> cut_out("meet at noon", "the moon is out tonight")
('me_t _t noon', 2)
>>> cut_out("tea", "eat")
('tea', 0)
Your turn: what does cut_out("noon", "no") return?

('no__', 2). The page has one n and one o. The first n and o use them up, so the second o and the second n are gaps.

It's fine to change that dictionary

cut_out takes 1 off the counts every time it cuts out a letter. That is safe because letter_counts builds a new dictionary every time you call it, so nothing outside cut_out sees the change.

Trace it: what does cut_out("Run, now!", "RUN NOW") return?

('R__, ___!', 5). The page is all capitals, so only the R matches. The u, n, n, o, and w are lowercase in the note and missing from the page, and the comma, the space, and the ! are kept as they are.

Part C: prove it with test_collage.py

Open test_collage.py. It imports your two functions and has one test function for each, test_letter_counts and test_cut_out, with a docstring suggesting what to test. Replace each pass with at least three assert statements, each checking one call against an answer you worked out yourself:

def test_cut_out():
    assert cut_out("tea", "eat") == ("tea", 0)
    ...

Run your tests from the terminal, in your Week08 folder:

cd Week08
pytest

or click the beaker icon in VS Code's Testing view, as you did in the pytest lab.

Gradescope grades your tests in three ways:

  • They must pass on a correct collage.py. A test that fails there has a wrong expected value. Gradescope runs your tests against the correct solution here, not against your own code.
  • They must fail on a collage.py whose functions return nonsense, so every test has to check what a function returns.
  • They must catch bugs. Gradescope plants a mistake in a correct collage.py, one at a time, and at least one of your tests has to fail on each. The mistakes are the kind people really make in this PA.

Where the bugs hide

The easy cases (a note that is all there, an empty page) are worth a test, but almost any code gets them right. The bugs hide in the cases from this page: punctuation and spaces, and a note that needs a letter more times than the page has it. For every function, ask yourself, "What is the case most likely to go wrong?" and write that test.

Test it before you submit

Run pytest after every change. If a test fails, read the message: it shows the value your function returned next to the one your test expected. Before you decide the function is wrong, work out the answer by hand once more, because sometimes the test is the one with the mistake.

Until cut_out works, running collage.py stops with a TypeError from the main block. That is expected, not a sign you broke something. When both functions work, press Run, and the main block pastes up three messages from one page:

Page: Win BIG at the county fair! Pie contest Sat, 7 pm. Free entry.
_eet me at noon.  (1 missing)
See you at the fair!  (0 missing)
_han_s a ton, Sam!  (2 missing)

Look closely: the page has m and t, but no M and no T, and no k at all. Each message starts from a fresh copy of the page, so the second one can use the same letters as the first. Before you submit, work out the third note on paper, and check that your output agrees.

Rules

Only what we have covered

Gradescope rejects a collage.py that uses any of these:

  • a while loop (Week 9)
  • slicing, like note[1:3] (Week 10)
  • a comprehension or a lambda (Week 11)
  • count(), index(), find(), or replace()
  • the dictionary methods get(), setdefault(), keys(), values(), and items() (Week 11)
  • any import, such as Counter from collections

Each of these would do a loop's job for you, and writing the loop yourself is what this PA is for. isalpha() is fine, since it only answers a question about one character. Your test file may use anything.

Submission

Submit both collage.py and test_collage.py to the Gradescope assignment PA2b Magazine Collage, then commit and push your Week08 folder (how). Gradescope also checks that your name and the date are in both docstrings, and that ruff check is clean on both files. Remember to upload both files every time, even if test_collage.py is still the starter version.

Do this option or Hot Letters, not both.

Where the idea comes from

Cut-and-paste lettering has been a scrapbooking and zine favorite for decades, and "can you spell this message from the letters in that text?" is a classic programming puzzle about counting. This PA is new for this semester.