Skip to content

Instantly share code, notes, and snippets.

@itarato
Last active December 22, 2017 18:39
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save itarato/418fd0429c4ac591c904d344d8d27d8f to your computer and use it in GitHub Desktop.
Match making model - solution goes into `generate_new_meeting`.
## 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