https://www.linkedin.com/feed/update/urn:li:activity:6764510886880169985/

OptionalAssignments.rb

# 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