naloga2.rb

# added some useful methods to Array class
class Array
  def sum
    self.inject{ |sum,x| sum ? sum + x : x }
  end
end
# counts conflicts at current seat order
def conflicts(order, hates)
  conflict = 0
  order.each do |table|
    if table
      table.each do |guest|
        if hates[guest.to_s]
          conflict += (table & hates[guest.to_s]).length
        end
      end
    end
  end
  conflict
end
# generates a random number between 0..Tables.length-1
def generate_index(t)
  (rand * t).to_i
end

# input
# file = File.new("in0.txt", "r")
file = File.new("in1.txt", "r")
# file = File.new("in2.txt", "r")
# file = File.new("in3.txt", "r")
# file = File.new("in4.txt", "r")
# file = File.new("in5.txt", "r")

# number of invited guests
guests = file.readline.to_i
# table seating capacity
Tables = file.readline.scan(/\w+/).collect!{ |i| i.to_i }
# stores current seat order
order = Array.new
# hates hash holds data about "love" between the invited guests
hates = Hash.new
# how many people does everybody hate
hate_meter = Array.new(guests)
# every body loves each other
total_hate = 0
# ruby way of representing infinity
best_conflict = 1.0/0
# best_arragement should provide NON mexican-like wedding circumstances
best_arragement = nil
# indicates ammount of hate present at each table
hate_at_table = Array.new(Tables.length).fill(0)

(1).upto(guests) { |guest| hates[guest.to_s] = [] }
file.each_line do |line|
  key, value = line.split(' ').first, line.split(' ').last.to_i
  hates[key] << value
  hate_meter[key.to_i] = hates[key].length
end

hate_meter.shift # get rid of guest 0; removes first element of array
total_hate = hate_meter.sum # if everyone sat at 1 table; where's the love?
hate_pivot = total_hate / Tables.length

# debug printouts
# puts "-" * 50
# print "guests = "; p guests
# print "Tables = "; p Tables
# print "hates = "; p hates
# print "hate_meter = "; p hate_meter
# puts "total_hate = #{total_hate}"
# puts "hate_pivot = #{hate_pivot}"
# puts "-" * 50

def reset_order
  (1..Tables.length).map{ [] }
end

table_reset = Tables.clone
order = reset_order

x = 0
total = 0
while(x < 1000000 and best_conflict.nonzero?)
  
  total += 1
  x += 1
  
  hates.each do |guest|
    i = generate_index(table_reset.length)
    if hate_at_table[i] >= hate_pivot
      1000.times do
        if hate_at_table[i] < hate_pivot
          break
        else
          i = generate_index(table_reset.length)
        end
      end
    end
    if table_reset[i].zero?
      1000.times do
        if table_reset[i].nonzero?
          break
        else
          i = generate_index(table_reset.length)
        end
      end
    end
    order[i] << guest.first.to_i
    # puts "#" * 50
    hate_at_table[i] = 0
    order[i].each do |g|
      # print "order = "; p order
      # print "eval = "; p(hates[g.to_s] & order[i])
      # print "hates[g.to_s] = "; p hates[g.to_s]
      hate_at_table[i] += (hates[g.to_s] & order[i]).length
      # print "hate_at_table = "; p hate_at_table
    end
    # puts "#" * 50
    table_reset[i] -= 1
  end
  c = conflicts(order, hates)
  # if c < best_conflict
    # print "order = "; p order
    # print "current_conflict = "; p c
    # print "best_conflict = "; p c
    # puts "-" * 50
  # end
  if c < best_conflict
    best_arragement = order
    best_conflict = c
    puts "-" * 50
    puts "best_conflict = #{best_conflict}"
    print "best_arragement = "; p best_arragement
    print "hate_at_table = "; p hate_at_table
    x = 0
  end
  table_reset = Tables.dup
  order = reset_order
  hate_at_table = Array.new(table_reset.length).fill(0)
end
# print "total = #{total} \n"
print "best_conflict = ";p best_conflict
# results printout
best_arragement.each do |table|
  table.each do |guest|
    print "#{guest} " if guest > 0
  end
  print "\n"
end