We’re back to doing another simple UVa Online Judge problem, and this time we take on problem 102, Ecological Bin Packing. In the problem we are asked to solve a bin packing problem about recycling glass. It can be easily solved with brute force, but requires careful coding. Enough yapping, let’s take a look at the problem description.

## Interpretation

We have three bins, each of which contains some number of bottles. There are three types of bottles; brown, green and clear, denoted by “B”, “G” and “C”, respectively. We are given how many bottles of each type are in each bin.

In this particular example are 9 bottles. The first bin contains two brown bottles and one clear bottle, the second bin contains four green bottles, and the third bin contains two clear bottles. The problem description tells us that we are recycling the bottles, and we must sort them so that there is only one type of bottles in each bin. For the example above, we could have moved the two brown bottles in the first bin to the third bin, and the two clear bottles in the third bin to the first bin.

Now there is only one type of bottles in each bin; clear bottles in the first bin, green bottles in the second bin, and brown bottles in the third bin. We had to move four bottles to accomplish this. But lets go back to the previous example. We can also achieve this kind of sorting by moving only one bottle: the clear bottle in the first bin to the third bin.

In fact, that is exactly what the problem description is asking about: the minimum number of bottles that need be moved in order to have only one type of bottle in each bin. We are also asked to return in what order the bottle types will be after they have been moved to their correct places. For example, in the last image, brown bottles are in the first bin, green bottles in the second bin and clear bottles in the third bin. So the order is *brown*, *green*, *clear*, or simply “BGC”. If there are multiple orders that would result in the minimum move count, then we are asked to output the order which has the alphabetically first string representation. Therefore “CBG” would be chosen instead of “GBC”, assuming they both have the minimum move count.

## Implementation

So how do we find the minimum move count? First we must notice that if we decide some order in which to put the bottle types, for example “CBG”, then we can easily compute how many moves we would need by counting how many bottles are in the wrong bin according to the bottle type order. There are only possible permutations of the bottle order that we can choose, so looping through each permutation and computing the move count of that particular order is completely feasible. Then we just keep track of the lowest move count, along with its alphabetically first bottle type order, that we’ve found so far.

Since there are only six possible permutations, we’re probably faster to manually write each of them down instead of writing a special function to generate them. Then we also need to be careful when we write the implementation – there are a lot of multiple dimensional arrays and indices that can go wrong. When we’re finished, the code might look something like this:

Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out, true); // types of bottles: brown, green, clear char[] bottleType = { 'B', 'G', 'C' }; // all 6 possible permutations of bottle type-to-bin mappings int[][] permutations = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } }; // bottles[i][j] are the number of type j bottles in bin i int[][] bottles = new int[3][3]; // while there is a test case left while (in.hasNextInt()) { // the minimum bottle move-count so far, // initially -1 to indicate that we haven't found anything yet int minCount = -1; // the string representation of the permutation with the minimum bottle move-count so far String minPerm = ""; // read in the bottle counts for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { bottles[i][j] = in.nextInt(); } } // loop through each permutation for (int i = 0; i < permutations.length; i++) { // count how many bottles need to be moved int curCount = 0; // j is the current bin, and permutations[i][j] is the bottle-type that we want in that bin for (int j = 0; j < 3; j++) { // go through all each bottle-type k for (int k = 0; k < 3; k++) { // if the current bottle type is not supposed to be in the current bin if (permutations[i][j] != k) { // then we need to move them, and we're counting how many we need to move curCount += bottles[j][k]; } } } // the string representing the current permutation, example: "GCB" String curPerm = "" + bottleType[permutations[i][0]] + bottleType[permutations[i][1]] + bottleType[permutations[i][2]]; // if this is the first permutation we try, or if the current bottle move-count is less than the minimum bottle move-count, // or the current bottle move-count is equal to the minimum bottle move-count and the permutation string is less than the // permutation string of the minimum bottle move-count if (minCount == -1 || curCount < minCount || (curCount == minCount && curPerm.compareTo(minPerm) < 0)) { // then this is the best permutation so far minCount = curCount; minPerm = curPerm; } } // print the minimum bottle move-count and the permutation string out.println(minPerm + " " + minCount); }

## Conclusion

And that pretty much sums it up. The complete source code is located here.

Leave a comment if you have any questions, or if you want to tell us how you solved the problem.

nice.