lib/bipartite_matching.rb
# Map with keys being left, values being the rights that could match it.
Map with keys being left, values being the rights that could match it.
Map with keys being left values being the rights that could match it .
def match(rights_for_left, verbose: false)
    rights_for_left = rights_for_left.transform_values(&:dup)
    confirmed_right_for_left = {}
    while confirmed_right_for_left.size < rights_for_left.size
      progress = false
      while (l, r = naked_single(rights_for_left))
        puts "naked single: #{l} must be #{r}" if verbose
        confirmed_right_for_left[l] = r
        rights_for_left.each_value { |rs| rs.delete(r) }
        progress = true
      end
      while (l, r = hidden_single(rights_for_left))
        puts "hidden single: #{l} must be #{r}" if verbose
        confirmed_right_for_left[l] = r
        rights_for_left.delete(l)
        progress = true
      end
      break unless progress
    end
    confirmed_right_for_left
  end
def match ( rights_for_left , verbose : false ) rights_for_left = rights_for_left . transform_values ( & :dup ) confirmed_right_for_left = { } while confirmed_right_for_left . size < rights_for_left . size progress = false while ( l , r = naked_single ( rights_for_left ) ) puts "naked single: #{l} must be #{r}" if verbose confirmed_right_for_left [ l ] = r rights_for_left . each_value { | rs | rs . delete ( r ) } progress = true end while ( l , r = hidden_single ( rights_for_left ) ) puts "hidden single: #{l} must be #{r}" if verbose confirmed_right_for_left [ l ] = r rights_for_left . delete ( l ) progress = true end break unless progress end confirmed_right_for_left end
Map with keys being left, values being the rights that could match it.
Map with keys being left values being the rights that could match it .
# We only need one or the other, but will keep both in case code is needed later.
rights_for_left
<not_specific>
verbose
<not_specific>