CareerCup

Python

def trace(*txt):
    traceOn = False
    if traceOn:
        print(*txt)

def getTimeForDelivery(boxes, machines):
    time = 0
    if len(machines) == 0 and len(boxes)> 0:
        print("No machines, That will take eternity\n")
        return
    
    # work on a copy of boxes and set the weight to deliver 
    # to 0 when delivered
    delb = boxes[:]
    
    # while we have anything to deliver
    while len([b for b in delb if b > 0]):
        noofdeliveries = 0
        for m in machines:
            for bIx in range(len(delb)):
                b = delb[bIx]
                if b == 0:
                    continue
                if m >= b:
                    trace("box %u goes with machine %u"%(b, m))
                    noofdeliveries += 1
                    delb[bIx] = 0
                    break
        time += 1
        trace("waiting for machines... 1 min")
        if noofdeliveries == 0:
            print("Something goes wrong, cannot deliver anything for boxes %s with machines %s\n"%(boxes, machines))
            return 
            
    print("%u mins to move boxes %s with machines %s\n"%(time, boxes, machines))
    return time

# negative tests
getTimeForDelivery([],[1])
getTimeForDelivery([1],[])
getTimeForDelivery([1],[0])
getTimeForDelivery([1,2,3],[1,1])
# positive
getTimeForDelivery([1,1,3],[1,3])
getTimeForDelivery([3,3,3],[1,3])
getTimeForDelivery([1,1],[1,3,5,6])

Output:

0 mins to move boxes [] with machines [1]

No machines, That will take an eternity

Something goes wrong, cannot deliver anything for boxes [1] with machines [0]

Something goes wrong, cannot deliver anything for boxes [1, 2, 3] with machines [1, 1]

2 mins to move boxes [1, 1, 3] with machines [1, 3]

3 mins to move boxes [3, 3, 3] with machines [1, 3]

1 mins to move boxes [1, 1] with machines [1, 3, 5, 6]

Preamble:
- Definitions:
Box(ID, Weight, Scheduled?),
Machine(ID, Capacity),
Schedule(Machine, Boxes)

- Create sorted array of machines sorted by Machine.CarryingCapacity - say, machines
- Create array of boxes sorted by Box.Weight - say, boxes

- Assume there is a binary search utility method over sorted arrays with a twist as:
-- For Machines: Try exact match, otherwise return the next highest capacity machine


Algorithm:
- For every pending box,
-- Find best machine
-- Reduce the machine capacity
-- Add box to schedule
-- Remove box from pending list
- Repeat the above loop
-- Until all the boxes are scheduled or no new schedule has been created
-- Reason for repeating of loop can be
--- More boxes than machines can carry
--- Machine that can fit box has been selected for other boxes with not enough capacity

Psuedo-Code:

total_schedules = new Array()
time_units = 0

while (true) {
  # Initialize the loop state
  unscheduled_boxes = boxes.filter_by { |box| NOT box.Scheduled? }
  unscheduled_machines = machines.dup_as_sorted()
  scheduled_machines = new SortedArray()
  current_schedules = new Array()
  
  for (Box box in unscheduled_boxes) {
    # Find best possible machine for this box weight 
    # in both scheduled and unscheduled machines
    old_machine = scheduled_machines.binary_search(box.Weight)
    new_machine = unscheduled_machines.binary_search(box.Weight)
    
    # If both Old and New Machines are NULL, then continue
    # Why not break? May be one of the old machines has higher capacity 
    # but due to it's existing scheduled capacity can't have this in the schedule
    if (old_machine == NULL && new_machine == NULL) {
      continue;
    }
    
    # If old machine remaining capacity is apt
    if (old_machine!= NULL && 
         (
           (old_machine.CarryingCapacity == box.Weight) || 
           (old_machine.CarryingCapacity <= new_machine.CarryingCapacity)
         ) {
      # Update Schedule
      schedule = current_schedules.find(old_machine)
      schedule.Boxes.add(box)

      # Update Box
      box.Scheduled? = true
    
      # Update Machine Lists
      ## Removing and adding would make the machine sorted on reduced capacity
      old_machine.CarryingCapacity -= box.weight
      scheduled_machines.remove(old_machine)
      ## Only add if there is some capacity left over
      if (old_machine.CarryingCapacity > 0) {
        scheduled_machines.add(old_machine)
      }
    }
    # If new machine capacity is apt
    else 
    if (new_machine!= NULL &&
         (  
           (new_machine.CarryingCapacity == box.Weight) ||
           (new_machine.CarryingCapacity < old_machine.CarryingCapacity)
         ) {
      # Update Schedule
      schedule = new Schedule(new_machine, [box])
      current_schedules.add(schedule)
      
      # Update Box
      box.Scheduled? = true
    
      # Update Machine Lists
      new_machine.CarryingCapacity -= box.weight
      unscheduled_machines.remove(new_machine)
      ## Only add if there is some capacity left over
      if (new_machine.CarryingCapacity > 0) {
        scheduled_machines.add(new_machine)
      }
    } 
  }
  
  if (current_schedules.empty?) {
    # Scheduling failed! Fatal Error
    # May be the box(es) weight is more than machine capacity
    break
  }
  
  total_schedules.add(current_schedules)
  time_units += 1
}