Another Google question - drop glassballs from a building 4 博客分类： algorithms 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.