Happy Holidays everyone! I wanted to do something in the spirit of the season and thought the Secret Santa Ruby quiz would be the perfect puzzle to tackle. This puzzle is right on theme, but it's also really well-defined and small enough in scope that we can go through the process of solving it in a blog post. Let's get started.
To make sure everyone is on the same page, this won't be strictly for beginners to Ruby or programming. I will gloss over specific steps like initializing a repository with RSpec, running tests, and general Ruby conventions. Instead, I will link to references that provide more information.
The Puzzle Requirements
The quiz defines the rules as the following:
Feed the script a list of names on STDIN. It might look like
Alice Jones <alice@example.com>
Bob Jones <bob@example.com>
Carlos Jones <ricky@example.com>
Demi Smith <demi@example.com>
Eli Smith <eli@example.com>
Florence Williams <florence@example.com>
With a format of
FIRST_NAME space FAMILY_NAME space <EMAIL_ADDRESS> newline
To keep things simple: people only have two names (no Jrs, IIs, etc.).
The script should choose a Secret Santa for every name on the list. A person can't be their own Secret Santa. And you can't be assigned to anyone with the same FAMILY_NAME.
Finally, email the Santa and tell them who their person is.
To make the content more focused, I made the scope a little bit smaller by tweaking a few of the requirements. I'm reading from a text file instead of feeding the list through STDIN, and I will not be sending emails. I also gave myself about an hour to work on this puzzle.
My Thought Process
When starting a new Ruby project, the first thing I do is to initialize my directory with a testing framework. I use RSpec.
In an "ideal" scenario, whenever I sit down to tackle a problem, I start by thinking about the very first test. It should test exactly one thing, and it should fail. After I get that test to pass, I write another test that will fail, write enough code to make that test pass, and maintain passing status for all previous tests. I repeat this cycle, this is known as test-driven development.
However, real-life and what's ideal often diverge. I don't always practice "perfect" test-driven development, but I still try to let tests guide me.
These are the steps I wanted to take, removed from implementation:
- Receive a list of names and emails and from that list create Santas.
- From the Santas list, for each Santa, generate all possibilities for who their assignees could be.
- Pick a random assignee from each potential assignment for each Santa.
I thought the steps above would be my basic algorithm going into this problem.
I would discover that I would need to tweak it a little bit for step three to work reliably. Picking a random person from each potential assignment for each Santa means that sometimes the same person gets assigned to multiple Santas. I would later change step three to look like this:
- Pick a random person from the potential assignment for each Santa, keep re-picking until all the assignees are unique.
Not the most sophisticated or performant algorithm, but we're getting things done, and we're testing our expectations. This puzzle is still a great learning opportunity.
Code Walk Through
For this section, I want to walk you through each step I worked through, starting with my first test.
Step 1: Receive a list of names and make Santas
it "receives a list of names and emails and creates santas" do
secret_santa = SecretSanta.new('./santas.txt')
expect(secret_santa.santas).to_not be_empty
end
When it comes to writing the first test, I want to be as general as possible. I know that I will have a class called SecretSanta, and I want to initialize it with my text file full of my Secret Santas in the format we defined above. However, I don't want to tie myself to a particular implementation regarding how I store the santas attribute.
Tests that aren't dependent on implementation details are much easier to maintain.
After initializing the SecretSanta class, I want to make sure that there is something inside the santas attribute. That could be any number of data structures. I want to keep my tests general, so they don't have to change.
If I tied myself right away to expecting santas to be a particular data structure, but down the line, I decided I want them to be a different data structure, I would have to change my test. But, is it truly a failing test? It's still receiving a list of names and creating santas, but because it's tied to a specific implementation, the expectation needs to change.
Next, I write enough code to make the test pass.
class SecretSanta
attr_reader :santas
def initialize(file)
@santas = File.open(file).read.split("\n")
end
end
Step 2: For each Santa, find their potential assignees
I broke my rule here from above when I initially wrote this test. I tied myself to the implementation. And I tied myself to my outside inputs (the textfile I pass in to initialize).
it "doesn't allow someone to be assigned to their family member" do
secret_santa = SecretSanta.new('./santas.txt')
expect(secret_santa.potential_assignees[0]["Alice Jones"]).to eql [["Demi", "Smith", "<demi@example.com>"], ["Eli", "Smith", "<eli@example.com>"], ["Florence", "Williams", "<florence@example.com>"]]
end
I had an idea in my mind of how I wanted these potential_assignees to look. And I let it drive the test rather than the other way around. Not to mention, this isn't testing what it purports to it doesn't allow someone to be assigned to their family member. The test is setting up an expectation for how a data structure looks, nothing about behavior. We'll see how this bites us below.
The code below makes the test above pass.
class SecretSanta
attr_reader :santas
def initialize(file)
@santas = File.open(file).read.split("\n").map { |s| s.split }
end
def potential_assignees
@santas.map do |santa|
{ "#{santa[0]} #{santa[1]} "} => @santas.reject { |s| s[1] == santa[1] }}
end
end
end
I decided to assign each Santa an array of emails instead of the full name and email for each potential assignee. But the test is tied to the implementation above, so it fails.
The code that makes this test break:
def potential_assignees
@santas.map do |santa|
{ "#{santa[0]} #{santa[1]}" => @santas.reject { |s| s[1] == santa[1] }.map { |s| s[2].flatten }
end
end
Ouch. Testing this behavior is difficult with our current setup. I want a little more structure inside the santas attribute.
Maybe something like this?
class SecretSanta
Santa = Struct.new(:first_name, :family_name, :email)
attr_reader :santas
def initialize(file)
santa_info = File.open(file).read.split("\n")
@santas = santa_info.each_with_object([]) do |santa, santas|
first_name, family_name, email = santa.split
santas << Santa.new(first_name, family_name, email)
end
end
end
The santas attribute is a collection of Structs; this gives us the attributes of first_name, family_name, and email on each Santa. Plus, our first test was general enough that even refactoring our santas attribute to look different keeps the test passing.
For the test to ensure no one gets assigned to a family member, I had to test a fair bit of the implementation. But this test isn't also tied to the text file we pass into the initializer.
it "doesn't allow a santa to be assigned a family member" do
secret_santa = SecretSanta.new('./santas.txt')
expect(secret_santa.santas.first.potential_assignees.map(&:family_name)).to_not include secret_santa.santas.first.family_name
end
I've also decided to include the potential_assignees as an attribute on each Santa Struct.
This test might know too much about how @santas look, but I feel it's valid for our use case. We need to understand how @santas looks because the way we're assigning potential_assignees depends on it.
class SecretSanta
Santa = Struct.new(:first_name, :family_name, :email, :potential_assignees)
attr_reader :santas
def initialize(file)
santa_info = File.open(file).read.split("\n")
@santas = santa_info.each_with_object([]) do |santa, santas|
first_name, family_name, email = santa.split
santas << Santa.new(first_name, family_name, email)
end
set_potential_assignees
end
def set_potential_assignees
@santas.map do |santa|
santa.potential_assignees = @santas.reject { |s| s.family_name == santa.family_name }
end
end
end
I've also gone ahead and moved the creation of potential_assignees to the initializer; one less thing we have to call in the tests explicitly.
If I had more than an hour, I could develop a more elegant solution, but I am happy with this small puzzle solution. I've moved away from being dependent on two things: the text file AND the implementation. I'm dependent on the implementation only now, but at least the test is
testing what it says it is. The expectation is that the potential_assignee attribute won't include the family_name for that Santa.
Step 3: Pick randomly for each Santa
For this step, I initially had a naive implementation for the algorithm. I picked a random assignee for each Santa; this led to assignees that were not unique and some people not assigned. The code below relies on the code in step two before we refactored to Structs.
it "picks a random person from the potential assignees list" do
secret_santa = SecretSanta.new('./santas.txt')
potentials = secret_santa.potential_assignees
picked = secret_santa.pick_assignees(potentials)
assigned = picked.map do |santa|
santa.map do |k, v|
v
end
end
expect(assigned.flatten.uniq.count).to eql secret_santa.santas.count
end
This test created the potential_assignees, called the pick_assignees function, and then created an array of the picked (assigned). The expectation was that all the unique values in assigned would be equal to the total number of santas. Each Santa should be assigned a unique person. This test was flaky, and I think I saw it pass one time out of the dozens and dozens of times I ran it. Here is the code for step three:
def pick_assignees(potentials)
potentials.map do |potential|
{ "#{potential.keys[0]}" => potential.values.flatten.sample }
end
end
This naive implementation maps through the potential_assignees (at this point that data structure looked like:
[{"First Name Family Name" => ["email", "email", "email"]}, {"First Name Family Name" => ["email", "email"]}]`)
for each potential it just picks a random email from it's values using sample, returning an array that looks like:
[{"First Name Last Name" => "email" }, {"First Name Last Name" => "email"}]
Step 3a. Keep re-picking until everyone has a unique assignee
I had to make the algorithm a little bit smarter. The simplest way I could think to do that was to keep calling pick_assignees until every Santa had a unique assignee.
def pick_assignees(potentials)
picked = potentials.map do |potential|
{ "#{potential.keys[0]}" => potential.values.flatten.sample }
end
assigned = picked.map do |santa|
santa.map do |k, v|
v
end
end
if assigned.flatten.uniq.count != @santas.count
pick_assignees(potentials)
else
return picked
end
end
Now the test passes consistently. We're using recursion (a function that calls itself) to solve this problem in a kind of brute-force way. If the unique assigned values don't equal the total number of @santas, try again; if they do return the assignments.
Let's refactor this to use our Santa Structs.
class SecretSanta
Santa = Struct.new(:first_name, :family_name, :email, :potential_assignees, :assignee)
attr_reader :santas
def initialize(file)
...
set_assignee
end
...
def set_assignee
@santas.map do |santa|
santa.assignee = santa.potential_assignees.sample
end
if @santas.map(&:assignee).map(&:email).uniq.count != @santas.count
set_assignee
else
return
end
end
end
it "picks a random person from the potential santas list" do
secret_santa = SecretSanta.new('./santas.txt')
expect(secret_santa.santas.map(&:assignee).map(&:email).uniq.count).to eql secret_santa.santas.count
end
The test, at this point, reiterates what set_assignee does internally. We could figure out a better way to approach this test, but once again, I am happy with where we got for a short time-boxed puzzle.
Let's look at the SecretSanta class before our refactoring!
class SecretSanta
attr_reader :santas
def initialize(file)
@santas = File.open(file).read.split("\n").map { |s| s.split }
end
def potential_santas
# Gives a data structure that looks like:
# [{ "First Name Family Name" => ["email", "email", "email"]}]
@santas.map do |santa|
{ "#{santa[0]} #{santa[1]}" => @santas.reject { |s| s[1] == santa[1] }.map { |s| s[2]}.flatten }
end
end
def pick_santas(potentials)
picked = potentials.map do |potential|
{ "#{potential.keys[0]}" => potential.values.flatten.sample }
end
assigned = get_assigned(picked)
if unique_assigneds(assigned) != @santas.count
pick_santas(potentials)
else
return picked
end
end
private
def get_assigned(picked)
picked.map do |santa|
santa.map do |k, v|
v
end
end
end
def unique_assigneds(assigned)
assigned.flatten.uniq.count
end
end
Not bad, but room for improvement. Something we didn't touch on here is pulling out methods into private methods. I am conflicted if this is the right way to approach a private method, but it's what I'm keen to do.
Our refactored version:
class SecretSanta
Santa = Struct.new(:first_name, :family_name, :email, :potential_assignees, :assignee)
attr_reader :santas
def initialize(file)
santa_info = File.open(file).read.split("\n")
@santas = santa_info.each_with_object([]) do |santa, santas|
first_name, family_name, email = santa.split
santas << Santa.new(first_name, family_name, email)
end
set_potential_assignees
set_assignee
end
def set_potential_assignees
@santas.map do |santa|
santa.potential_assignees = @santas.reject { |s| s.family_name == santa.family_name }
end
end
def set_assignee
@santas.map do |santa|
santa.assignee = santa.potential_assignees.sample
end
if @santas.map(&:assignee).map(&:email).uniq.count != @santas.count
set_assignee
else
return
end
end
end
I think this version is much easier to understand. The Struct makes our code more flexible while also providing the benefit of named attributes. No more passing around square brackets with index numbers inside. Human-readable names make the code much more approachable.
Conclusion & Further Reading
I had a lot of fun doing this Ruby Quiz. I attempted to do it during my apprenticeship and got stuck on my own. It reminds me of how much progress I have made over the past six-plus years. I'd love to see your solutions to this quiz.
Top comments (0)