Solve most influential people test

solve.rb

# We are going to find the most influential people in the in-it network.
# Each user in in-it follows a group of zero or more people.
# The list of "followings" are given to us as an array of pairs. Each pair is
# in the form of [x, y] which means the user with username x
# is following the user with username y.

# A user X influences a user Y if 
#    Y follows X or
#    Y follows one of the users that X influences

# Also, a user cannot follow herself.

# The output should be the list of username of the users that each influence
# the most number of people in the network and no one else influences that many
# users that they each do.

# For example, suppose Ross, Monica, Phoebe, Joey, Rachel and Chandler are the
# in-it users and the input is given as follows:

#[
#  ['Ross', 'Monica'],
#  ['Ross', 'Rachel']
#  ['Rachel', 'Monica']
#  ['Joey', 'Phoebe']
#  ['Chandler', 'Joey']
#  ['Ross', 'Chandler']
#  ['Chandler', 'Ross']
#]

# Then Monica influences Rachel, Ross and Chandler
# and Phoebe influences Joey, Chandler and Ross
# and no one else in the network influences 3 or more people, therefore
# Monica and Phoebe are the most influential people in the network and a correct
# output would be ['Monica', 'Phoebe']

# Write the body of the find_influencers method below that
# gets a list of followings as input and returns the list of
# most influential users in the network.

# Once complete, hit 'run' to test your method agains sample inputs 

require 'set'

def find_influencers(followings)
  g= followings.group_by {|(follower, following)| following }
  pairs = g.values.reduce([]) { |m, e| m + e }
  sums = g.keys.map { |e| [e, Set.new] }.to_h
  nodes = g.keys.map { |e| [e, []] }.to_h
  pairs.each { |p| nodes[p[1]] << p[0] }
  visited = nil

  g.keys.each do |v|
    visited = g.keys.map { |e| [e, []] }.to_h
    pairs.each { |p| visited[p[1]] << false }
    dfs(v, v, nodes, visited, sums)
  end

  s = {}  
  sums.each { |k, v|  s[k] = v.count }
  max = s.values.max

  return s.select { |k| s[k] == max }.keys
end

def dfs(e, r, nodes, visited, sums)
  unless nodes[r].nil?
    nodes[r].each_with_index do |n, i|
      unless visited[r][i]
        visited[r][i] = true
        sums[e].add n
        dfs(e, n, nodes, visited, sums)
      end
    end
  end
end











#############################
# Do not edit below this line

inputs = [[["Ross", "Monica"], ["Ross", "Rachel"], ["Rachel", "Monica"], ["Joey", "Phoebe"], ["Chandler", "Joey"], ["Ross", "Chandler"], ["Chandler", "Ross"]], [], [["a", "c"], ["c", "b"]], [["a", "b"], ["b", "c"], ["c", "a"]], [["a", "b"], ["a", "c"], ["a", "d"]], [["a", "b"], ["b", "c"], ["c", "d"]], [["a", "b"], ["b", "c"], ["c", "d"], ["c", "e"]], [["user1", "user8"], ["user4", "user10"], ["user8", "user5"], ["user9", "user5"], ["user9", "user7"], ["user10", "user5"], ["user10", "user8"], ["user10", "user9"]], [["user1", "user2"], ["user3", "user1"], ["user3", "user2"], ["user3", "user4"], ["user3", "user10"], ["user4", "user3"], ["user4", "user6"], ["user4", "user7"], ["user4", "user9"], ["user7", "user4"], ["user7", "user9"], ["user8", "user3"], ["user9", "user1"], ["user9", "user3"], ["user9", "user8"], ["user10", "user2"], ["user10", "user7"], ["user10", "user8"], ["user10", "user9"], ["user11", "user6"], ["user11", "user8"]], [["user2", "user3"], ["user3", "user6"], ["user5", "user3"], ["user7", "user9"], ["user7", "user11"], ["user7", "user12"], ["user10", "user5"], ["user11", "user2"], ["user11", "user6"], ["user12", "user10"]], [["user1", "user3"], ["user1", "user5"], ["user1", "user8"], ["user1", "user10"], ["user2", "user3"], ["user2", "user9"], ["user2", "user10"], ["user2", "user11"], ["user3", "user5"], ["user3", "user8"], ["user4", "user5"], ["user4", "user11"], ["user4", "user13"], ["user5", "user3"], ["user5", "user8"], ["user5", "user10"], ["user6", "user1"], ["user7", "user2"], ["user8", "user4"], ["user9", "user3"], ["user9", "user10"], ["user10", "user9"], ["user11", "user10"], ["user11", "user13"], ["user13", "user12"]], [["user1", "user8"], ["user2", "user11"], ["user3", "user10"], ["user3", "user14"], ["user4", "user11"], ["user4", "user12"], ["user5", "user4"], ["user8", "user4"], ["user9", "user10"], ["user11", "user7"], ["user13", "user8"], ["user13", "user10"], ["user14", "user1"], ["user14", "user11"]], [["user3", "user5"], ["user5", "user3"], ["user6", "user8"], ["user10", "user1"], ["user10", "user15"], ["user14", "user6"], ["user14", "user12"]], [["user1", "user15"], ["user2", "user8"], ["user2", "user13"], ["user3", "user10"], ["user3", "user11"], ["user3", "user14"], ["user5", "user8"], ["user6", "user1"], ["user6", "user2"], ["user6", "user10"], ["user7", "user8"], ["user7", "user14"], ["user8", "user10"], ["user8", "user13"], ["user9", "user1"], ["user9", "user4"], ["user9", "user8"], ["user9", "user10"], ["user10", "user2"], ["user10", "user6"], ["user10", "user13"], ["user11", "user1"], ["user11", "user3"], ["user12", "user8"], ["user12", "user15"], ["user13", "user8"], ["user13", "user16"], ["user14", "user5"], ["user14", "user6"], ["user16", "user3"]], [["user1", "user8"], ["user1", "user11"], ["user1", "user15"], ["user1", "user16"], ["user2", "user1"], ["user2", "user7"], ["user2", "user12"], ["user3", "user7"], ["user4", "user16"], ["user6", "user5"], ["user7", "user11"], ["user8", "user4"], ["user8", "user16"], ["user10", "user12"], ["user10", "user13"], ["user12", "user6"], ["user12", "user7"], ["user12", "user14"], ["user13", "user6"], ["user14", "user4"], ["user14", "user6"], ["user16", "user10"], ["user16", "user11"], ["user16", "user15"], ["user16", "user17"], ["user17", "user8"]], [["user3", "user4"], ["user4", "user11"], ["user4", "user17"], ["user7", "user4"], ["user8", "user17"], ["user9", "user8"], ["user9", "user13"], ["user9", "user18"], ["user10", "user9"], ["user11", "user7"], ["user11", "user9"], ["user11", "user10"], ["user12", "user2"], ["user14", "user16"], ["user15", "user8"], ["user15", "user12"], ["user15", "user14"], ["user16", "user1"], ["user17", "user3"], ["user18", "user13"]], [["user1", "user4"], ["user1", "user12"], ["user1", "user13"], ["user2", "user10"], ["user2", "user12"], ["user2", "user17"], ["user3", "user12"], ["user4", "user14"], ["user4", "user15"], ["user5", "user9"], ["user6", "user1"], ["user6", "user9"], ["user6", "user14"], ["user7", "user4"], ["user7", "user11"], ["user8", "user16"], ["user9", "user6"], ["user9", "user8"], ["user9", "user14"], ["user10", "user13"], ["user11", "user17"], ["user12", "user9"], ["user12", "user15"], ["user13", "user19"], ["user14", "user10"], ["user14", "user12"], ["user16", "user3"], ["user16", "user9"], ["user17", "user4"], ["user19", "user7"], ["user19", "user11"], ["user19", "user15"]], [["user1", "user3"], ["user1", "user8"], ["user3", "user7"], ["user4", "user2"], ["user4", "user6"], ["user4", "user15"], ["user5", "user4"], ["user6", "user7"], ["user6", "user15"], ["user6", "user17"], ["user6", "user18"], ["user7", "user6"], ["user8", "user13"], ["user9", "user4"], ["user9", "user12"], ["user9", "user16"], ["user10", "user6"], ["user10", "user14"], ["user10", "user19"], ["user11", "user9"], ["user11", "user15"], ["user11", "user18"], ["user11", "user20"], ["user12", "user6"], ["user12", "user11"], ["user12", "user14"], ["user12", "user17"], ["user13", "user3"], ["user13", "user4"], ["user13", "user11"], ["user14", "user11"], ["user14", "user18"], ["user15", "user12"], ["user16", "user11"], ["user18", "user6"], ["user20", "user9"], ["user20", "user17"]], [["user1", "user6"], ["user2", "user18"], ["user3", "user18"], ["user3", "user19"], ["user5", "user13"], ["user7", "user5"], ["user7", "user17"], ["user7", "user21"], ["user8", "user12"], ["user13", "user1"], ["user14", "user6"], ["user16", "user12"], ["user17", "user3"], ["user17", "user5"], ["user18", "user3"], ["user18", "user13"], ["user21", "user17"]], [["user1", "user8"], ["user2", "user1"], ["user2", "user17"], ["user3", "user16"], ["user4", "user2"], ["user4", "user22"], ["user5", "user6"], ["user5", "user11"], ["user6", "user16"], ["user8", "user2"], ["user8", "user6"], ["user9", "user12"], ["user9", "user15"], ["user10", "user9"], ["user10", "user12"], ["user10", "user19"], ["user11", "user14"], ["user12", "user22"], ["user13", "user5"], ["user13", "user11"], ["user14", "user9"], ["user15", "user20"], ["user16", "user11"], ["user16", "user17"], ["user18", "user4"], ["user18", "user19"], ["user20", "user1"], ["user20", "user6"], ["user20", "user10"], ["user21", "user12"], ["user22", "user6"]], [["user1", "user11"], ["user1", "user16"], ["user1", "user17"], ["user1", "user19"], ["user3", "user9"], ["user3", "user10"], ["user3", "user13"], ["user3", "user16"], ["user4", "user9"], ["user4", "user11"], ["user4", "user15"], ["user4", "user22"], ["user5", "user4"], ["user5", "user21"], ["user6", "user8"], ["user6", "user12"], ["user6", "user16"], ["user6", "user17"], ["user6", "user20"], ["user7", "user4"], ["user7", "user10"], ["user7", "user23"], ["user8", "user16"], ["user8", "user17"], ["user8", "user20"], ["user9", "user6"], ["user9", "user11"], ["user9", "user18"], ["user9", "user19"], ["user10", "user2"], ["user10", "user6"], ["user10", "user17"], ["user11", "user2"], ["user11", "user19"], ["user11", "user23"], ["user12", "user5"], ["user14", "user20"], ["user15", "user3"], ["user15", "user19"], ["user16", "user7"], ["user17", "user15"], ["user18", "user3"], ["user18", "user22"], ["user19", "user9"], ["user19", "user13"], ["user19", "user21"], ["user20", "user5"], ["user20", "user15"], ["user21", "user14"], ["user21", "user18"], ["user21", "user20"], ["user22", "user2"], ["user22", "user23"], ["user23", "user2"], ["user23", "user6"], ["user23", "user13"]], [["user2", "user19"], ["user3", "user22"], ["user5", "user3"], ["user5", "user22"], ["user6", "user10"], ["user6", "user14"], ["user7", "user8"], ["user7", "user15"], ["user8", "user15"], ["user11", "user17"], ["user12", "user18"], ["user15", "user2"], ["user15", "user10"], ["user15", "user19"], ["user15", "user24"], ["user17", "user18"], ["user17", "user24"], ["user18", "user12"], ["user21", "user7"], ["user22", "user17"]], [["user1", "user23"], ["user2", "user7"], ["user2", "user14"], ["user3", "user2"], ["user3", "user5"], ["user4", "user6"], ["user7", "user3"], ["user7", "user9"], ["user8", "user7"], ["user11", "user10"], ["user11", "user16"], ["user13", "user24"], ["user14", "user16"], ["user14", "user21"], ["user15", "user8"], ["user15", "user11"], ["user16", "user4"], ["user16", "user15"], ["user17", "user16"], ["user18", "user5"], ["user18", "user14"], ["user19", "user1"], ["user21", "user20"], ["user22", "user14"], ["user23", "user1"], ["user23", "user11"], ["user23", "user12"], ["user24", "user21"], ["user25", "user3"], ["user25", "user5"], ["user25", "user20"]], [["user1", "user2"], ["user1", "user6"], ["user1", "user12"], ["user1", "user25"], ["user2", "user5"], ["user2", "user19"], ["user2", "user21"], ["user3", "user4"], ["user4", "user10"], ["user4", "user12"], ["user5", "user2"], ["user5", "user8"], ["user6", "user19"], ["user7", "user8"], ["user7", "user13"], ["user8", "user15"], ["user8", "user19"], ["user10", "user3"], ["user11", "user13"], ["user11", "user16"], ["user11", "user20"], ["user12", "user1"], ["user12", "user3"], ["user12", "user9"], ["user12", "user15"], ["user14", "user21"], ["user14", "user24"], ["user15", "user11"], ["user16", "user3"], ["user16", "user13"], ["user16", "user14"], ["user17", "user6"], ["user17", "user23"], ["user18", "user2"], ["user18", "user22"], ["user19", "user8"], ["user19", "user9"], ["user19", "user15"], ["user19", "user26"], ["user21", "user24"], ["user22", "user21"], ["user22", "user25"], ["user23", "user7"], ["user23", "user9"], ["user25", "user5"], ["user26", "user16"], ["user26", "user24"]], [["user1", "user2"], ["user1", "user13"], ["user2", "user12"], ["user3", "user7"], ["user3", "user27"], ["user4", "user9"], ["user4", "user19"], ["user6", "user25"], ["user7", "user3"], ["user7", "user21"], ["user8", "user12"], ["user8", "user19"], ["user9", "user7"], ["user10", "user25"], ["user11", "user13"], ["user11", "user22"], ["user12", "user1"], ["user12", "user17"], ["user14", "user9"], ["user14", "user21"], ["user14", "user23"], ["user16", "user5"], ["user16", "user26"], ["user17", "user15"], ["user20", "user7"], ["user21", "user16"], ["user23", "user3"], ["user23", "user7"], ["user23", "user12"], ["user23", "user27"], ["user25", "user4"], ["user26", "user4"], ["user26", "user12"], ["user27", "user8"], ["user27", "user11"], ["user27", "user25"]], [["user1", "user9"], ["user1", "user15"], ["user2", "user18"], ["user2", "user25"], ["user3", "user6"], ["user3", "user14"], ["user4", "user15"], ["user4", "user23"], ["user4", "user24"], ["user5", "user4"], ["user6", "user5"], ["user6", "user18"], ["user7", "user14"], ["user8", "user1"], ["user8", "user14"], ["user11", "user2"], ["user12", "user4"], ["user12", "user14"], ["user12", "user25"], ["user13", "user5"], ["user13", "user21"], ["user13", "user23"], ["user14", "user7"], ["user14", "user16"], ["user14", "user18"], ["user15", "user7"], ["user17", "user3"], ["user17", "user5"], ["user17", "user13"], ["user17", "user28"], ["user18", "user3"], ["user19", "user6"], ["user19", "user28"], ["user20", "user18"], ["user21", "user5"], ["user21", "user8"], ["user21", "user16"], ["user21", "user22"], ["user22", "user25"], ["user23", "user15"], ["user23", "user21"], ["user24", "user14"], ["user25", "user19"], ["user25", "user27"], ["user26", "user5"], ["user26", "user10"], ["user26", "user19"], ["user26", "user23"], ["user27", "user7"], ["user28", "user10"]]]

outputs = [["Monica", "Phoebe"], [], ["b"], ["a", "b", "c"], ["b", "c", "d"], ["d"], ["d", "e"], ["user5"], ["user2"], ["user6"], ["user12"], ["user7"], ["user3", "user5", "user8"], ["user15"], ["user11", "user5"], ["user13"], ["user1", "user10", "user11", "user12", "user13", "user14", "user15", "user16", "user17", "user19", "user3", "user4", "user6", "user7", "user8", "user9"], ["user11", "user12", "user14", "user15", "user16", "user17", "user18", "user2", "user20", "user4", "user6", "user7", "user9"], ["user6"], ["user1", "user10", "user11", "user12", "user14", "user15", "user16", "user17", "user19", "user2", "user20", "user22", "user6", "user8", "user9"], ["user10", "user11", "user12", "user13", "user14", "user15", "user16", "user17", "user18", "user19", "user2", "user20", "user21", "user22", "user23", "user3", "user4", "user5", "user6", "user7", "user8", "user9"], ["user24"], ["user20"], ["user24"], ["user13", "user15"], ["user10"]]


score = 0
inputs.each_with_index do |input, index|
  expected_output = outputs[index]
  print "Test #{index + 1}: "
  begin
    if expected_output.sort == find_influencers(input).sort
      puts "Correct! :)"
      score += 1
    else
      puts "Incorrect :("
    end
  rescue Exception => e
    "Errored :|"
  end
end

puts "Score: #{score} / #{inputs.count}"