LubbersSolver.java

   1 import java.util.AbstractMap.SimpleEntry;
   2 import java.util.Arrays;
   3 import java.util.Collections;
   4 import java.util.Comparator;
   5 import java.util.LinkedList;
   6
   7 /**
   8  * Class that implements the pet problem solver.
   9  *
  10  * @author Mart Lubbers, s4109503
  11  */
  12 public class LubbersSolver implements IPetproblemSolver {
  13         @Override
  14         public int[] solve(int n, int m, int[][] compatibility) {
  15                 // Create initial result list of of length n and fill with -1
  16                 int[] result = new int[n];
  17                 Arrays.fill(result, -1);
  18
  19                 // Create the lists that define the sums of the rows and columns
  20                 LinkedList<SimpleEntry<Integer, Integer>> rows = new LinkedList<SimpleEntry<Integer, Integer>>();
  21                 LinkedList<SimpleEntry<Integer, Integer>> cols = new LinkedList<SimpleEntry<Integer, Integer>>();
  22
  23                 // Calculate the sums
  24                 int[] col_sums = new int[m];
  25                 for (int i = 0, sum = 0; i < n; i++) {
  26                         for (int j = 0; j < m; j++) {
  27                                 sum += compatibility[i][j];
  28                                 col_sums[j] += compatibility[i][j];
  29                         }
  30                         rows.add(new SimpleEntry<Integer, Integer>(i, sum));
  31                 }
  32                 for (int i = 0; i < m; i++) {
  33                         cols.add(new SimpleEntry<Integer, Integer>(i, col_sums[i]));
  34                 }
  35                 //Sort the lists so the rows and columns with the least amount of positive compatibilities
  36                 Comparator<SimpleEntry<Integer, Integer>> comp = new Comparator<SimpleEntry<Integer, Integer>>() {
  37                         @Override
  38                         public int compare(SimpleEntry<Integer, Integer> a, SimpleEntry<Integer, Integer> b) {
  39                                 return a.getValue().compareTo(b.getValue());
  40                         }
  41                 };
  42                 Collections.sort(rows, comp);
  43                 Collections.sort(cols, comp);
  44
  45                 /* 1. Find the row or column with the lowest sum(least available matches)
  46                  *    Because the rows and columns are sorted on value the first item is the lowest
  47                  * 2. Find the match with the lowest sum and still positive compatibility for that row or column
  48                  * 3. Select smallest from those indices
  49                  */
  50                 SimpleEntry<Integer, Integer> MINIMUM = new SimpleEntry<Integer, Integer>(-1, Integer.MAX_VALUE);
  51                 while (!(rows.isEmpty() || cols.isEmpty())) {
  52                         //1. Find the row or column with the lowest sum(least available matches)
  53                         SimpleEntry<Integer, Integer> row_l = rows.peekFirst();
  54                         SimpleEntry<Integer, Integer> col_l = cols.peekFirst();
  55
  56                         //2. The row is the lowest
  57                         if (row_l.getValue() < col_l.getValue()) {
  58                                 //Remove the current lowest row sum
  59                                 rows.remove(row_l);
  60                                 //3. Find smallest column that has compatibility 1
  61                                 SimpleEntry<Integer, Integer> smallest = MINIMUM;
  62                                 for (SimpleEntry<Integer, Integer> e : cols) {
  63                                         if (e.getValue() < smallest.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1) {
  64                                                 smallest = e;
  65                                         }
  66                                 }
  67                                 //No pets left that have a positive compatibility
  68                                 if (smallest.getKey() == -1) {
  69                                         continue;
  70                                 }
  71                                 cols.remove(smallest);
  72                                 result[row_l.getKey()] = smallest.getKey();
  73                         //2. The column is the lowest
  74                         } else {
  75                                 //Remove the current lowest column sum
  76                                 cols.remove(col_l);
  77                                 //3. Find smallest row that has compatibility 1
  78                                 SimpleEntry<Integer, Integer> smallest = MINIMUM;
  79                                 for (SimpleEntry<Integer, Integer> e : rows) {
  80                                         if (e.getValue() < smallest.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1) {
  81                                                 smallest = e;
  82                                         }
  83                                 }
  84                                 //No pets left that have a positive compatibility
  85                                 if (smallest.getKey() == -1) {
  86                                         continue;
  87                                 }
  88                                 rows.remove(smallest);
  89                                 result[smallest.getKey()] = col_l.getKey();
  90                         }
  91                 }
  92                 return result;
  93         }
  94 }