Tomatoes, Apples, and Bananas: Oh my!
(Originally published November 5, 2015)
Suppose you have a tomato, an apple, and a banana. The tomato bruises easily and is red. The apple is red and is hand-eaten. The banana is hand-eaten.
Tomato: Bruises, red
Apple: Hand-eaten, red
Banana: Hand-eaten
You also have three containers, each of which can contain a single piece of fruit. One container is for red fruit only, one container hand-eaten fruit only, and one container for fruit that bruises only. How do you write an algorithm to allocate fruit to containers so that all the containers are full? You can eyeball it for this specific case: the banana goes in the hand-eaten container, the apple goes in the red container, and the tomato goes in the container for fruit that bruises.
But what about the general case, when you don’t know which fruit or which containers you will have ahead of time?
I was presented with this scenario at work recently, although I have changed the details to protect the guilty. This seemed like some sort of prototypical computer science problem that had probably been studied to death, so I started looking for a pre-built and possibly ‘mathematically-proven’ algorithm that I could adapt. My first consideration was a bin packing algorithm. It seemed to fit but after a few hours, I began to realize the problem. That bin-packing algorithm (specifically, branch and bound), required that I could start with an arbitrary element. That would not work in my case. I also tried looking at routing algorithms, but nothing there seemed to fit.
A suggestion was made to sort the fruit by the number of containers each one can fit into, starting with the fewest. That works for the scenario I’ve detailed above, but was quickly proven not correct for the general case. However, going one step further, I decided to also sort the list of containers that each fruit can go into by the number of fruit that each container type supports. With this in place, the algorithm works for every test case I have been able to find. Once the two sorts are complete, you simply allocate each fruit to an available container starting from the top of the list.
In our example, let’s sort by the number of containers for each fruit. Banana would go first. Then tomato and apple in any order. There are two fruit that fit in red containers, two that fit in hand-eaten containers and one that fits in a container for bruising fruit. That means the order of containers for each fruit is already sorted. Then we start with the banana and put it in the hand-eaten container. Next, let’s take the tomato. We put that in its first container option – the bruises container. Finally, the apple has to go in the red container because the hand-eaten container is occupied.
Is this algorithm ‘correct’? Possibly. That’s the subject of a future post, hopefully.