Skip to content

PA3: Gift Swap

Every December, offices, dorm floors, and families all over the world run the same little ritual. Everyone's name goes on a slip of paper, the slips go in a hat, and each person draws one: that's who you buy a gift for. Nobody knows who has them, so the gift is a surprise.

The rules are simple: you can't buy for yourself, and nobody gets two gifts. But anyone who has run one knows the snag. If the slips go round in order, the last person can find that the only slip left in the hat is their own, and then everyone has to put their slip back and draw again.

In this PA, you run the hat. Your code signs everyone up, draws a name for each giver until it gets one it can use, reads everyone's wish from a file, and writes a card for every giver.

This is one of the two PA3 options; do this one or Trivia Night, not both.

What you'll practice

  • Writing a while loop that repeats until a random event happens, and making sure it can end.
  • Writing a while loop that asks for input again until the input is valid.
  • Naming the three parts of a loop: initialization, condition, and update.
  • Using a set to keep track of what you have already seen.
  • Reading a file one line at a time, and writing a new one (Week 10).

Get set up

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

Open gift_swap.py and look around. All four 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 the file. 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. It's one assignment for the whole PA. Submit Part A as soon as it works; Gradescope grades each part separately, so the parts you haven't started don't stop it.

Part A: draw a name with draw_name

draw_name(giver, names, taken) pulls one slip out of the hat for giver. It draws with random.choice(names), which picks one item of the list at random. If the slip is the giver's own name, or a name somebody else already drew (it is in the set taken), the slip goes back and it draws again. How many draws will that take? Nobody knows ahead of time, and that is exactly the job a while loop is for.

>>> draw_name("Ana", ["Ana", "Ben", "Cal"], {"Cal"})
'Ben'
>>> draw_name("Ana", ["Ana", "Ben", "Cal"], set())     # Ben or Cal, at random
'Cal'

There is one trap. If no slip in the hat is one the giver can use, drawing again will never help, and a while loop that waits for a usable slip runs forever. So before it draws at all, draw_name checks with a for loop whether any name in the list is usable, and if none is, it returns "" without drawing.

Predict it: what does draw_name("Cal", ["Ana", "Ben", "Cal"], {"Ana"}) return?

'Ben', every time. Cal can't draw Cal, and Ana is already taken, so the loop keeps drawing until it gets Ben.

Trace it: name the three parts of the drawing loop

The initialization is the first draw, before the loop. The condition is "the name is the giver, or it is already taken". The update is drawing again, inside the loop. If you leave out the update, the condition never changes, and the loop runs forever on the first bad draw.

Check it yourself

For now, add a few print(draw_name(...)) calls at the top of the main block, right under the if __name__ == "__main__": line, and run the file a few times: the second example should change between Ben and Cal, and the first should never change. Then take those lines out again.

Part B: sign everyone up with sign_up

sign_up() asks for one name at a time with input("Name (blank to finish): ") and stops at a blank line. It rejects two kinds of name, printing a message and asking again:

  • a name with anything but letters in it ("B3n", "Ana Lee"): Letters only, please.
  • a name already signed up: Ben is already signed up.

It returns the list of names, in the order they were typed. To check "already signed up", keep a set of the names you have seen: a set answers in without you writing a loop, and it never holds the same name twice.

Your turn: what does sign_up() return if the user types Zoe, zoe, Zoe, Z o e, and a blank line?

['Zoe', 'zoe'], after printing Zoe is already signed up. and then Letters only, please. Uppercase and lowercase are different letters, so zoe is a new name. Z o e has spaces in it, and isalpha() is False for a space.

The prompt goes in two places

You need a name before the loop can check it, and a new one at the end of every time around. That second input call is the loop's update. Without it, the loop checks the same name forever.

To check Part B, run the file and sign up a few people, including a repeated name and one with a digit in it. If you want to see the list it returns, add a temporary print(names) right under the line names = sign_up(), and take it out afterward.

Part C: read the wishes with load_wishes (Week 10)

wishes.txt holds one wish per line, a name and a wish separated by |:

# name | wish
Ana | a good mystery novel
Ben | fuzzy socks

load_wishes(filename) opens the file, reads it one line at a time, and returns a dictionary from each name to its wish. Each line needs a bit of cleaning: strip() takes the spaces and the newline off the ends, and split("|") breaks it into the name and the wish, which need a strip() of their own. It skips four kinds of line:

  • a blank line,
  • a line that starts with # (a comment, like the first line of the file),
  • a line whose wish is empty, like Eve |,
  • a name it has already seen, which keeps the first wish.
Predict it: what does load_wishes do with the line Gus |?

It skips it. After the strip and the split, the wish is "", and a line with an empty wish doesn't count.

Your turn: the provided wishes.txt has eight lines with a | in them. How many names end up in the dictionary?

Five: Ana, Ben, Cal, Dee, and Fay. The first line is a comment, the second Ben line is a repeat, and Eve has no wish.

Part D: write the cards with save_cards (Week 10)

save_cards(filename, givers, receivers, wishes) writes one line per giver. givers[0] drew receivers[0], givers[1] drew receivers[1], and so on. Each line is the giver's name in capitals, the person they drew, and that person's wish:

ANA: buy a gift for Cal. Wish: anything with din...
BEN: buy a gift for Dee. Wish: hot sauce

A card has only so much room, so a wish longer than 20 characters is cut to its first 17 with a slice, and ... is added. That keeps every wish to 20 characters at most. Someone with no wish in the dictionary gets Surprise them! instead.

Predict it: how does the wish a book about space travel look on a card?

a book about spac... The wish is 25 characters, more than 20, so the card shows its first 17, then .... Count the space: a book about spac is 17 characters.

Your turn: why does a good mystery novel show up whole?

It is exactly 20 characters, and only a wish longer than 20 gets cut.

Test it before you submit

Test each part as you finish it, the way the tips above describe, and submit to Gradescope after each one. Gradescope's messages name the part and what it checked.

Until sign_up works, running gift_swap.py stops with a TypeError in the main block, and until save_cards works, it says it wrote the cards but no cards.txt appears. That is expected, not a sign you broke something. When all four work, run it and type the names below. You should see exactly this, and a new file cards.txt in your Week09 folder:

Sign up for the gift swap!
Name (blank to finish): Ana
Name (blank to finish): Ben
Name (blank to finish): B3n
Letters only, please.
Name (blank to finish): Ben
Ben is already signed up.
Name (blank to finish): Cal
Name (blank to finish): Dee
Name (blank to finish):
Dee would draw their own name, so everyone draws again.
Wrote 4 cards to cards.txt.

ANA: buy a gift for Cal. Wish: anything with din...
BEN: buy a gift for Dee. Wish: hot sauce
CAL: buy a gift for Ben. Wish: fuzzy socks
DEE: buy a gift for Ana. Wish: a good mystery novel

The main block starts the random numbers from a fixed seed, so your draws come out the same as these, as long as draw_name draws exactly the way its docstring says.

Think about it: why did Dee have to draw again?

On the first round, Ana drew Ben, Ben drew Cal, and Cal drew Ana. That left one slip in the hat, and it said Dee. draw_name saw that no name was usable and returned "", and the main block started everyone over. Without the check in Part A, that draw would have looped forever.

Rules

Only what we have covered

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

  • a comprehension or a lambda (Week 11)
  • the dictionary methods get(), setdefault(), keys(), values(), and items() (Week 11)
  • any import other than random

while loops are fair game from now on, and so are the string methods from class, like isalpha(), strip(), split(), startswith(), and upper().

Submission

Submit gift_swap.py to the Gradescope assignment PA3a Gift Swap, then commit and push your Week09 folder (how). You don't need to submit wishes.txt; Gradescope has its own copy. Gradescope also checks that your name and the date are in the docstring, and that ruff check is clean.

Do this option or Trivia Night, not both.

Where the idea comes from

Drawing names from a hat goes by many names: Secret Santa, Kris Kringle, Pollyanna, Wichteln. "Can the last person be stuck with their own name?" is a classic probability puzzle; mathematicians call a draw where nobody gets their own name a derangement.