(UVA) Ecological Bin Packing - Solution 2

If you want to see another solution for this problem, click here.

As in the previous solution, I am using Brute Force. However, instead of using some nestled for loops, I am using recursion.

The execution time for this solution was worse than for the previous one.


import java.io.*;
import java.util.*;

class Main  {
    public static int[] binsContent;
    public static ArrayList<Solution> solutions;
    public static int[] chosen;
    public static String colorsLetters = "BGC";
   
    public static int calc(int firstBin, int secondBin, int thirdBin) {
        int sum = 0;
        for (int i = 0; i < 3; i++) { // get how many bottles will be moved
            if (i != firstBin) {
                sum += binsContent[i];
            }
        }
        for (int i = 3; i < 6; i++) {
            if (i%3 != secondBin) {
                sum += binsContent[i];
            }
        }
        for (int i = 6; i < 9; i++) {
            if (i%3 != thirdBin) {
                sum += binsContent[i];
            }
        }
       
        return sum;
    }
   
    public static boolean check() {
        if (chosen[0] != chosen[1] && chosen[1] != chosen[2] && chosen[0] != chosen[2]) {
            return true;
        }
       
        return false;
    }
   
    public static void rec(int bin) {
        if (bin > 2) {
            if (check()) {
                solutions.add(new Solution(colorsLetters.charAt(chosen[0])+""+colorsLetters.charAt(chosen[1])+""+colorsLetters.charAt(chosen[2]), calc(chosen[0], chosen[1], chosen[2])));
            }
            return;
        }
       
        for (int i = 0; i < 9; i++) {
            chosen[bin] = i%3;
            rec(bin+1);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        while (line != null) {
            String[] s = line.split("\\s");
           
            binsContent = new int[9];
            for (int i = 0; i < 9; i++) {
                binsContent[i] = Integer.parseInt(s[i]);             
            }

            solutions = new ArrayList<Solution>();
            chosen = new int[3];
            rec(0);           
                       
            Collections.sort(solutions);
           
            System.out.println(solutions.get(0).colors + " " + solutions.get(0).movements);
          
            line = br.readLine();
        }
                   
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Solution implements Comparable<Solution> {
    String colors;
    int movements;
   
    public Solution(String colors, int movements) {
        this.colors = colors;
        this.movements = movements;
    }
   
    public int compareTo(Solution s) {
        if (this.movements == s.movements) {
            return colorsComparator.compare(this, s);
        }
       
        return this.movements-s.movements;
    }
   
    public static Comparator<Solution> colorsComparator = new Comparator<Solution>() {
        public int compare(Solution s1, Solution s2) {
            return s1.colors.compareTo(s2.colors);
        }
    };
}