Overview

In the previous step we set up our database and data models, so now any name drawing from hats can be persisted. But we haven't actually written the main feature of our app! We could have started with this, which really wouldn't have been a bad idea, but in this case having the data modeling set up first was also a good option, so now we can write this feature with real data.

What is an Algorithm anyway? That sound fancy.

A quick google search defines algorithm as "a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer." So this could be as complicated as a social media recommendation engine or as simple as how to randomly draw names from a hat for giving and receiving gifts.

What should our algorithm be?

First lets define what we want to accomplish first. In our database we have hats, which have drawings and names. Drawings have name matches. Name matches record a giver and receiver. So we want to input a list of names, and output name matches where everyone has a giver, and that giver isn't oneself (maybe we should've added a validation for that! We still can). Lets consider some possibilities. Most languages have some sort of random generator, so we could give it an array (like a list) of numbers and have is select one randomly. With that we could say start with a random name (with a corresponding id) and pick from the other names-ids as who that one gives to. Then remove the receiver from the list and go though the list until there are none left. We could certainly just jump in and start coding that right away! But wait a second, this still introduces a problem that drawing from hats occasionally have, which is if there are say three (or a higher odd number) people, two might draw each other, leaving the last one out. As the pool of people increase, this gets less likely, but can always still happen, if when left with the last three people, two of them give to each other. This is fine with even numbered people, but then we are simply pairing them off occasionally. Or maybe a combination of pairs and circular givings.

One solution to this is to always force a circular giving method, so no one is paired up. I think thats a good place to start. We could make things complicated and allow for pairings by an option before the drawing, but we will just stick with with a circular giving.

So how can we accomplish this? Lets give ourselves an example of how this would work: Luke -> Leia -> Han -> Chewie -> Luke

If I could type in a circle we could have just had Chewie's arrow point back around to Luke. This looks like a simple ordered list to me! [luke, leia, han, chewie] and we just know that the last gives to the first. So all we need to do is gather our list of names in an array and then shuffle them! If this were a computer science class, we might write a shuffle algorithm, and for extra credit you certainly can! But lets be real programmers and not re-invent the wheel and use ruby's built in shuffle method for arrays. Which is literally just calling shuffle on an array. So if we had an array called names set up like this names = [luke, leia, han, chewie] and then simply called shuffle on that names variable that is an Array object names.shuffle it might give us something like [leia, chewie, han, luke]. Then we could loop through that list and set up our name_match records by looking at the next one in the array, or the first one in the list if its the last member of the array. Now that we have a pretty good idea of what are method(s) will need to accomplish lets write some tests so that as we write our methods we have a way to know they are working, in other words, lets let our tests drive our development.

Test Driven Development (TDD) with Rspec

TDD isn't the only or the best way to write code, but it is a good way for quite a few situations. Sometimes you are still working out what a feature even needs to do or how it will work so you might not know what tests to write. That flow is pretty typical. But in our case our criteria for this feature is clear and concrete, so I think we can write the tests first.

In the previous article we added rpsec and factory bot to our project so that as we added our models it would generate the proper files to help us get started and organized. In our project root directory we have a spec directory, this is where all our specs or rpsec tests live. Depending on when you added rpsec, it may have generated a default tests directory for mini-test. We won't be using that.

Anyway in spec, there should be a factories and models folder. Factories is from the factory-bot gem, which gives us an easy way to replicate our models and other ruby objects without having to use as much resources. For our purposes now, we are concerned with drawings, as that will be what is what will 'draw' the names from the hat, in other words create our name_match records that belong to that drawing. Go ahead and open up the spec/factories/drawings.rb file. It should look like this:

FactoryBot.define do
  factory :drawing do
    hat { nil }
    name { "MyString" }
  end
end

This shows that we can give a drawing factory a hat and name. The hat will be a hat factory object and name will default to "MyString" if we leave this as is. Which means we either need to pass it a unique name if we instantiate more than one of these, or we need to tell this factory to generate a unique name somehow. We could use a gem called Faker to generate real looking fake information, like names and make sure they are unique. Or we could simply have it sequence a number after each one is created. To keep things light, lets skip adding another gem for now (I do use Faker a lot, nothing wrong with it) and do this:

FactoryBot.define do
  factory :drawing do
    hat { nil }
    sequence(:name) {|n| "Name #{n}" }
  end
end

Now we can generate a drawing factory and it will always have a unique name by default. Save that file and lets move to actually writing a test or two in spec/models.drawing_spec.rb which looks like this to start:

require 'rails_helper'

RSpec.describe Drawing, type: :model do
  pending "add some examples to (or delete) #{__FILE__}"
end

Now lets think through some of the methods we will need to write to get a drawing object able to generate the name matches we want.

I think in then end we will simply want to be able to call a method called something like draw_names which will do all the things we want, finding the names, shuffling them, then in that shuffled order create name_match records and returning those name_matches. We don't need to test rails on whether or not drawing.names works, or if something like drawing.names.create(giver:..., reciever:...) works either. But the part in between where we are dealing with an array of active-record names, shuffling them and instantiating name_matches accordingly the right way would be the most interesting thing to test. So maybe we have that draw_names method, but it calls shuffle_and_match_names(name_ids) which returns name matches, which each name_id is a giver_id and receiver_id exactly once.

In our drawing_spec.rb file, lets start setting up our factories we will need, which will a hat, drawing, and a few names.

require 'rails_helper'

RSpec.describe Drawing, type: :model do
  describe "#shuffle_and_match_names" do
    let(:drawing) { create(:drawing, hat: hat) }
    let(:name_1) { create(:name, hat: hat) }
    let(:name_2) { create(:name, hat: hat) }
    let(:name_3) { create(:name, hat: hat) }
    let(:hat) { create(:hat) }

  end
end

However, if your spidy-senses tingled, thats good, because we need to also set up names and hats to have unique names, especially names here since we are setting up more than one. Lets copy and paste that exact sequence name line from drawing to the hats and names factories:

FactoryBot.define do
  factory :hat do
    sequence(:name) {|n| "Name #{n}" }
  end
end

FactoryBot.define do
  factory :name do
    hat { nil }
    sequence(:name) {|n| "Name #{n}" }
  end
end

Now that we have our factories set up, let’s write some tests. I just mentioned we want to assert that given a list of name ids, a drawing's shuffle_and_match_names method should return an array of name_matches. In that array we should expect all of the ids passed in to be both found as a receiver_id and a giver_id. Also we should expect that if we ran that method twice on the same ids, those two groups of name matches should equal each other, especially if we gave them different random seeds. Technically it’s possible that the code could work perfect and return the same exact matches, but with a different random seed that shouldn't happen typically.

I wrote out the first test, take a look and then I'll tell you more about it:

describe "#shuffle_and_match_names" do
    let(:drawing) { create(:drawing, hat: hat) }
    let(:name_1) { create(:name, hat: hat) }
    let(:name_2) { create(:name, hat: hat) }
    let(:name_3) { create(:name, hat: hat) }
    let(:hat) { create(:hat) }
    let(:name_ids_array) { [name_1.id, name_2.id, name_3.id] }     

    it "sorted returned giver_ids match sorted given array" do
      shuffled_giver_ids = drawing.shuffle_and_match_names(name_ids_array).pluck(:giver_id)
      expect(shuffled_giver_ids).to match_array(name_ids_array)
    end
end

I added one more variable name_ids_array to make it easier to pass that into our method. In that it block I called the method on the drawing with the name_ids_array, then 'plucked' an array of giver_ids out of it and then wrote the expect statement. That is what actually will give us a pass or fail. We expect that the new shuffled array giver_ids will match the name_ids_array. Using match_array will simply compare the two array's members and disregard their order. When this passes, we know that every one is giving to someone else. Lets also test for receivers in the same way, lets add this underneath:

    it "sorted returned recevier_ids match sorted given array" do
      shuffled_receiver_ids = drawing.shuffle_and_match_names(name_ids_array).pluck(:reciever_id)
      expect(shuffled_receiver_ids).to match_array(name_ids_array)
    end

Once we have both of those passing, we know that we've got enough name matches and that everyone is giving and receiving. Cool!

Its hard to test random things, because technically random could come out as looking ordered! You could technically run a random method twice in a row and get the same result, but lets try to control for that the best we can and write a test. Maybe if we ran this test some thousands of times it would fail occasionally, but probably not as far as I know:

require 'rails_helper'

RSpec.describe Drawing, type: :model do

  describe "#shuffle_and_match_names" do
    let(:drawing) { create(:drawing, hat: hat) }
    let(:name_1) { create(:name, hat: hat) }
    let(:name_2) { create(:name, hat: hat) }
    let(:name_3) { create(:name, hat: hat) }
    let(:hat) { create(:hat) }
    let(:name_ids_array) { [name_1.id, name_2.id, name_3.id] } 

    it "sorted returned giver_ids match sorted given array" do
      shuffled_giver_ids = drawing.shuffle_and_match_names(name_ids_array).pluck(:giver_id)
      expect(shuffled_giver_ids).to match_array(name_ids_array)
    end
    it "sorted returned recevier_ids match sorted given array" do
      shuffled_receiver_ids = drawing.shuffle_and_match_names(name_ids_array).pluck(:receiver_id)
      expect(shuffled_receiver_ids).to match_array(name_ids_array)
    end

    it "shuffles name matches differently with different random seeds" do
      srand(1)
      shuffled_1 = drawing.shuffle_and_match_names(name_ids_array).pluck(:reciever_id, :giver_id)
      srand(2)
      shuffled_2 = drawing.shuffle_and_match_names(name_ids_array).pluck(:reciever_id, :giver_id)
      expect(shuffled_1).not_to eq(shuffled_2)
    end

    it "returns NameMatch objects" do
      shuffled_receiver_ids = drawing.shuffle_and_match_names(name_ids_array)
      expect(shuffled_receiver_ids.first).to be_a(NameMatch)
    end
  end
end

In our first new spec here, it calls srand before each shuffle, which should ensure it gets two different random results. Then it directly compares the plucked array, which has both receiver and giver ids as pairs and expects that they are not equal.

For good measure I added the bottom one to make sure its returning NameMatch objects.

Now with those four tests, we should feel pretty confident our method is doing what we want it to do. Lets start writing that method, and then any others we need to finish this feature on the backend.

Write the feature methods

Lets open up our drawing.rb model file. It should have a couple relationships set up and a couple validations, but thats it. Lets start by writing the method we wrote tests for, to start by simply defining it with def shuffle_and_match_names(name_ids_array) with a return [] and then end in the line and two below.

This should allow us to run our spec and see it fail now. First if you haven't run rails generate rspec:install yet you will need to do that. Then in spec/rails_helper.rb under the Rspec.configure do |config| block add config.include FactoryBot::Syntax::Methods. You should be ready to run bundle exec rspec ./spec/models/drawing_spec.rb which will only run that one spec file. You could remove the file path and run all the specs as well. Either way you should see things like the expected collection contained: and the missing elements were and stuff like that, showing that it had no trouble running the tests (no syntax errors, or set up problems) and they all failed. Which is what we expect for now until we write our method. Lets write it. This is how I would think of it, by breaking it down in steps:

1. Use Array.shuffle to shuffle the initial name_ids_array

2. We need an array of NameMatches in the end, so lets initialize an empty array to add too.

3. Loop through the shuffled id list and initialize a new NameMatch record with the id of the current as the giver and the next as the receiver. We will have to notice if we are at the end of the array to create the last one with the first as the receiver.

4. return that array of name matches.

Lets set up this method with steps 1, 2, and 4 and the shell of 3.

  def shuffle_and_match_names(name_ids_array)
    shuffled_ids_array = name_ids_array.shuffle
    name_matches = []
    shuffled_ids_array.each do |name_id|
      # make the name match, add it to name_matches
    end
    name_matches
  end

You can see we set up all those variables we discussed and returned name_matches. Ruby assumes the last line in the method is what it should return if you don't explicitly write something like return name_matches.

Now lets get to the meat of this method at look at that loop. We are going to need to know each time what the next item is, and for the last one, if we are on the last one, then find the first one. Which means we will need to know our current index meaning which position, an arrays start at 0. With that knowledge we can add 1 to that to find the next one and check if its equal to the length of the array (we will have to -1 from that since the length will be one more than the index of the last item).

First we need to change our each statement to each_with_index and add the index to the enumerator between the pipes. Now there's a few ways to write this out. I've chosen to first figure out who the next_receiver_id is first with some conditions checking if this is the last item in the array or not. Then using that along with the current_giver_id. I renamed my current item I'm on as the current_giver_id to make it clear what it is. So heres what I came up with:

  def shuffle_and_match_names(name_ids_array)
    shuffled_name_matches = []
    shuffled_ids_array = name_ids_array.shuffle
    shuffled_ids_array.each_with_index do |current_giver_id, i|
      next_receiver_id = unless i == shuffled_ids_array.length - 1
                           shuffled_ids_array[i+1] 
                         else
                           shuffled_ids_array[0]
                         end
      shuffled_name_matches.push(name_matches.new(giver_id: current_giver_id, receiver_id: next_receiver_id))
    end
    shuffled_name_matches
  end

In ruby you can set a variable to the result of an if then statement, so you don't have to write it over an over, which is whats going on with next_receiver_id = unless ...

Lets run rspec again bundle exec rspec ./spec/models/drawing_spec.rb

Yes! You should have gotten 4 green dots and 4 examples, 0 failures

Now we know that our method does at least those 4 things correctly at least. But what about some edge cases? Or at least can we think of ways this could break down? What if we passed it an empty array? Or something that wasn't an array? Or nothing at all? If we give it an empty array, what do we want it to do? Return an empty one back, return nil or should it error out? Well the next thing we want to do with this is save the records, or add them to that drawing to save with it. I don't think this method needs to be concerned with adding errors to the drawing object, just one thing and that is given the array return and array of name_matches. So if an empty array is given lets give an empty one back. As written it assuming name_ids_array is an array and its made very clear it should be, so we should probably just let it break whatever it breaks, and if they aren't ids of actual names, then I hold the same sentiment. We can't be much more clear about whats supposed to be passed here and I don't think we need to program it so it gives them lots of nice errors. Eventually it will break if they do it wrong, and we will let them figure that out then.

But let’s write a test and alter the method to make it clear how empty arrays are handled. Lets add a spec directly underneath what we already have to see what currently is happening and to confirm any new code adheres to what we want:

    context "name_ids_array is an empty array" do
      let(:name_ids_array) { [] } 

      it "returns an empty array" do
        expect(drawing.shuffle_and_match_names(name_ids_array)).to eq []
      end
    end

You can see I added a context block, which lets us say, hey here in this block we are changing the context under which this is run, and here its that our name_ids_array is now an empty array. Then we can set that array to just that just for this block.

If you run that spec, it passes. Which means our code already does what we hoped it would by happy accident, well at least according to the effort we put into it. But lets make it clear thats what supposed to happen and skip trying to anything with it if it is already empty:

  def shuffle_and_match_names(name_ids_array)
    return [] if name_ids_array.blank?

    shuffled_name_matches = []
    shuffled_ids_array = name_ids_array.shuffle
    shuffled_ids_array.each_with_index do |current_giver_id, i|
      next_receiver_id = unless i == shuffled_ids_array.length - 1
                           shuffled_ids_array[i+1] 
                         else
                           shuffled_ids_array[0]
                         end
      shuffled_name_matches.push(name_matches.new(giver_id: current_giver_id,
                                                  receiver_id: next_receiver_id))
    end
    shuffled_name_matches
  end
end

Running rspec again should give all passing results. Now lets write some methods that will actually persist our drawing results to the database, and make it so when a drawing is created it will automatically actually draw the names.

Save Our 'Drawing' to the Database

Now that we have a tested method to handle randomly drawing names, lets write a method that will call that one and then save those names.

This method will rely on our database structure and being opinionated on it being setup in that way. While the shuffle and match names only needed this class to have a 'name_matches' relationship. In this method we will need access the the correct list of names that the hat has, so lets make a relationship for that has_many :names, through: :hat in the line below the belongs_to :hat relationship. Now we can call names on a drawing instance and get the hats names, which is the only names we want to deal with for this method. It will also make this method trivial:

  def draw_and_save_matches
    name_matches = shuffle_and_match_names(names.pluck(:id))
    name_matches.each(&:save)
  end

Or a one liner:

  def draw_and_save_matches
    shuffle_and_match_names(names.pluck(:id)).each(&:save)
  end

Now we don't have to test whether rails relationships and save features work correctly as we've put them in this separate method. However, I wouldn't complain to much if someone combined all of this into one, and skipped plucking the ids and just iterated over the names it had access too. I just like this (for now) to make it simpler to test our 'algorithm'

We can also set this up to run each time we create a new drawing. We could debate weather we should create an 'after create callback' for this or just remember to call our draw_and_save_matches each time we want to. In a lot of, if not most situations, it is a really good idea to consider not creating a callback, but this is a situation where the existence of a 'drawing' only matters if names were drawn, right? So a drawing shouldn't exist in our database without names_matches attached, and also without the hat having at least three names. So lets add those constraints.

  after_create :draw_and_save_matches

  def draw_and_save_matches
    if names.size < 3
      errors.add(:base, "Hat must have at least 3 names")
      return
    end

    shuffle_and_match_names(names.pluck(:id)).save
  end

Above our methods and below our validations I added that after_create callback, which simply calls our draw_and_save_matches method every time a new record is created for the first time. I've also added a validation as a guard statement in draw_and_save_matches to make sure there are at least 3 names. When we get to the front end we may come up with a better way to do this validation, but at least its in place for now.

Lets try out creating a drawing in our console to see if it creates the name_matches like we expect. First just to make all our data consistent, I'm going to delete any previous drawings and corresponding name_matches with Drawing.destroy_all. Because we have dependent: :destroy on our has_many relationships destroying the drawing will destroy its dependents, which are all the name_matches. Now you can find your Hat with names we've already created, for me Hat.first found it, if that returns something, you can call Hat.first.drawings.create(name: "1978") (or whatever name you want) and it should create not just the drawing, but all the corresponding name_matches. Your console should give some output like this:

This saved a drawing that belongs to the first found Hat, and because we have an after_create callback for draw_and_save_matches it automatically runs it, which shuffles all the names that belong it it's hat and then creates name match records for us. The intial console output does show the random drawing order, but if we type Hat.first.drawings.first.name_matches it will print it in a easier to read way like this:

You can see by id that 1 gives to 3 who gives to 2 who gives to 4 who gives to 1. Those ids correspond to the names we setup earlier. We could create another drawing to see if its random (which we know it will be based on our specs we wrote, but just for fun). I tried it and sure enough it gave a new order. You could try adding or removing a name from the hat and see how it performs as well. I feel satisfied with what we've got so far. We could type a little script to show us the names, but we will just wait until we get to the front end code to really show it nicely in the browser.

We did it! We wrote the models and business logic for our name from hat drawing app! Now all we need to do is create a web interface to make it usable in a browser.

Here is the git commit I added for this step.