`

Another Google question - drop glassballs from a building 4

Googlejunit 
阅读更多
The test cases are divided into 3 classes.

The first one is just a pinpoint test class that contains some corner cases:

java 代码
 
  1. package glassball;  
  2.   
  3. import junit.framework.TestCase;  
  4. import java.util.List;  
  5.   
  6. /** 
  7.  * Testcases for path. 
  8.  */  
  9. public class PathFinderTest extends TestCase  
  10. {  
  11.     public void test1BallSingleCase()  
  12.     {  
  13.         int broken = 10;  
  14.         Building building = new Building(10, broken);  
  15.         PathFinder finder = new PathFinder(building, 1);  
  16.         List path = finder.findPuzzlePath();  
  17.         TestUtil.printPath(path);  
  18.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  19.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  20.     }  
  21.   
  22.     public void test2BallSingleCase1()  
  23.     {  
  24.         // 70 is the beginning of the 2nd level search  
  25.         int broken = 70;  
  26.         Building building = new Building(100, broken);  
  27.         PathFinder finder = new PathFinder(building, 2);  
  28.         List path = finder.findPuzzlePath();  
  29.         TestUtil.printPath(path);  
  30.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  31.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  32.     }  
  33.   
  34.     public void test2BallSingleCase2()  
  35.     {  
  36.         // 77 is the end of the 2nd level search.  
  37.         // 77 jumps out of the loop without going to return line.  
  38.         int broken = 77;  
  39.         Building building = new Building(100, broken);  
  40.         PathFinder finder = new PathFinder(building, 2);  
  41.         List path = finder.findPuzzlePath();  
  42.         TestUtil.printPath(path);  
  43.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  44.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  45.     }  
  46.   
  47.     public void test3BallSingleCase()  
  48.     {  
  49.         int broken = 53;  
  50.         Building building = new Building(100, broken);  
  51.         PathFinder finder = new PathFinder(building, 3);  
  52.         List path = finder.findPuzzlePath();  
  53.         TestUtil.printPath(path);  
  54.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  55.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  56.     }  
  57.   
  58.     public void test4BallSingleCase()  
  59.     {  
  60.         // 89 is a special number to test whether  
  61.         // totalFloors == baseFloor + totalFloors, it caused  
  62.         // 91 has been hit 3 times. Without this check, it kills 3 balls.  
  63.         int broken = 89;  
  64.         Building building = new Building(100, broken);  
  65.         PathFinder finder = new PathFinder(building, 4);  
  66.         List path = finder.findPuzzlePath();  
  67.         TestUtil.printPath(path);  
  68.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  69.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  70.     }  
  71.   
  72.     public void test4BallForLowerBound1()  
  73.     {  
  74.         int broken = 1;  
  75.         Building building = new Building(10, broken);  
  76.         PathFinder finder = new PathFinder(building, 4);  
  77.         List path = finder.findPuzzlePath();  
  78.         TestUtil.printPath(path);  
  79.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  80.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  81.     }  
  82.   
  83.     public void test4BallForLowerBound2()  
  84.     {  
  85.         int broken = 2;  
  86.         Building building = new Building(10, broken);  
  87.         PathFinder finder = new PathFinder(building, 4);  
  88.         List path = finder.findPuzzlePath();  
  89.         TestUtil.printPath(path);  
  90.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  91.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  92.     }  
  93.   
  94.     public void test4BallForLowerBound3()  
  95.     {  
  96.         int broken = 6;  
  97.         Building building = new Building(10, broken);  
  98.         PathFinder finder = new PathFinder(building, 4);  
  99.         List path = finder.findPuzzlePath();  
  100.         TestUtil.printPath(path);  
  101.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  102.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  103.     }  
  104.   
  105.     public void test2Ball4Floors()  
  106.     {  
  107.         int broken = 1;  
  108.         Building building = new Building(4, broken);  
  109.         PathFinder finder = new PathFinder(building, 2);  
  110.         List path = finder.findPuzzlePath();  
  111.         TestUtil.printPath(path);  
  112.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  113.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  114.     }  
  115.   
  116.     public void test3Ball17Floors()  
  117.     {  
  118.         int broken = 13;  
  119.         Building building = new Building(17, broken);  
  120.         PathFinder finder = new PathFinder(building, 3);  
  121.         List path = finder.findPuzzlePath();  
  122.         TestUtil.printPath(path);  
  123.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  124.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  125.     }  
  126.   
  127.     public void test4Ball100Floors()  
  128.     {  
  129.         int broken = 70;  
  130.         Building building = new Building(100, broken);  
  131.         PathFinder finder = new PathFinder(building, 4);  
  132.         List path = finder.findPuzzlePath();  
  133.         TestUtil.printPath(path);  
  134.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  135.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  136.     }  
  137.   
  138.     public void test5Ball100Floors()  
  139.     {  
  140.         int broken = 70;  
  141.         Building building = new Building(100, broken);  
  142.         PathFinder finder = new PathFinder(building, 5);  
  143.         List path = finder.findPuzzlePath();  
  144.         TestUtil.printPath(path);  
  145.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  146.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  147.     }  
  148.   
  149.     public void test6Ball100Floors()  
  150.     {  
  151.         int broken = 70;  
  152.         Building building = new Building(100, broken);  
  153.         PathFinder finder = new PathFinder(building, 6);  
  154.         List path = finder.findPuzzlePath();  
  155.         TestUtil.printPath(path);  
  156.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  157.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  158.     }  
  159.   
  160.     public void test3Ball9Floors()  
  161.     {  
  162.         int broken = 9;  
  163.         Building building = new Building(100, broken);  
  164.         PathFinder finder = new PathFinder(building, 3);  
  165.         List path = finder.findPuzzlePath();  
  166.         TestUtil.printPath(path);  
  167.         assertTrue(broken == TestUtil.getBrokenFloor(path));  
  168.         assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  169.     }  
  170. }  

The util class is like this:

java 代码
 
  1. package glassball;  
  2.   
  3. import java.util.List;  
  4.   
  5. /** 
  6.  * 
  7.  */  
  8. public class TestUtil  
  9. {  
  10.     public static void printPath(List path)  
  11.     {  
  12.         System.out.print("path=");  
  13.         for (int i=0; i<path.size(); i++)  
  14.         {  
  15.             System.out.print(path.get(i).toString() + "-->");  
  16.         }  
  17.         System.out.println("END");  
  18.         System.out.println("number of trials=" + path.size());  
  19.     }  
  20.   
  21.     public static int getPathSize(List path)  
  22.     {  
  23.         int size = 0;  
  24.         for (int i=0; i<path.size(); i++)  
  25.         {  
  26.             Trial trial = (Trial)path.get(i);  
  27.             if (!trial.isDeducted()) size++;  
  28.         }  
  29.   
  30.         return size;  
  31.     }  
  32.       
  33.     public static int getBrokenFloor(List path)  
  34.     {  
  35.         // several cases:  
  36.         // 1. the last one is broken,  
  37.         // 2. the last broken is before several wholes.  
  38.         // 3. all are broken, the one we are looking for is not in the list because:  
  39.         //     it's the last one.  
  40.         for (int i=path.size()-1; i>=0; i--)  
  41.         {  
  42.             Trial trial = (Trial)path.get(i);  
  43.             // The last broken piece is the one we are looking for.  
  44.             if (trial.isBroken()) return trial.getFloor();  
  45.         }  
  46.         return -1;  
  47.     }  
  48.   
  49.     public static boolean compareTwoIntegerArrays(List path1, List path2)  
  50.     {  
  51.         if (path1.size() != path2.size()) return false;  
  52.   
  53.         for (int i=0; i<path1.size(); i++)  
  54.         {  
  55.             if (path1.get(i).equals(path2.get(i))) return false;  
  56.         }  
  57.   
  58.         return true;  
  59.     }  
  60. }  


The second one is to vary the broken level to see whether it's good enough:

java 代码
 
  1. package glassball;  
  2.   
  3. import junit.framework.TestCase;  
  4.   
  5. import java.util.List;  
  6.   
  7. /** 
  8.  * This is to test the minimal trial numbers. 
  9.  */  
  10. public class PathFinderMinimalFullTest extends TestCase  
  11. {  
  12.     public void test3Ball100Floors()  
  13.     {  
  14.         int numOfTrials = 0;  
  15.   
  16.         for (int broken=1; broken < 100; broken++)  
  17.         {  
  18.             Building building = new Building(100, broken);  
  19.             PathFinder finder = new PathFinder(building, 3);  
  20.             List path = finder.findPuzzlePath();  
  21.   
  22.             if (TestUtil.getPathSize(path) > numOfTrials)  
  23.                 numOfTrials = TestUtil.getPathSize(path);  
  24.   
  25.             TestUtil.printPath(path);  
  26.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  27.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  28.         }  
  29.   
  30.         System.out.println("numOfTrials=" + numOfTrials);  
  31.     }  
  32.   
  33.     public void test4Ball100Floors()  
  34.     {  
  35.         int numOfTrials = 0;  
  36.   
  37.         for (int broken=1; broken < 100; broken++)  
  38.         {  
  39.             Building building = new Building(100, broken);  
  40.             PathFinder finder = new PathFinder(building, 4);  
  41.             List path = finder.findPuzzlePath();  
  42.   
  43.             if (TestUtil.getPathSize(path) > numOfTrials)  
  44.                 numOfTrials = TestUtil.getPathSize(path);  
  45.   
  46.             TestUtil.printPath(path);  
  47.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  48.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  49.         }  
  50.   
  51.         System.out.println("numOfTrials=" + numOfTrials);  
  52.     }  
  53.   
  54.     public void test5Ball100Floors()  
  55.     {  
  56.         int numOfTrials = 0;  
  57.   
  58.         for (int broken=1; broken < 100; broken++)  
  59.         {  
  60.             Building building = new Building(100, broken);  
  61.             PathFinder finder = new PathFinder(building, 5);  
  62.             List path = finder.findPuzzlePath();  
  63.   
  64.             if (TestUtil.getPathSize(path) > numOfTrials)  
  65.                 numOfTrials = TestUtil.getPathSize(path);  
  66.   
  67.             TestUtil.printPath(path);  
  68.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  69.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  70.         }  
  71.   
  72.         System.out.println("numOfTrials=" + numOfTrials);  
  73.     }  
  74.   
  75.     public void test5Ball1000Floors()  
  76.     {  
  77.         int numOfTrials = 0;  
  78.   
  79.         for (int broken=1; broken < 200; broken++)  
  80.         {  
  81.             Building building = new Building(200, broken);  
  82.             PathFinder finder = new PathFinder(building, 5);  
  83.             List path = finder.findPuzzlePath();  
  84.   
  85.             if (TestUtil.getPathSize(path) > numOfTrials)  
  86.                 numOfTrials = TestUtil.getPathSize(path);  
  87.   
  88.             TestUtil.printPath(path);  
  89.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  90.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  91.         }  
  92.   
  93.         System.out.println("numOfTrials=" + numOfTrials);  
  94.     }  
  95.   
  96.     public void test6Ball1000Floors()  
  97.     {  
  98.         int numOfTrials = 0;  
  99.   
  100.         for (int broken=1; broken < 200; broken++)  
  101.         {  
  102.             Building building = new Building(200, broken);  
  103.             PathFinder finder = new PathFinder(building, 6);  
  104.             List path = finder.findPuzzlePath();  
  105.   
  106.             if (TestUtil.getPathSize(path) > numOfTrials)  
  107.                 numOfTrials = TestUtil.getPathSize(path);  
  108.   
  109.             TestUtil.printPath(path);  
  110.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  111.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  112.         }  
  113.   
  114.         System.out.println("numOfTrials=" + numOfTrials);  
  115.     }  
  116.   
  117.     public void test10Ball1000Floors()  
  118.     {  
  119.         int numOfTrials = 0;  
  120.   
  121.         for (int broken=1; broken < 200; broken++)  
  122.         {  
  123.             Building building = new Building(200, broken);  
  124.             PathFinder finder = new PathFinder(building, 50);  
  125.             List path = finder.findPuzzlePath();  
  126.   
  127.             if (TestUtil.getPathSize(path) > numOfTrials)  
  128.                 numOfTrials = TestUtil.getPathSize(path);  
  129.   
  130.             TestUtil.printPath(path);  
  131.             assertTrue(broken == TestUtil.getBrokenFloor(path));  
  132.             assertTrue(TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  133.         }  
  134.   
  135.         System.out.println("numOfTrials=" + numOfTrials);  
  136.     }  
  137. }  

The third one is a brutal force testing to test all cases in a certain range:

java 代码
 
  1. package glassball;  
  2.   
  3. import junit.framework.TestCase;  
  4.   
  5. import java.util.List;  
  6.   
  7. /** 
  8.  * The brutal force loops. 
  9.  */  
  10. public class PathFinderFullTest extends TestCase  
  11. {  
  12.     public void test1BallSingleCase()  
  13.     {  
  14.         for (int floors=3; floors<=300; floors++)  
  15.         {  
  16.             for (int broken=1; broken<floors; broken++)  
  17.             {  
  18.                 for (int balls=1; balls<6; balls++)  
  19.                 {  
  20.                     Building building = new Building(floors, broken);  
  21.                     PathFinder finder = new PathFinder(building, balls);  
  22.                     List path = finder.findPuzzlePath();  
  23.   
  24.                     //TestUtil.printPath(path);  
  25.                     String errorMsg = "floors=" + floors + " broken=" + broken + " balls=" + balls;  
  26.                     errorMsg += " path size=" + TestUtil.getPathSize(path) + " minimal trials=" +  
  27.                                 finder.getPuzzle().getMinimalTrials();  
  28.                     errorMsg += " result floor=" + TestUtil.getBrokenFloor(path);  
  29.                     assertTrue(errorMsg, TestUtil.getPathSize(path) <= finder.getPuzzle().getMinimalTrials());  
  30.                     assertTrue(errorMsg, broken == TestUtil.getBrokenFloor(path));  
  31.                 }  
  32.             }  
  33.         }  
  34.     }  
  35. }  

Now we should have enough confidence.
分享到：
| Another Google question - drop glassbal ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics