Applying bin packing techniques to GNIP PowerTrack rules

best_fit.rb

domains = ARGF.readlines.map(&:chomp)
queries = domains.map { |domain| %[url_contains:"/#{domain}" OR url_contains:".#{domain}"] }
queries.sort_by!(&:size)

rule_limit = 1024
operator_limit = 30

rules = [queries.pop]

queries.reverse_each do |query|
  best_fit = rules.select { |rule|
    proposed_rule = "#{rule} OR #{query}"

    proposed_rule.size <= rule_limit && proposed_rule.scan(' OR ').size <= operator_limit
  }.max_by(&:size)

  if best_fit
    best_fit << " OR #{query}"
  else
    rules << query
  end
end

puts rules

first_fit.rb

domains = ARGF.readlines.map(&:chomp)
queries = domains.map { |domain| %[url_contains:"/#{domain}" OR url_contains:".#{domain}"] }
queries.sort_by!(&:size)

rule_limit = 1024
operator_limit = 30

rules = [queries.pop]

queries.reverse_each do |query|
  first_fit = rules.find { |rule|
    proposed_rule = "#{rule} OR #{query}"

    proposed_rule.size <= rule_limit && proposed_rule.scan(' OR ').size <= operator_limit
  }

  if first_fit
    first_fit << " OR #{query}"
  else
    rules << query
  end
end

puts rules