gistfile1.txt

=begin
  BoardLine
  ---------

  Describe one line in the result board.
=end
class BoardLine
  include Enumerable

  attr_accessor :values

  # Constructor
  def initialize(board)
    @board = board
    @values = Array.new(board.width)
  end

  # Read a value from the board line
  def [](index)
    @values[index - 1]
  end

  # Assign a value to the board line in a specific position.
  def []=(index, value)
    if index == 0
      @board.width += 1
      @board.board_array.each {|bl| bl.values.insert(0, nil).first}
      @values[0] = value
    elsif index == @board.width + 1
      @board.width += 1
      @values.push(value).last
    else
      @values[index - 1] = value
    end
  end

  # Iterator
  def each(&block)
    @values.each(&block)
  end

  # Printable
  def inspect
    @values.map{|v| v.to_s.rjust(3)}.join
  end

  # Duplicate current line
  def duplicate(new_board)
    duplicate = self.class.new(new_board)
    duplicate.values = @values.dup
    duplicate
  end
end

=begin
  Board
  -----

  Describe a full board.
=end
class Board
  include Enumerable

  attr_accessor :height, :width, :board_array, :all_values, :max_layout, :last_assignment, :last_board, :forbidden

  # Constructor
  def initialize(max_layout)

    # Initial height and width
    @height = 0
    @width = 0

    # Board container
    @board_array = []

    # Maximum layout size
    @max_layout = max_layout
    @all_values = []
    @forbidden = []
  end

  # Assign borderline
  def [](index)
    if index == 0
      @height += 1
      @board_array.insert(0, BoardLine.new(self)).first
    elsif index == @height + 1
      @height += 1
      @board_array.push(BoardLine.new(self)).last
    else
      @board_array[index - 1]
    end
  end

  # Iterator
  def each(&block)
    @board_array.each(&block)
  end

  # Return total size of the board.
  def surface
    @height * @width
  end

  # Board is empty?
  def empty?
    @board_array.empty?
  end

  # Printable output
  def inspect
    return "Empty Board" if empty?
    (1..@width).map(&:to_s).inject(" "){|a,b| "#{a.rjust(3)}#{b.rjust(3)}"} + "\n" + (1..@height).map{|l| "#{l.to_s.rjust(3)}#{@board_array[l - 1].inspect}"}.join("\n")
  end

  # duplicate board.
  def duplicate
    duplicate = self.class.new(max_layout)
    duplicate.width = self.width
    duplicate.height = self.height
    duplicate.board_array = self.board_array.map{|bl| bl.duplicate(duplicate)}
    duplicate.max_layout = self.max_layout
    duplicate.all_values = @all_values.dup
    duplicate.forbidden = @forbidden.dup
    duplicate
  end

  def neighbour(i, j, value)
    neighbours = []
    if !(i == 0 || i == self.height + 1 && j == 0 || j == self.width + 1)
      if i == 0 && (j != 0 && j != self.width + 1)
        neighbours += [self[1][j]]
      elsif j == 0 && (i != 0 && i != self.height + 1)
        neighbours += [self[i][1]]
      elsif i == self.height + 1 && (j != 0 && j != self.width + 1)
        neighbours += [self[self.height][j]]
      elsif j == self.width + 1 && (i != 0 && i != self.height + 1)
        neighbours += [self[i][self.width]]
      else
        neighbours += [self[i-1][j]] if i != 1
        neighbours += [self[i+1][j]] if i != self.height
        neighbours += [self[i][j-1]] if j != 1
        neighbours += [self[i][j+1]] if j != self.width
      end
    end

    neighbours.include? value
  end

  def empty(i,j)
    return true if i == 0 || j == 0 || i == self.height + 1 || j == self.width + 1
    return self[i][j].nil?
  end

  def assign_and_minify(value, &calc_grade)
    if all_values.include? value
      grade = Float::INFINITY
      best_board = nil
      (0..@height + 1).each do |i|
        (0..@width + 1).each do |j|
          next if forbidden.include? [i,j,value]
          if self.empty(i,j) && self.neighbour(i, j, value)
            duplicate = self.duplicate
            duplicate[i][j] = value
            next if duplicate.surface > max_layout
            curr_grade = calc_grade.call(duplicate)
            if curr_grade < grade
              duplicate.last_assignment = [i,j,value]
              duplicate.last_board = self
              best_board = duplicate
              grade = curr_grade
            end
          end
        end
      end
    else
      grade = Float::INFINITY
      best_board = nil
      (0..@height).each do |i|
        (0..@width).each do |j|
          next if forbidden.include? [i,j,value]
          if self.empty(i,j)
            duplicate = self.duplicate
            duplicate[i][j] = value
            next if duplicate.surface > max_layout
            curr_grade = calc_grade.call(duplicate)
            if curr_grade < grade
              duplicate.last_assignment = [i,j,value]
              duplicate.last_board = self
              best_board = duplicate
              grade = curr_grade
            end
          end
        end
      end

      best_board.all_values += [value] if best_board
    end

    if best_board.nil?
      self.last_board.forbidden += [self.last_assignment]
      best_board = self.last_board.assign_and_minify(self.last_assignment.last,&calc_grade).assign_and_minify(value,&calc_grade)
    end

    best_board
  end
end

class Array
  def sum
    self.inject(&:+)
  end

  def normalize!
    min, max = self.min, self.max
    self.map! { |element| (element - min).to_f / (max - min) }
  end
end

def distance(p1, p2)
  Math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
end

def run(streams, departments, layout, w1, w2)
  streams_sum = []

  departments.each_with_index do |dep, index|
    streams_sum[index] ||= 0
    streams_sum[index] += streams[index].sum
    streams_sum[index] += streams.map{|line| line[index]}.sum
  end

  streams_sum.normalize!.map! { |e| e * w1 }
  normalized_departments = departments.dup
  normalized_departments.normalize!.map! { |e| e * w2 }

  grades = streams_sum.zip(normalized_departments).map(&:sum)

  indexed_grades = (1..grades.length).zip(grades)

  sorted_grades = indexed_grades.sort_by{|a| -a.last}

  calc_grade = Proc.new do |board|
    centers = {}
    rects = {}
    board.each_with_index do |line, index_y|
      index_y += 1
      line.each_with_index do |value, index_x|
        next if value.nil?
        index_x += 1
        centers[value] ||= [0,0,0]
        centers[value] = centers[value].zip([index_x + 0.5, index_y + 0.5, 1]).map(&:sum)
        rects[value] ||= [index_x, index_x + 1, index_y, index_y + 1]
        rects[value][0] = index_x if index_x < rects[value][0]
        rects[value][1] = index_x + 1 if index_x + 1 > rects[value][1]
        rects[value][2] = index_y if index_y < rects[value][2]
        rects[value][3] = index_y + 1 if index_y + 1 > rects[value][3]
      end
    end

    result = rects.map do |value, indices|
      width = indices[1] - indices[0]
      height = indices[3] - indices[2]
      [value, width * height / centers[value][2].to_f + (width > height ? width / height.to_f : height / width.to_f)]
    end

    rects = Hash[result]
    centers = Hash[centers.map { |value, totals| [value, [totals[0] / totals[2], totals[1] / totals[2]]]}]
    sum = 0
    depts = centers.keys
    depts.each do |dept|
      depts.each do |dept2|
        sum += w1 * streams[dept - 1][dept2 - 1] * distance(centers[dept], centers[dept2])
      end
    end
    sum += w2 * rects.values.sum * 1000
    sum
  end

  board = Board.new(layout)
  sorted_grades.each do |curr_dept, _|
    departments[curr_dept - 1].times do
      board = board.assign_and_minify(curr_dept, &calc_grade)
      puts board.inspect
    end
  end

  puts "Board:"
  puts board.inspect
  puts
  puts "Grade: #{calc_grade.call(board)}"
end

# streams = [
#   [0,0,2,0,0,0],
#   [0,0,51,11,0,0],
#   [0,56,0,39,0,51],
#   [25,73,69,0,0,0],
#   [0,0,27,0,0,0],
#   [87,0,0,42,41,0]
# ]
#
# departments = [32,9,27,30,18,10]
#
# layout = 162
#
# w1 = 0.95
# w2 = 0.05
#
# run(streams, departments, layout, w1, w2)

streams = [
  [0,2,0,1,74,0,0,0],
  [0,0,99,56,0,0,0,0],
  [0,0,0,38,1,100,0,98],
  [0,68,51,0,45,10,26,0],
  [24,74,0,0,0,44,70,0],
  [36,65,0,0,88,0,0,22],
  [71,72,30,0,0,0,0,57],
  [0,0,0,68,0,88,0,0]
]

departments = [68,89,50,80,76,63,39,52]

layout = 579

w1 = 0
w2 = 1

run(streams, departments, layout, w1, w2)