gistfile1.rb

def solve_for(teams)
  t1 = Time.now

  cs = Array.new(teams) {|i| 1 << i }
  combinations = cs.combination(2).map {|c| [c, (c.first | c.last)] }
  combos = combinations.map {|c| c.last }

  found = nil

  loop {
    begin
      needs = [cs.dup.inject {|m, i| m | i }] * (teams - 1)

      rounds = Array.new(teams - 1) { [] }

      combos.each {|c|
        index = needs.find_index {|n| n & c == c }
        needs[index] ^= c
        rounds[index] << c
      }

      found = rounds.map {|r|
                r.map {|rr|
                  combinations.find {|co| co.last == rr }.first
                }
              }
      break
    rescue
      combos = combos.sort_by { rand }
    end
  }

  t2 = Time.now
  puts
  puts "Solved in #{t2 - t1} seconds. Producing result."
  puts

  found.map! {|day| day.map {|game| [cs.index(game.first), cs.index(game.last)] } }

  puts "#{teams} teams play #{combinations.size} games over #{teams - 1} rounds."
  found.each_with_index {|day, i|
    print "Round #{i}: ".ljust(11)
    puts day.map {|d| d.first.to_s + " vs. " + d.last.to_s  }.join(", ")
  }

  found
end

if $0 == __FILE__

  n = solve_for Integer(ARGV.shift)

  puts "Verifying."

  n.each_with_index {|day, i|
    puts "Round #{i} teams: #{day.flatten.sort.inspect}"
  }

  all = n.inject([]) {|coll, day| day.each {|game| coll << game.sort }; coll }

  puts "Total #{all.size} games, #{all.uniq.size} of those unique."

end