PetTest.java

   1 import org.junit.Test;
   2 import org.junit.runner.RunWith;
   3 import org.junit.runners.Parameterized;
   4 import org.junit.runners.Parameterized.Parameters;
   5
   6 import java.util.Arrays;
   7 import java.util.Collection;
   8 import java.util.Random;
   9 import java.util.TreeSet;
  10
  11 import junit.framework.Assert;
  12
  13 /**
  14  * Tests conformance of a Solver to constraints.
  15  * May not test whether a solution returns a correct (optimal) answer.
  16  */
  17 @RunWith(Parameterized.class)
  18 public class PetTest {
  19         IPetproblemSolver ps;
  20
  21         public PetTest(IPetproblemSolver ps)
  22         {
  23                 this.ps = ps;
  24         }
  25
  26         @Parameters
  27         public static Collection<Object[]> data() {
  28                 Object[][] solvers = new Object[][] {
  29                                 { //new RandomSolver(),
  30                                         new LubbersSolver()
  31                                 }
  32                 };
  33                 return Arrays.asList(solvers);
  34         }
  35
  36         /**
  37          * @param n The number of children.
  38          * @param m The number of pets.
  39          * @param result
  40          */
  41         private static void checkConformance(int n, int m, final int[] result)
  42         {
  43                 Assert.assertEquals("There should not suddenly be more or less children.", n, result.length);
  44
  45                 TreeSet<Integer> pets = new TreeSet<Integer>();
  46                 for(int i = 0; i < result.length; i++)
  47                 {
  48                         Assert.assertTrue("Pet should exist, or be a no-pet (-1).", result[i] >= -1 && result[i] < m);
  49                         Assert.assertTrue("Pet should not be assigned to multiple children.", result[i] == -1 || pets.add(result[i]));
  50                 }
  51         }
  52
  53         private static int[][] generateTestMatrix(int n, int m, int maxValue)
  54         {
  55                 int[][] result = new int[n][m];
  56
  57                 Random r = new Random(n * (m+1));
  58                 for(int n_i = 0; n_i < n; n_i++)
  59                         for(int m_i = 0; m_i < m; m_i++)
  60                                 result[n_i][m_i] = r.nextInt(maxValue+1);
  61
  62                 return result;
  63         }
  64
  65         private static int computeCompatibility(int[][] matrix, int[] pairing)
  66         {
  67                 int sum = 0;
  68                 for(int n_i = 0; n_i < pairing.length; n_i++)
  69                 {
  70                         int m_i = pairing[n_i];
  71                         if(m_i == -1)
  72                                 continue;
  73
  74                         sum += matrix[n_i][m_i];
  75                 }
  76
  77                 return sum;
  78         }
  79
  80         /**
  81          * Test whether Solver conforms for a semi-random test set.
  82          * Note that these tests do not test whether a solution is optimal.
  83          * (If it could do that the test would be a Solver by itself)
  84          */
  85         private void performGeneratedTest(int n, int m)
  86         {
  87                 int[][] compatibility = generateTestMatrix(n, m, 1);
  88                 int[] result = ps.solve(n, m, compatibility);
  89                 checkConformance(n, m, result);
  90         }
  91
  92         @Test(timeout = 10000)
  93         public void testExample() {
  94                 int n = 5, m = 4;
  95                 int[][] compatibility = {
  96                         {1, 1, 0, 0},
  97                         {0, 1, 1, 1},
  98                         {0, 1, 0, 0},
  99                         {1, 0, 1, 0},
 100                         {0, 0, 1, 1}
 101                 };
 102
 103                 int[] result = ps.solve(n, m, compatibility);
 104                 checkConformance(n, m, result);
 105                 Assert.assertEquals("Does not give a correct answer", 4, computeCompatibility(compatibility, result));
 106         }
 107
 108         @Test(timeout = 10000)
 109         public void testGeneratedSmall() {
 110                 performGeneratedTest(8, 10);
 111                 performGeneratedTest(10, 8);
 112         }
 113
 114         @Test(timeout = 10000)
 115         public void testGeneratedMedium() {
 116                 performGeneratedTest(23, 20);
 117                 performGeneratedTest(20, 23);
 118         }
 119
 120         @Test(timeout = 10000)
 121         public void testGeneratedLarge() {
 122                 performGeneratedTest(121, 130);
 123                 performGeneratedTest(130, 121);
 124         }
 125
 126         /**
 127          * This timeout is just a suggestion,
 128          * your solution is not incorrect if it takes longer,
 129          * or if it is not capable to finish in a reasonable amount of time.
 130          */
 131         @Test(timeout = 10000)
 132         public void testGeneratedTerrible() {
 133                 performGeneratedTest(2910, 3102);
 134                 performGeneratedTest(3102, 2910);
 135         }
 136 }