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 are up front
  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                 while (!(rows.isEmpty() || cols.isEmpty())) {
  51                         //1. Find the row or column with the lowest sum(least available matches)
  52                         SimpleEntry<Integer, Integer> row_l = rows.peekFirst();
  53                         SimpleEntry<Integer, Integer> col_l = cols.peekFirst();
  54
  55                         //2. The row is the lowest
  56                         if (row_l.getValue() < col_l.getValue()) {
  57                                 //Remove the current lowest row sum
  58                                 rows.remove(row_l);
  59                                 //3. Find smallest column that has compatibility 1
  60                                 SimpleEntry<Integer, Integer> min = new SimpleEntry<Integer, Integer>(-1, Integer.MAX_VALUE);
  61                                 for (SimpleEntry<Integer, Integer> e : cols)
  62                                         if (e.getValue() < min.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1)
  63                                                 min = e;
  64                                 //No pets left that have a positive compatibility
  65                                 if (min.getKey() != -1) {
  66                                         cols.remove(min);
  67                                         result[row_l.getKey()] = min.getKey();
  68                                 }
  69                         //2. The column is the lowest
  70                         } else {
  71                                 //Remove the current lowest column sum
  72                                 cols.remove(col_l);
  73                                 //3. Find smallest row that has compatibility 1
  74                                 SimpleEntry<Integer, Integer> min = new SimpleEntry<Integer, Integer>(-1, Integer.MAX_VALUE);
  75                                 for (SimpleEntry<Integer, Integer> e : rows)
  76                                         if (e.getValue() < min.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1)
  77                                                 min = e;
  78                                 //If there is a pet left, remove it and assign it
  79                                 if (min.getKey() != -1) {
  80                                         rows.remove(min);
  81                                         result[min.getKey()] = col_l.getKey();
  82                                 }
  83                         }
  84                 }
  85                 return result;
  86         }
  87 }