Class: MatchyMatchy::MatchMaker

Inherits:
Object
  • Object
show all
Defined in:
lib/matchy_matchy/matchmaker.rb

Overview

Implements the Stable Match algorithm ovver a given set of candidates and targets.

Instance Method Summary collapse

Constructor Details

#initialize(targets:, candidates:) ⇒ MatchMaker

Initializes the MatchMaker. You must specify a list of targets (objects “offering” places) and candidates (objects “seeking” places). These can be any type of object: they are wrapped internally, but you should never have to deal with that.

The target and candidate parameters look similar, but the values in the target hash have an extra number, which is the maximum capacity of that target (the total number of candidates it can accept). The capacity may also be omitted, in which case it defaults to 1; that is:

{
  'Gryffindor' => ['Hermione', 'Ron', 'Harry'],
  'Ravenclaw'  => ['Hermione'],
  'Hufflepuff' => ['Neville', 'Hermione'],
  'Slytherin'  => ['Harry', 'Hermione', 'Ron', 'Neville'],
}

…is equivalent to:

{
  'Gryffindor' => [['Hermione', 'Ron', 'Harry'], 1],
  'Ravenclaw'  => [['Hermione'], 1],
  'Hufflepuff' => [['Neville', 'Hermione'], 1],
  'Slytherin'  => [['Harry', 'Hermione', 'Ron', 'Neville'], 1]
}

Examples:

match_maker = MatchyMatchy::MatchMaker.new(
  targets: {
    'Gryffindor' => [['Hermione', 'Ron', 'Harry'], 2],
    'Ravenclaw'  => [['Hermione'], 1],
    'Hufflepuff' => [['Neville', 'Hermione'], 2],
    'Slytherin'  => [['Harry', 'Hermione', 'Ron', 'Neville'], 4]
  },
  candidates: {
    'Harry'    => ['Gryffindor', 'Slytherin'],
    'Hermione' => ['Ravenclaw', 'Gryffindor'],
    'Ron'      => ['Gryffindor'],
    'Neville'  => ['Hufflepuff', 'Gryffindor', 'Ravenclaw', 'Slytherin']
  }
)


46
47
48
49
50
51
 
# File 'lib/matchy_matchy/matchmaker.rb', line 46

def initialize(targets:, candidates:)
  @matchbook = Matchbook.new
  @targets = matchbook.build_targets(targets)
  @candidates = matchbook.build_candidates(candidates)
  @matches = MatchResults.new(targets: @targets, candidates: @candidates)
end

Instance Method Details

#perform ⇒ MatchyMatchy::MatchResults

Kicks off the match. Iterates through the candidates in order, proposing each to their first-choice target. If this match is rejected, the candidate is proposed to their next choice of candidate (if any).

The running time of the algorithm is proportional to the number of candidates and targets in the system, but is guaranteed to finish and yield the same result for the same input.

Returns:



64
65
66
67
 
# File 'lib/matchy_matchy/matchmaker.rb', line 64

def perform
  candidates.each { |candidate| propose(candidate) }
  @matches
end