peaktraffic

#!/usr/bin/ruby

# http://www.facebook.com/careers/puzzles.php?puzzle_id=8
# Joep Kerbosch and Coenraad Bron came up with Bron-Kerbosch, I'm just a 
# hack going through the motions of solving algorithmic puzzles.
# Facebook Puzzle Bot, you are a cruel mistress. I think it took me
# about a day to realize max_by isn't in Ruby 1.8.6. Christ.
# - Vincent Woo, 2010 

$sets = []              #output of sets
$sparse = {}            #sparse adjacency matrix
$degen = []             #degeneracy ordering

def ingest(input)
    File.foreach(input) do |line|
        line.strip!
        next if line.empty?
        from, to = line.split("\t")[1..2]
        next if from == to
        $sparse[to] ||= {}
        $sparse[from] ||= {}
        if $sparse[to][from].nil?
            $sparse[from][to] = false
        elsif not $sparse[to][from]
            $sparse[to][from] = $sparse[from][to] = true
        end
    end
    $sparse.merge!($sparse) {|k, row| row.reject{|k, v| !v}.keys}
end

def generate_degeneracy_ordering
    d = []  #degree buckets
    dw = {} #degree for each vertex
    $sparse.each_pair do |vertex, neighbors|
        deg = neighbors.size
        d[deg] ||= []
        d[deg].push vertex
        dw[vertex] = deg
    end
    d.each_index {|i| d[i] ||= []}
    $sparse.size.times do
        vertex = d.find {|x| !x.empty?}.pop
        $degen.push vertex
        for neighbor in $sparse[vertex]
            if d[dw[neighbor]].delete neighbor
                dw[neighbor] -= 1
                d[dw[neighbor]].push neighbor
            end
        end
    end
end

def bron_kerbosch(set, points, exclude, pivot_neighbors=nil)
    if points.empty?
        $sets.push set.sort.join(', ') if set.size > 2 and exclude.empty?
        return
    end

    pivot_neighbors ||= (exclude.empty? or $sparse[points.last].size > $sparse[exclude.last].size) ?
        $sparse[points.last] : $sparse[exclude.last]
        
    points.each_with_index do |vertex, i|
        next if pivot_neighbors.include? vertex
        points[i] = nil
        bron_kerbosch(set + [vertex],
                      points & $sparse[vertex],
                      exclude & $sparse[vertex])
        exclude.push vertex
    end
end

exit unless ARGV.size == 1
ingest(ARGV[0])

if false #this is the Bron Kerbosch algorithm codepath
         #surrounded by an if false to preserve formatting
generate_degeneracy_ordering
before = []
after = $degen[1..$degen.size-1]
$degen.each do |vertex|
    intersect = after & $sparse[vertex]
    bron_kerbosch([vertex],
                  intersect,
                  before & $sparse[vertex],
                  $sparse[intersect.last]) #last elements in $degen have highest degrees
    before.push vertex
    after.shift
end
end

if true
# ... and here's my naive solution! It works? Fast? 
$seen = {}
def subgraph(set, adj)
    hash = (set + adj).sort
    return if $seen[hash]
    $sets.push set.sort.join(", ") if adj.empty? and set.size > 2
    adj.each {|node| subgraph(set + [node], $sparse[node] & adj)}
    $seen[hash] = true
end

$sparse.keys.each do |vertex|
    subgraph([vertex], $sparse[vertex])
end
end
$sets.sort.each {|line| puts line}