-import java.util.ArrayList;
-import java.util.LinkedList;
-import java.util.Collections;
-import java.util.Random;
+import java.util.AbstractMap.SimpleEntry;
import java.util.Arrays;
-import java.util.List;
+import java.util.Collections;
import java.util.Comparator;
-
+import java.util.LinkedList;
/**
- * Class that implements the pot problem solver.
- *
- * @author Mart Lubbers
+ * Class that implements the pet problem solver.
+ *
+ * @author Mart Lubbers, s4109503
*/
public class LubbersSolver implements IPetproblemSolver {
+ @Override
+ public int[] solve(int n, int m, int[][] compatibility) {
+ // Create initial result list of of length n and fill with -1
+ int[] result = new int[n];
+ Arrays.fill(result, -1);
- private class Tuple {
- public int[] list;
- public int score;
-
- public Tuple(int[] l, int s) {
- list = l;
- score = s;
- }
-
- @Override
- public String toString() {
- return score + ": " + Arrays.toString(list);
- }
- }
+ // Create the lists that define the sums of the rows and columns
+ LinkedList<SimpleEntry<Integer, Integer>> rows = new LinkedList<SimpleEntry<Integer, Integer>>();
+ LinkedList<SimpleEntry<Integer, Integer>> cols = new LinkedList<SimpleEntry<Integer, Integer>>();
- public int factorial(int n) {
- return n==1 ? 1 : n*factorial(n-1);
- }
-
- public void permute(int[] num, int start, List<int[]> result) {
- if(start == num.length) {
- result.add(num.clone());
- }
- for(int i = start; i<num.length; i++){
- int t = num[start];
- num[start] = num[i];
- num[i] = t;
- permute(num, start+1, result);
- t = num[start];
- num[start] = num[i];
- num[i] = t;
- }
- }
-
- private static int computeCompatibility(int[][] matrix, int[] pairing)
- {
- int sum = 0;
- for(int n_i = 0; n_i < pairing.length; n_i++)
- {
- int m_i = pairing[n_i];
- if(m_i == -1)
- continue;
- sum += matrix[n_i][m_i];
+ // Calculate the sums
+ int[] col_sums = new int[m];
+ for (int i = 0, sum = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ sum += compatibility[i][j];
+ col_sums[j] += compatibility[i][j];
+ }
+ rows.add(new SimpleEntry<Integer, Integer>(i, sum));
}
-
- return sum;
- }
+ for (int i = 0; i < m; i++)
+ cols.add(new SimpleEntry<Integer, Integer>(i, col_sums[i]));
- /**
- * Mart Lubbers' implementation of the pet problem
- *
- * @param n the amount of children
- * @param m the amount of pets
- * @param compatibility the compatibility matrix of pets and children
- * @return the optimal distribution of pets and children
- */
- @Override
- public int[] solve(int n, int m, final int[][] compatibility) {
- System.out.println("n: " + n + " m: " + m);
- int[] possibilities = new int[n];
- for(int i = 0; i<n; i++){
- possibilities[i] = i>=m ? -1 : i;
- }
- if(m<=n){
- System.out.println("Wierd shizzleeee");
- List<int[]> ps = new LinkedList<int[]>();
- permute(possibilities, 0, ps);
- for(int[] i : ps){
- System.out.println(computeCompatibility(compatibility, i) + ": " + Arrays.toString(i));
+ //Sort the lists so the rows and columns with the least amount of positive compatibilities are up front
+ Comparator<SimpleEntry<Integer, Integer>> comp = new Comparator<SimpleEntry<Integer, Integer>>() {
+ @Override
+ public int compare(SimpleEntry<Integer, Integer> a, SimpleEntry<Integer, Integer> b) {
+ return a.getValue().compareTo(b.getValue());
}
- System.exit(0);
+ };
+ Collections.sort(rows, comp);
+ Collections.sort(cols, comp);
- return Collections.max(ps, new Comparator<int[]>(){
- @Override
- public int compare(int[] a, int[] b){
- return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
+ /* 1. Find the row or column with the lowest sum(least available matches)
+ * Because the rows and columns are sorted on value the first item is the lowest
+ * 2. Find the match with the lowest sum and still positive compatibility for that row or column
+ * 3. Select smallest from those indices
+ */
+ while (!(rows.isEmpty() || cols.isEmpty())) {
+ //1. Find the row or column with the lowest sum(least available matches)
+ SimpleEntry<Integer, Integer> row_l = rows.peekFirst();
+ SimpleEntry<Integer, Integer> col_l = cols.peekFirst();
+
+ //2. The row is the lowest
+ if (row_l.getValue() < col_l.getValue()) {
+ //Remove the current lowest row sum
+ rows.remove(row_l);
+ //3. Find smallest column that has compatibility 1
+ SimpleEntry<Integer, Integer> min = new SimpleEntry<Integer, Integer>(-1, Integer.MAX_VALUE);
+ for (SimpleEntry<Integer, Integer> e : cols)
+ if (e.getValue() < min.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1)
+ min = e;
+ //No pets left that have a positive compatibility
+ if (min.getKey() != -1) {
+ cols.remove(min);
+ result[row_l.getKey()] = min.getKey();
}
- });
- }
- else {
- System.out.println("not equal...");
- return new int[n];
- //return null;
+ //2. The column is the lowest
+ } else {
+ //Remove the current lowest column sum
+ cols.remove(col_l);
+ //3. Find smallest row that has compatibility 1
+ SimpleEntry<Integer, Integer> min = new SimpleEntry<Integer, Integer>(-1, Integer.MAX_VALUE);
+ for (SimpleEntry<Integer, Integer> e : rows)
+ if (e.getValue() < min.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1)
+ min = e;
+ //If there is a pet left, remove it and assign it
+ if (min.getKey() != -1) {
+ rows.remove(min);
+ result[min.getKey()] = col_l.getKey();
+ }
+ }
}
-
+ return result;
}
}
repositories / co1314.git / blobdiff