donuts.rb

# 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