Skip to content

Instantly share code, notes, and snippets.

@joaomarceloods
Created October 22, 2019 12:51
Show Gist options
  • Save joaomarceloods/640f2959a79e43712135611c1cc6643c to your computer and use it in GitHub Desktop.
Save joaomarceloods/640f2959a79e43712135611c1cc6643c to your computer and use it in GitHub Desktop.
# Pseudo-code to create pairs of people who didn't meet yet.
# In exceptional case, there may be three people in a group.
donuts = []
people = Person.pluck(:id, :already_met) # { id: 1, already_met: [2, 3, 4] }
for person in people:
# skip if person is already in a donut
next if donuts.flat_map.include(person.id)
# find people who this person didn't meet yet
unmet_ids = people.map(:id).reject(person.already_met)
# if this person met everyone, clear the list and pick anyone
if unmet_ids.empty?
person.already_met = []
unmet_ids = people.map(:id)
end
# filter unmet people who aren't assigned to a donut yet
free_ids = unmet_ids.reject(donuts.flat_map)
if free_ids.any?
# 1. pick a random candidate
# 2. mark that they already met now
# 3. put people in donut
chosen_id = random(free_ids)
people[person.id].already_met << chosen_id
people[chosen_id].already_met << person.id
donuts << [person, chosen]
else
# if no one is free:
# 1. pick a random donut
# 2. mark that all people in that donut already met each other
# 3. put extra person in donut
donut = random(donuts)
person.already_met << donut
donut.each { |person_id| people[person_id].already_met << person.id
donut << person.id
end
end
# TODO: persist donuts and people in database
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment