Every year, my family has a pretty traditional American Christmas gathering and gift exchange. We all give our presents, have brunch, and enjoy the day. Normally, everybody tries to buy gifts for everyone else. This is really great in theory, but it ends up costing everyone a lot of money, and we all end up with way too many gifts. It's a huge blessing to have a family who loves gifting so much, but in order to be both more economical and equitable, we have decided to try something new this year; a "Secret Santa" exchange.
In the style of "Reddit Gifts" (RIP), each person will be assigned to give a gift to one other randomly-selected person in the group. Everybody gives to and receives from exactly one other person. The bonus is, no one knows who their secret santa is, not even me.
So where does Python come into this? Well, Python is great for writing quick automation scripts. I thought that if I could create a list of everyone participating and their emails, then my Python script could randomly choose everyone's Secret Santa. I sort of underestimated the complexity of the algorithm needed, but that's the fun part.
Anyway, keep reading to see how I did it and maybe implement it yourself. I've also got the code on Gitlab freely available here.
Read in Data with Numpy
First things first, the code reads the data about the family members from a .csv file. Each person has a name, an email, and a list of people they're not allowed to have as their giftee (mostly spouses). The data is read into a numpy matrix, then converted into a dictionary of dicts, mapped by the person's name. This makes it easy to get each person's information.
# Read table into a numpy matrix
data = np.genfromtxt('people_real.tsv', delimiter=";", skip_header=1, dtype=str, filling_values=1)
# some simple checks on the format
if data.shape[0] == 0:
print("Data doesn't have any rows.")
quit()
if data.shape[1] != 3:
print("Data doesn't have 3 columns.")
quit()
print("Data found: ")
# Turn data into a dict where the key is the person's name. Each entry in the
# dict is another dict which stores the email, name, and list of exclusions
people_list = {}
for person in data:
name = person[0]
email = person[1]
exclusions = person[2]
exclusions_set = set(exclusions.split(","))
print(f"\t{name}: {email} -- Exluding: {exclusions_set}")
people_list[name] = { 'name': name, 'email': email, 'exclusions': exclusions_set }
Next, each person gets a list added to their dict entry, under 'giftees'. This is all the people that person can give to, by name.
# Create a set of all possible pairs of matches (every person with every other person)
# with consideration to the exclusions. Each person's dict entry also gets a new key 'giftees'
# which is a list of all the people this person can give to
print("\nIterating all possible matches... ")
possible_pairs = []
for name0 in people_list:
persons_giftees = []
for name1 in people_list:
if name0 == name1:
continue
if name1 in people_list[name0]['exclusions']: # Skip the 2nd person if they're in the 1st person's exclusions list
continue
pair = (name0, name1)
possible_pairs.append(pair)
persons_giftees.append(name1)
if (args.verbose):
print(f"\tFound potential pair: {pair}")
people_list[name0]['giftees'] = persons_giftees
Assignment Algorithm (Depth-First Search)
The next part of the code is a bit trickier, but it's basically a graph traversal algorithm.
Now, I still haven't decided if it's more complicated than it needs to be; there's probably an algorithm that is much more efficient or better optimized, but I wrote this program in day and I just needed it to work. The reason that I finally settled on this algorithm is because of the fact that there's an exclusion list; each person may have one or more people that they can't give to. If this weren't a factor, then I believe that there may be a simple greedy algorithm solution out there. But anyway, the algorithm is basically as follows:
- We imagine all of the people in this exchange as nodes in a graph, and the edges are going from each person to whoever they could give to. Since each person can potentially give (at most) to every other person, then this approaches a fully connected graph if there are no exclusions.
- Each step of the outer loop of the algorithm starts with one person, and we iterate through all the people. From this starting person, we recursively map the graph in a depth-first search.
- During the DFS, every time we find a new route that returns us to the starting person (start and end on the same node, a graph cycle) then we add that route to a list of possible routes. Some simple rules dictate which routes are accepted, such as the route must be same length as the number of people + 1.
gift_graphs = [] # Holds all possible gifter -> giftee pair lists
#Recursive DFS through graph of participants
def walkgraph(people_graph, current_person, curr_path, all_paths):
# Base case, copy route into final route list
if len(curr_path) == len(people_graph) + 1:
# print(f"Found chain: {curr_path}")
all_paths.append(curr_path.copy())
return
for giftee in people_graph[current_person]['giftees']:
# Rules for which routes are accepted.
if giftee in curr_path and len(curr_path) != len(people_graph):
continue
if len(curr_path) > 2 and giftee == curr_path[-2]:
continue
if len(curr_path) == len(people_graph) and giftee != curr_path[0]:
continue
curr_path.append(giftee)
walkgraph(people_graph, giftee, curr_path, all_paths)
curr_path.pop()
return
def startwalk(people_graph):
all_paths = []
for first_person in people_graph:
curr_path = []
curr_path.append(first_person)
walkgraph(people_graph, first_person, curr_path, all_paths)
return all_paths
print("\nWalking graph of all possible gift chains...\n")
final_paths = startwalk(people_list)
if len(final_paths) == 0:
print("No valid gift chains found.")
quit()
After the DFS algorithm has obtained a list of all possible walks through the graph, we select one at random by generating a random int as the index into the list. After the path is selected, then it is broken down into a list of pairs of people; a gifter and a giftee. These are the pairs that will be used for the exchange.
print("\nSelecting random gift chain...")
idx = randint(0, len(final_paths) - 1)
print(f"\t Selected chain {idx}.")
print(f"\nTurning gift chain {idx} into pairings...")
chain = final_paths[idx]
pairings = []
lastName = chain[0]
for i in range(1, len(chain)):
pairings.append((lastName, chain[i]))
lastName = chain[i]
for pair in pairings:
if args.verbose:
print(f"\t- {pair}")
people_list[pair[0]]['assignee'] = pair[1]
Send All the Emails!
Then, for each pair, we send an email to the gifter, with information about who they need to shop for.
Note that this code uses some functions from a separate file in my code, email_sender.py. I didn't write most of this other module, it was adapted from a blog post here.
This page also helped me understand how it works.
I did add a small part that reads the authorization information from a csv file. You can use this, or just copy your own tokens into the code and have it hardcoded.
from email_sender import EmailSender
email = np.genfromtxt('email_login.csv', delimiter=",", skip_header=1, dtype=str, filling_values=1)
if email.shape[0] == 3:
client_id = email[1].strip()
client_secret = email[2].strip()
from_addr = email[0].strip()
sender = EmailSender(client_id, client_secret, from_addr, None)
quit()
elif email.shape[0] == 4:
client_id = email[1].strip()
client_secret = email[2].strip()
from_addr = email[0].strip()
refresh_token = email[3].strip()
sender = EmailSender(client_id, client_secret, from_addr, refresh_token)
else:
print("Invalid file for sender email. Should be a csv with a header, and 3 columns; one for email, one for client_id, and one for client_secret. Optionally, 4th column for refresh token")
quit()
print("\nSending emails to participants:")
for person in people_list:
addr = people_list[person]['email']
assignee = people_list[person]['assignee']
if addr and assignee:
if not args.test:
print(f"\tSending to {addr}:")
bodyStr = f"HTML here. {person}:{assignee}"
sender.sendEmail(addr, "Gift assignee", bodyStr)
print("\tSent.")
else:
print(f"\tTest {addr}: didn't send.")
Note that the contents of the email can be constructed with HTML, where I have the variable "bodyStr". I've just removed the contents in this block because it was messing with my site's page parser.
And that's it! I hope you enjoyed reading about this short Python project.