Last active
February 8, 2021 11:51
-
-
Save sobrinho/7f3488af801d6ed27ffd2e8b68e382c7 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
# Have the function OptimalAssignments(strArr) read strArr which will represent | |
# an NxN matrix and it will be in the following format: ["(n,n,n...)","(...)",...] | |
# where the n's represent integers. This matrix represents a machine at row i | |
# performing task at column j. The cost for this is matrix[i][j]. Your program | |
# should determine what machine should perform what task so as to minimize the | |
# whole cost and it should return the pairings of machines to tasks in the | |
# following format: (i-j)(...)... Only one machine can perform one task. For | |
# example: if strArr is ["(5,4,2)","(12,4,3)","(3,4,13)"] then your program | |
# should return (1-3)(2-2)(3-1) because assigning the machines to these tasks | |
# gives the least cost. The matrix will range from 2x2 to 6x6, there will be no | |
# negative costs in the matrix, and there will always be a unique answer. | |
def optimal_assignments(input) | |
least_cost = Float::INFINITY | |
least_keys = [] | |
permutate(input) do |path| | |
tasks = path.keys | |
costs = path.values | |
total = costs.sum | |
if total < least_cost | |
least_cost = total | |
least_keys = tasks | |
end | |
end | |
least_keys.map.with_index do |machine, task| | |
[task + 1, machine + 1] | |
end | |
end | |
def permutate(input, path = {}, &block) | |
input.each do |row| | |
row.each_with_index do |cost, task| | |
next if path[task] | |
if input.length == 1 | |
yield path.merge(task => cost) | |
else | |
permutate( | |
input[1..-1], | |
path.merge(task => cost), | |
&block | |
) | |
end | |
end | |
break | |
end | |
end | |
data = [ | |
[ | |
[[5,4,2],[12,4,3],[3,4,13]], | |
[[1,3],[2,2],[3,1]] | |
], | |
[ | |
[[1,1,2],[2,1,5],[1,5,1]], | |
[[1,1],[2,2],[3,3]] | |
], | |
[ | |
[[1,4],[5,18]], | |
[[1,2],[2,1]] | |
], | |
[ | |
[[1,2],[1,1]], | |
[[1,1],[2,2]] | |
], | |
[ | |
[[90,75,75,80,82],[35,85,20,50,41],[40,2,24,1,67],[4,70,2,11,23],[23,25,56,44,21]], | |
[[1,2],[2,3],[3,4],[4,1],[5,5]] | |
] | |
] | |
data.each do |input, expected| | |
output = optimal_assignments(input) | |
if output == expected | |
puts "INPUT #{input}" | |
puts "PASSED" | |
else | |
puts "INPUT: #{input}" | |
puts "EXPECTED: #{expected}" | |
puts "RECEIVED: #{output}" | |
puts "FAILED" | |
exit 1 | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment