public
Created

Implements the algorithm used by the National Resident Matching Program (NRMP) to match residency and fellowship applicants to programs.

  • Download Gist
match.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
# Implements the algorithm used by the National Resident Matching Program
# (NRMP) to match residency and fellowship applicants to programs. The
# algorithm is described here:
# http://www.nrmp.org/fellow/algorithm.html
# and again here:
# http://www.nrmp.org/res_match/about_res/algorithms.html
#
# The Test class computes the example match scenario described on those pages.
 
module Match
class Matcher
attr_accessor :applicants, :programs
 
def self.run(applicants_hash, programs_hash)
applicants = applicants_hash.map { |name, list| Applicant.new(name, list) }
programs = programs_hash.map { |name, attr| Program.new(name, attr[:positions], attr[:list]) }
self.new(applicants, programs).run
end
def initialize(applicants, programs)
self.applicants = applicants
self.programs = {}
programs.each do |program|
self.programs[program.name] = program
end
end
def run
while remaining_applicants.any?
puts "Round ##{round ||= 0; round += 1} (#{remaining_applicants.map(&:name).join(', ')})"
remaining_applicants.each do |applicant|
print " #{applicant.name}: "
while !applicant.exhausted_programs? && !applicant.matched?
program = programs[applicant.next_program]
print "#{program.name} "
program.try_to_match(applicant)
end
puts ""
end
end
self
end
def remaining_applicants
applicants.reject{|applicant| applicant.matched? || applicant.exhausted_programs? }
end
def results_description
"\nMatch results:\n".tap do |str|
programs.each { |name, program| str << program.description + "\n" }
str << "Unmatched: #{applicants.reject(&:matched?).map(&:name).join(', ')}"
end
end
end
class Program
attr_accessor :name, :positions, :list, :matches
def initialize(name, positions, list)
self.name = name
self.positions = positions
self.list = list
self.matches = []
end
def try_to_match(applicant)
if list.index(applicant.name)
print "(#{list.index(applicant.name)}) "
matches << applicant
applicant.matched = true
cull_matches
else
print "(unranked) "
end
end
 
def cull_matches
while matches.size > positions do
reject = matches.sort_by{|applicant| list.index(applicant.name) }.last
reject.matched = false
matches.delete(reject)
print "[culled #{reject.name}] "
end
end
def description
"#{name}: #{matches.map(&:name).join(', ')} #{"(#{positions - matches.size} unfilled)" if matches.size < positions}"
end
end
class Applicant
attr_accessor :name, :list, :matched
def initialize(name, list)
self.name = name
self.list = list
@ranking_position = -1
end
def exhausted_programs?
@ranking_position >= self.list.size - 1
end
def next_program
raise "No ranked programs available!" if exhausted_programs?
@ranking_position += 1
self.list[@ranking_position]
end
def matched?
matched
end
end
end
 
class Test
 
PROGRAMS = {
'city' => {:positions => 2, :list => ['garcia', 'hassan', 'eastman', 'anderson', 'brown', 'chen', 'davis', 'ford']},
'general' => {:positions => 2, :list => ['brown', 'eastman', 'hassan', 'anderson', 'chen', 'davis', 'garcia']},
'mercy' => {:positions => 2, :list => ['chen', 'garcia']},
'state' => {:positions => 2, :list => ['brown', 'eastman', 'anderson', 'chen', 'hassan', 'ford', 'davis', 'garcia']}
}
 
APPLICANTS = {
'anderson' => ['city'],
'brown' => ['city', 'mercy'],
'chen' => ['city', 'mercy'],
'davis' => ['mercy', 'city', 'general', 'state'],
'eastman' => ['city', 'mercy', 'state', 'general'],
'ford' => ['city', 'general', 'mercy', 'state'],
'garcia' => ['city', 'mercy', 'state', 'general'],
'hassan' => ['state', 'city', 'mercy', 'general']
}
 
def self.main
matcher = Match::Matcher.run(APPLICANTS, PROGRAMS)
puts matcher.results_description
end
end
 
Test.main
output.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Round #1 (chen, anderson, brown, garcia, davis, ford, eastman, hassan)
chen: city (5)
anderson: city (3)
brown: city (4) [culled chen]
garcia: city (0) [culled brown]
davis: mercy (unranked) city (6) [culled davis] general (5)
ford: city (7) [culled ford] general (unranked) mercy (unranked) state (5)
eastman: city (2) [culled anderson]
hassan: state (4)
Round #2 (chen, brown)
chen: mercy (0)
brown: mercy (unranked)
 
Match results:
city: garcia, eastman
mercy: chen (1 unfilled)
general: davis (1 unfilled)
state: ford, hassan
Unmatched: anderson, brown

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.