[jddaniels commit] r172 - in trunk/Facebook_puzzles: src/net/ddaniels/facebook/puzzles test/net/ddaniels/facebook/pu...
codesite...@google.com
Date: Wed Feb 27 23:43:02 2008
New Revision: 172
Added:
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/BruteForceFlipMatrix.java
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Solution.java
Modified:
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Matrix.java
trunk/Facebook_puzzles/test/net/ddaniels/facebook/puzzles/TestGridFlip.java
Log:
more test changes to manage solutions of row minimum sum
Added: trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/BruteForceFlipMatrix.java
==============================================================================
--- (empty file)
+++
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/BruteForceFlipMatrix.java
Wed Feb 27 23:43:02 2008
@@ -0,0 +1,26 @@
+package net.ddaniels.facebook.puzzles;
+
+public class BruteForceFlipMatrix {
+
+ /**
+ * @param args
+ */
+ public static void main(String[] args) {
+ Matrix m = Matrix.fromFile("data/5x5.txt");
+ String summary = findMinPositiveSum(m);
+ System.out.println(summary);
+
+ }
+ /**
+ * Write a program to compute the minimum non-negative value of S
that can
+ * be obtained by a succession of calls to flip_col() and flip_row() such
+ * that all values in SC and SR are also non-negative, and give the shortest
+ * possible sequence of such calls which achieves this value S while
+ * satisfying the non-negative property for all elements in SC and SR.
+ */
+ public static String findMinPositiveSum(Matrix m) {
+ String summary = "";
+
+ return summary;
+ }
+}
Modified: trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Matrix.java
==============================================================================
---
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Matrix.java (original)
+++
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Matrix.java
Wed Feb 27 23:43:02 2008
@@ -4,7 +4,10 @@
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Set;
import java.util.StringTokenizer;
+import java.util.TreeSet;
public class Matrix {
@@ -227,6 +230,85 @@
}
}
return false;
+ }
+
+ /**
+ * Returns an array of bit vectors representing the sign flips needed
to provide a minimal
+ * positive sum for the row.
+ */
+ public Set<Solution> findRowMinSumSolutions(int row) {
+ int[] selectedRow = matrix[row];
+ Set<Solution> solutions = null;
+ Solution defaultSolution = new Solution();
+ defaultSolution.flipBitVector = new BitSet(selectedRow.length);
+ //We want to find a minimal positive sum closes to 0 which would
mean half the sum is cancelled out
+ int minSum = sum(selectedRow)/2;
+ defaultSolution.minSum = minSum;
+
+ solutions = findRowMinSumSolutionsRecursive(selectedRow,
selectedRow.length-1, (Solution)defaultSolution.clone());
+
+ return solutions;
+ }
+ /**
+ * The row sum with the bits flipped
+ */
+ public int SRBitFlip(int row, BitSet bitFlipVector) {
+ int[] selectedRow = matrix[row];
+ int sum = 0;
+ for(int i=0; i<selectedRow.length; i++) {
+ int val = selectedRow[i];
+ //Flip the sign if it's set
+ if(bitFlipVector.get(i)) {
+ val = -val;
+ }
+ sum += val;
+ }
+ return sum;
+ }
+ private Set<Solution> findRowMinSumSolutionsRecursive(
+ int[] selectedRow,
+ int end,
+ Solution currentSolution) {
+
+ Set<Solution> returnSolutions = new TreeSet<Solution>();
+ returnSolutions.add(currentSolution);
+ int newMinSum = currentSolution.minSum-Math.abs(selectedRow[end]);
+ if(newMinSum>=0) {
+ //We need to make it negative if the number is positive
+ if(selectedRow[end]>0) {
+ currentSolution.flipBitVector.set(end);
+ }
+ // We found a lower minimum sum so set it
+ currentSolution.minSum = newMinSum;
+ }
+ // We're at a leaf solution so return it
+ if(end == 0) {
+ returnSolutions.clear();
+ returnSolutions.add(currentSolution);
+
+ } else {
+ end--;
+ for(int i=end; i>=0; i--) {
+ Set<Solution> solutions =
findRowMinSumSolutionsRecursive(selectedRow, end, (Solution)currentSolution.clone());
+ if(solutions.size() == 0 ||
solutions.iterator().next().minSum==returnSolutions.iterator().next().minSum) {
+ returnSolutions.addAll(solutions);
+ }
+ //If we found solutions with a lower min sum then clear out the
existing solutions
+ else if(solutions.iterator().next().minSum <
returnSolutions.iterator().next().minSum ) {
+ returnSolutions.clear();
+ returnSolutions.addAll(solutions);
+ }
+ }
+ }
+ return returnSolutions;
+
+ }
+ private int sum(int[] selectedRow) {
+ int sum = 0;
+ for(int i=0; i<selectedRow.length;i++){
+ sum += selectedRow[i];
+ }
+ return sum;
}
@Override
public boolean equals(Object o) {
Added: trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Solution.java
==============================================================================
--- (empty file)
+++
trunk/Facebook_puzzles/src/net/ddaniels/facebook/puzzles/Solution.java
Wed Feb 27 23:43:02 2008
@@ -0,0 +1,47 @@
+package net.ddaniels.facebook.puzzles;
+
+import java.util.BitSet;
+
+public class Solution implements Comparable {
+
+
+ public int minSum = Integer.MAX_VALUE;
+ public BitSet flipBitVector = new BitSet();
+ @Override
+ public boolean equals(Object o) {
+ if(this == o) {
+ return true;
+ }
+ else if(o instanceof Solution) {
+ Solution sol = (Solution)o;
+ if(sol.minSum == this.minSum &&
sol.flipBitVector.equals(this.flipBitVector)) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+ @Override
+ public Object clone() {
+ Solution s = new Solution();
+ s.minSum = this.minSum;
+ s.flipBitVector = (BitSet) this.flipBitVector.clone();
+
+ return s;
+ }
+ public int compareTo(Object o) {
+ if(o instanceof Solution) {
+ Solution s = (Solution)o;
+ if(s.minSum < this.minSum) {
+ return -1;
+ }
+ if(s.minSum > this.minSum) {
+ return 1;
+ }
+ else {
+ return 0;
+ }
+ }
+ return -1;
+ }
+}
Modified: trunk/Facebook_puzzles/test/net/ddaniels/facebook/puzzles/TestGridFlip.java
==============================================================================
---
trunk/Facebook_puzzles/test/net/ddaniels/facebook/puzzles/TestGridFlip.java (original)
+++
trunk/Facebook_puzzles/test/net/ddaniels/facebook/puzzles/TestGridFlip.java
Wed Feb 27 23:43:02 2008
@@ -1,7 +1,12 @@
package net.ddaniels.facebook.puzzles;
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+
+import java.util.BitSet;
+import java.util.Iterator;
+import java.util.Set;
import java.util.logging.Logger;
+
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
@@ -95,7 +100,16 @@
@Test
public void testMinPositiveSum() {
- int[] elements = {1, 3, 3, 4, 6};
+
+ int[] elements = {1, 1, 2, 4, 8};
+ Matrix matrix = new Matrix(elements);
+
+ Set<Solution> solutions = matrix.findRowMinSumSolutions(0);
+ Iterator iter = solutions.iterator();
+ for(int i=0; i<solutions.size(); i++) {
+ Solution s = (Solution)iter.next();
+ logger.info("SolutionSum["+i+"]=" + matrix.SRBitFlip(0,
s.flipBitVector) + " BitVector="+s.flipBitVector);
+ }
}
}