Skip to content

Instantly share code, notes, and snippets.

@arya
Created March 3, 2009 04:14
Show Gist options
  • Save arya/73170 to your computer and use it in GitHub Desktop.
Save arya/73170 to your computer and use it in GitHub Desktop.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment