gistfile1.rb

# http://www.facebook.com/jobs_puzzles/index.php?puzzle_id=8
require 'set'
 
class Node
  @@nodes = Hash.new {|h, k| h[k] = Node.new(k)}
  class << self
    def find_clusters
      Node.solidify!
      clusters = []
      nodes.values.each do |n|
        n.clusters.each do |cls|
          clusters << cls.join(", ")
        end
        puts clusters.size
      end
      clusters.uniq.sort.join("\n")
    end
    
    def add_connection(from, to)
      from = from
      to = to
      @@nodes[from].add_outgoing(to)
    end
    
    def nodes
      @@nodes
    end
    
    def solidify!
      nodes.values.each {|v| v.solidify}
    end
  end
  
  def initialize(me)
    @me = me
    @outgoing = Set.new
    @neighbors = SortedSet.new
    @neighbors.add(self)
    @top_of = Set.new
  end
  
  def top_of(cls)
    @top_of.add(cls)
  end
  
  def has_subset?(cls)
    @top_of.each do |c|
      return true if c.superset?(cls)
    end
    return false
  end
  
  def name
    @me
  end
  
  def clusters(list = nil)
    bottom_level = list.nil?
    list = list ? intersect_with(list) : @neighbors
    cs = []
    return bottom_level ? [] : [[self]] if list.entries.last == self
    
    list.each do |key|
      next if key.name <= self.name 
      key.clusters(list).each do |pc|
        pc.unshift(self)
        if !bottom_level 
          cs << pc 
        elsif (bottom_level && pc.size >= 3) && (pcs = pc.to_set) && !pc.last.has_subset?(pcs)
          pc.last.top_of(pcs)
          cs << pc
        end
      end
    end
    cs
  end
  
  def <=>(o)
    self.name <=> o.name
  end
  
  def add_outgoing(to)
    @outgoing.add(to)
  end
  
  def add_neighbor(to)
    @neighbors.add(to)
  end
  
  def goes_to?(to)
    @outgoing.include?(to)
  end
  
  def delete_outgoing(to)
    @outgoing.delete(to)
  end
  
  def intersect_with(list)
    @neighbors & list
  end
  
  def to_s
    name.to_s
  end
  
  def to_str
    name.to_s
  end
  
  def solidify
    @outgoing.each do |key|
      other = Node.nodes[key] if Node.nodes.has_key?(key)
      if other && other.goes_to?(@me)
        add_neighbor(other)
        other.add_neighbor(self)
        delete_outgoing(key)
        other.delete_outgoing(@me)
      end
    end
  end
end

file = File.read('/Users/arya/Desktop/friendlist.txt')
file.split("\n").each do |conn|
  conn = conn.split(/\s+/).collect{|i| i.to_i}
  Node.add_connection(*conn)
end
 
require 'benchmark'
 
 
puts Node.find_clusters.size