LubbersSolver.java

   1 import java.util.ArrayList;
   2 import java.util.LinkedList;
   3 import java.util.Collections;
   4 import java.util.Random;
   5 import java.util.Arrays;
   6 import java.util.List;
   7 import java.util.Comparator;
   8 import java.util.AbstractMap.SimpleEntry;
   9 import java.util.Comparator;
  10 import java.util.PriorityQueue;
  11
  12
  13 /**
  14  * Class that implements the pot problem solver.
  15  *
  16  * @author Mart Lubbers
  17  */
  18 public class LubbersSolver implements IPetproblemSolver {
  19
  20         public class Tuple implements Comparable<Tuple>
  21         {
  22                 public int k;
  23                 public int v;
  24
  25                 public Tuple(int k, int v)
  26                 {
  27                         this.k = k;
  28                         this.v = v;
  29                 }
  30
  31                 /**
  32                  * Overrides compareTo so that the priorityqueue is ordered ascending
  33                  *
  34                  * @param a the entry to compare with
  35                  * @return comparison value
  36                  */
  37                 @Override
  38                 public int compareTo(Tuple a)
  39                 {
  40                         //note that the values are swapped, so that the sort will be reversed
  41                         return Integer.compare(a.v, this.v);
  42                 }
  43
  44                 @Override
  45                 public String toString()
  46                 {
  47                         return k + ": " + v;
  48                 }
  49         }
  50
  51         @Override
  52         public int[] solve(int n, int m, int[][] compatibility)
  53         {
  54                 int[] result = new int[n];
  55
  56                 // Set to -1 initially
  57                 for (int i = 0; i < result.length; i++)
  58                         result[i] = -1;
  59
  60                 // Sum rows and columns
  61                 PriorityQueue<Tuple> row_sums = new PriorityQueue<Tuple>(n);
  62                 PriorityQueue<Tuple> col_sums = new PriorityQueue<Tuple>(m);
  63
  64                 int[] running_row_sums = new int[n];
  65                 int[] running_col_sums = new int[m];
  66
  67                 // Sum
  68                 for (int j = 0; j < m; j++)
  69                 {
  70                         for (int i = 0; i < n; i++)
  71                         {
  72                                 running_row_sums[i] += compatibility[i][j];
  73                                 running_col_sums[j] += compatibility[i][j];
  74                         }
  75                 }
  76
  77                 // Add running sums to queues
  78                 for (int i = 0; i < running_row_sums.length; i++)
  79                         row_sums.add(new Tuple(i, running_row_sums[i]));
  80
  81                 for (int i = 0; i < running_col_sums.length; i++)
  82                         col_sums.add(new Tuple(i, running_col_sums[i]));
  83
  84
  85                 // Select smallest sum (in rows/cols)
  86                 // Get 1-indices for that sum's index
  87                 // Select smallest from those indices
  88                 while (!row_sums.isEmpty() && !col_sums.isEmpty()){
  89                         Tuple lowestIndexRow = row_sums.peek();
  90                         Tuple lowestIndexCol = col_sums.peek();
  91
  92                         boolean useRow = false;
  93
  94                         if (lowestIndexRow.v < lowestIndexCol.v)
  95                                 useRow = true;
  96
  97                         // Get 1-indices
  98                         if (useRow)
  99                         {
 100                                 row_sums.remove();
 101
 102                                 // Get smallest
 103                                 int smallestValue = Integer.MAX_VALUE;
 104                                 Tuple smallestKey = null;
 105
 106                                 for (Tuple e : col_sums)
 107                                 {
 108                                         if (e.v < smallestValue && compatibility[lowestIndexRow.k][e.k] == 1)
 109                                         {
 110                                                 smallestKey = e;
 111                                                 smallestValue = e.v;
 112                                         }
 113                                 }
 114
 115                                 // No candidates in this list, continue
 116                                 if (smallestKey == null)
 117                                         continue;
 118
 119                                 int col_index = smallestKey.k;
 120                                 col_sums.remove(smallestKey);
 121
 122                                 result[lowestIndexRow.k] = col_index;
 123                         }
 124                         else
 125                         {
 126                                 col_sums.remove();
 127
 128                                 // Get smallest
 129                                 int smallestValue = Integer.MAX_VALUE;
 130                                 Tuple smallestKey = null;
 131
 132                                 for (Tuple e : row_sums)
 133                                 {
 134                                         if (e.v < smallestValue && compatibility[e.k][lowestIndexCol.k] == 1)
 135                                         {
 136                                                 smallestKey = e;
 137                                                 smallestValue = e.v;
 138                                         }
 139                                 }
 140
 141                                 // No candidates in this list, continue
 142                                 if (smallestKey == null)
 143                                         continue;
 144
 145                                 int row_index = smallestKey.k;
 146                                 row_sums.remove(smallestKey);
 147
 148                                 result[row_index] = lowestIndexCol.k;
 149                         }
 150                 }
 151
 152                 int score = 0;
 153
 154                 for (int i = 0; i < result.length; i++)
 155                         score += result[i] == -1 ? 0 : 1;
 156
 157                 System.out.println("Score: " + score);
 158
 159                 return result;
 160         }
 161
 162 }