From 8e3b1b7c1e3ea5ce334cf6978496a3b6f7b7a434 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Thu, 19 Jun 2014 10:51:13 +0200
Subject: [PATCH] other implementation

---
 LubbersSolver.java | 187 +++++++++++++++++++++++++++++++--------------
 1 file changed, 129 insertions(+), 58 deletions(-)

diff --git a/LubbersSolver.java b/LubbersSolver.java
index 571bb26..a1b88a0 100755
--- a/LubbersSolver.java
+++ b/LubbersSolver.java
@@ -5,6 +5,9 @@ import java.util.Random;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Comparator;
+import java.util.AbstractMap.SimpleEntry;
+import java.util.Comparator;
+import java.util.PriorityQueue;
 
 
 /**
@@ -14,78 +17,146 @@ import java.util.Comparator;
  */
 public class LubbersSolver implements IPetproblemSolver {
 
-	private class Tuple {
-		public int[] list;
-		public int score;
+	public class Tuple implements Comparable<Tuple>
+	{
+		public int k;
+		public int v;
 
-		public Tuple(int[] l, int s) {
-			list = l;
-			score = s;
+		public Tuple(int k, int v)
+		{
+			this.k = k;
+			this.v = v;
 		}
 
+		/**
+		 * Overrides compareTo so that the priorityqueue is ordered ascending
+		 *
+		 * @param a the entry to compare with
+		 * @return comparison value
+		 */
 		@Override
-		public String toString() {
-			return score + ": " + Arrays.toString(list);
+		public int compareTo(Tuple a)
+		{
+			//note that the values are swapped, so that the sort will be reversed
+			return Integer.compare(a.v, this.v);
 		}
-	}
 
-	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++)
+		@Override
+		public String toString()
 		{
-			int m_i = pairing[n_i];
-			if(m_i == -1)
-				continue;
-			sum += matrix[n_i][m_i];
+			return k + ": " + v;
 		}
-		
-		return sum;
 	}
 
-	/**
-	 * 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;
+	public int[] solve(int n, int m, int[][] compatibility)
+	{
+		int[] result = new int[n];
+
+		// Set to -1 initially
+		for (int i = 0; i < result.length; i++)
+			result[i] = -1;
+
+		// Sum rows and columns
+		PriorityQueue<Tuple> row_sums = new PriorityQueue<Tuple>(n);
+		PriorityQueue<Tuple> col_sums = new PriorityQueue<Tuple>(m);
+
+		int[] running_row_sums = new int[n];
+		int[] running_col_sums = new int[m];
+
+		// Sum
+		for (int j = 0; j < m; j++)
+		{
+			for (int i = 0; i < n; i++)
+			{
+				running_row_sums[i] += compatibility[i][j];
+				running_col_sums[j] += compatibility[i][j];
+			}
 		}
 
-		List<int[]> ps = new LinkedList<int[]>();
-		permute(possibilities, 0, ps);
+		// Add running sums to queues
+		for (int i = 0; i < running_row_sums.length; i++)
+			row_sums.add(new Tuple(i, running_row_sums[i]));
+
+		for (int i = 0; i < running_col_sums.length; i++)
+			col_sums.add(new Tuple(i, running_col_sums[i]));
+
 
-		return Collections.max(ps, new Comparator<int[]>(){
-			@Override
-			public int compare(int[] a, int[] b){
-				return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
+		// Select smallest sum (in rows/cols)
+		// Get 1-indices for that sum's index
+		// Select smallest from those indices
+		while (!row_sums.isEmpty() && !col_sums.isEmpty()){
+			Tuple lowestIndexRow = row_sums.peek();
+			Tuple lowestIndexCol = col_sums.peek();
+
+			boolean useRow = false;
+
+			if (lowestIndexRow.v < lowestIndexCol.v)
+				useRow = true;
+
+			// Get 1-indices
+			if (useRow)
+			{
+				row_sums.remove();
+
+				// Get smallest
+				int smallestValue = Integer.MAX_VALUE;
+				Tuple smallestKey = null;
+
+				for (Tuple e : col_sums)
+				{
+					if (e.v < smallestValue && compatibility[lowestIndexRow.k][e.k] == 1)
+					{
+						smallestKey = e;
+						smallestValue = e.v;
+					}
+				}
+
+				// No candidates in this list, continue
+				if (smallestKey == null)
+					continue;
+
+				int col_index = smallestKey.k;
+				col_sums.remove(smallestKey);
+
+				result[lowestIndexRow.k] = col_index;
+			}
+			else
+			{
+				col_sums.remove();
+
+				// Get smallest
+				int smallestValue = Integer.MAX_VALUE;
+				Tuple smallestKey = null;
+
+				for (Tuple e : row_sums)
+				{
+					if (e.v < smallestValue && compatibility[e.k][lowestIndexCol.k] == 1)
+					{
+						smallestKey = e;
+						smallestValue = e.v;
+					}
+				}
+
+				// No candidates in this list, continue
+				if (smallestKey == null)
+					continue;
+
+				int row_index = smallestKey.k;
+				row_sums.remove(smallestKey);
+
+				result[row_index] = lowestIndexCol.k;
 			}
-		});
+		}
+
+		int score = 0;
+
+		for (int i = 0; i < result.length; i++)
+			score += result[i] == -1 ? 0 : 1;
+
+		System.out.println("Score: " + score);
+
+		return result;
 	}
+
 }
-- 
2.20.1