Last active
December 22, 2017 18:39
Star
You must be signed in to star a gist
Match making model - solution goes into `generate_new_meeting`.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## CONSTS ##################################################################### | |
PERSON_NUM = 32 | |
# Number of meeting iterations. | |
ITERATION = 64 | |
## METHODS #################################################################### | |
# Generates start-state meetings with the number of iterations | |
def generate_old_meetings | |
meetings = [] | |
ITERATION.times.map do | |
people = (0...PERSON_NUM).to_a | |
while people.size > 0 | |
person_lhs = people.sample | |
people.delete(person_lhs) | |
person_rhs = people.sample | |
people.delete(person_rhs) | |
meetings << [person_lhs, person_rhs] | |
end | |
end | |
meetings | |
end | |
# @TODO Prototype for optimal generation. | |
def generate_new_meeting(meetings) | |
existing_meetings = stat_person_partners(meetings) | |
existing_meetings.each { |_, v| v.uniq! } | |
# Inverse the edges. | |
possible_new_meetings = existing_meetings.each_with_object(Hash.new) { |pair, h| h[pair[0]] = (0...PERSON_NUM).to_a - pair[1] } | |
# ??? | |
end | |
def generate_new_meeting_random(meetings) | |
people = (0...PERSON_NUM).to_a | |
while people.size > 0 | |
person_lhs = people.sample | |
people.delete(person_lhs) | |
person_rhs = people.sample | |
people.delete(person_rhs) | |
meetings << [person_lhs, person_rhs] | |
end | |
end | |
def generate_new_meeting_random_exclude_redundant(meetings) | |
existing_meetings = stat_person_partners(meetings) | |
existing_meetings.each { |_, v| v.uniq! } | |
people = (0...PERSON_NUM).to_a | |
while people.size > 0 | |
person_lhs = people.sample | |
people.delete(person_lhs) | |
potential = people - existing_meetings[person_lhs] | |
next if potential.empty? | |
person_rhs = potential.sample | |
people.delete(person_rhs) | |
meetings << [person_lhs, person_rhs] | |
end | |
end | |
# Hash of people (key) and their number of meetings (value). | |
def stat_person_total(meetings) | |
meetings.each_with_object(Hash.new(0)) { |meeting, h| meeting.each { |id| h[id] += 1 } }.sort.to_h | |
end | |
# Hash of people (key) and all their previous meetings (value - list of other people). | |
def stat_person_partners(meetings) | |
h = {} | |
meetings.each do |meeting| | |
h[meeting[0]] = [] unless h.key?(meeting[0]) | |
h[meeting[1]] = [] unless h.key?(meeting[1]) | |
h[meeting[0]].push(meeting[1]) | |
h[meeting[1]].push(meeting[0]) | |
end | |
h.each { |_, v| v.sort! } | |
h.sort.to_h | |
end | |
# Hash of people (key) and their redundant meeting count (value). | |
def stat_doublemeets(meetings) | |
stat_person_partners(meetings).each_with_object(Hash.new(0)) { |pair, h| h[pair[0]] = pair[1].size - pair[1].uniq.size }.sort.to_h | |
end | |
# Total number of redundant meetings. | |
def stat_doublemeet_total(meetings) | |
stat_doublemeets(meetings).values.reduce(:+) >> 1 | |
end | |
# Total number of all meetings. | |
def stat_meetings_total(meetings) | |
meetings.count | |
end | |
# Runs a solution with a dedicated match generator function. | |
def run_solution(_meetings, name, total_meets_orig, total_doublemeets_orig, block) | |
meetings = Marshal.load(Marshal.dump(_meetings)) | |
block.call(meetings) | |
total_doublemeets = stat_doublemeet_total(meetings) | |
total_meets = stat_meetings_total(meetings) | |
puts "\n#{name} >> #{PERSON_NUM} people | +1 meeting iterations | #{total_doublemeets} redundant meetings out of #{total_meets} all meetings." | |
puts "#{name} >> Delta: +#{total_doublemeets - total_doublemeets_orig} redundant meetings and +#{total_meets - total_meets_orig} new meetings." | |
end | |
## OPS ######################################################################## | |
# Original generation. | |
meetings_orig = generate_old_meetings | |
total_doublemeets_orig = stat_doublemeet_total(meetings_orig) | |
total_meets_orig = stat_meetings_total(meetings_orig) | |
puts "BASE >> #{PERSON_NUM} people | #{ITERATION} meeting iterations | #{total_doublemeets_orig} redundant meetings out of #{total_meets_orig} all meetings." | |
run_solution(meetings_orig, 'RANDOM', total_meets_orig, total_doublemeets_orig, method(:generate_new_meeting_random)) | |
run_solution(meetings_orig, 'RANDOM EXCLUSIVE', total_meets_orig, total_doublemeets_orig, method(:generate_new_meeting_random_exclude_redundant)) | |
run_solution(meetings_orig, 'OPTIMAL', total_meets_orig, total_doublemeets_orig, method(:generate_new_meeting)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment