Secret Santa Ruby Quiz

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:

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:

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.