Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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