Created
February 22, 2015 14:04
-
-
Save eladmeidar/aa61195a7658c34b7a19 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
=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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment