-
|
I can pass all the test sometimes, but sometimes there is wrong test case for |
Beta Was this translation helpful? Give feedback.
Replies: 4 comments 5 replies
-
|
I will do my utmost. Please wait for a few days. I've quickly reviewed your Wishing you a good day! |
Beta Was this translation helpful? Give feedback.
-
|
Thank you very much 👍 |
Beta Was this translation helpful? Give feedback.
-
|
I have just reviewed this discussion. I reproduced this problem with your code and also failed to pass these two test cases when testing my own code in my local machine, and the error points are exactly the same as yours. But I think there is no problem with your code. Here is my explanation. First of all, I think the situation you mentioned that GradeScope sometimes passes and sometimes fails is because the test cases of GradeScope are randomly selected according to Professor Hug (He has mentioned that there are a few students choosing to use great quantities of if-else to cover as many test cases as possible rather than coming up with the correct algorithm to pass the autograder). That is to say, the shortest path generated by your code will not change, but the test cases are always changing. Sometimes the test cases you encounter when submitting cause errors (i.e. these two cases), sometimes do not, so it passes smoothly. Then I checked the specific situation of these two test cases. Here is an example of your first test case. I wrote a @Test
public void testShortestPathAG() throws Exception {
Map<String, Double> testParam = new HashMap<>();
// end_lat=37.82769961829141, start_lon=-122.28525299251741,
// start_lat=37.85193141952368, end_lon=-122.23869943366023
testParam.put("end_lat", 37.82769961829141);
testParam.put("start_lon", -122.28525299251741);
testParam.put("start_lat", 37.85193141952368);
testParam.put("end_lon", -122.23869943366023);
List<Long> expectedResults = new ArrayList<>();
List<Long> actual = new ArrayList<>();
Long[] expectedArrays = new Long[]{2421788578L, 2421788572L, 4235206881L, 53119692L,
4235206880L, 4235206867L, 53042100L, 4235206864L, 2421788562L, 4235206857L,
53109978L, 4235206856L, 73991090L, 430994090L, 430994091L, 2421788520L, 430994092L,
73991098L, 430994093L, 2421788570L, 73991104L, 394196514L, 394196515L, 394196516L,
4235206860L, 53047311L, 4235206852L, 53047313L, 53138574L, 4235206851L, 394196538L,
53100729L, 394196539L, 687179342L, 53024605L, 4235206811L, 53024607L, 4235206809L,
4168260358L, 4235206801L, 53050642L, 4235206796L, 53050644L, 302803293L, 1994957632L,
53085427L, 53085428L, 53085430L, 240469482L, 4559569772L, 240469597L, 240469840L, 4559569767L,
1237053660L, 240469594L, 240469592L, 1237053718L, 1994957647L, 240469473L, 240469672L, 430992573L,
53090197L, 430992572L, 2240045667L, 53112624L, 2240045668L, 1237053724L, 1237053736L, 95323761L,
95323768L, 1237053613L, 95323772L, 1237053560L, 2375208693L, 95323788L, 1475224966L, 1237053611L,
53092590L, 1237053577L, 4169996317L, 2352069432L, 266434139L, 53126702L, 1237053620L, 266434152L,
53079228L, 4169996314L, 280431894L, 1203807993L, 4169996311L, 4169996312L, 5060959013L, 5060959012L,
53045882L, 92984207L, 271855224L, 506459086L, 95164561L, 3969482338L, 4918915965L, 4918915970L,
506459075L, 302801977L, 682403904L, 212465291L, 3969482340L, 3969482339L, 212465293L, 302801863L,
506458647L, 2430670764L, 302801824L, 506458653L, 53099316L, 694066168L, 694066169L, 3127028848L,
4169996306L, 694066171L, 694066172L, 694066174L, 694066175L, 4169996304L, 694066160L, 4169996303L,
694066163L, 694066176L, 694066177L, 694066178L, 694066179L, 694066180L, 694066149L, 694066181L,
4168192178L, 694066153L, 694066182L, 694066183L, 4168192176L, 694066156L, 694066184L, 694066185L,
4168192174L, 1003274388L, 694066082L, 694066083L, 694066084L, 694066085L, 4168192172L, 694066087L,
694066088L, 694066079L, 694066089L, 694066090L, 694066091L, 694066092L, 694066093L, 694066094L,
694066096L, 694066097L, 694066098L, 694066099L, 694066100L, 694066101L, 53112641L, 957600270L,
53134475L, 2932394300L, 2932394322L, 2932394321L, 2932394317L, 899950046L, 3695372188L,
53038057L, 4671608616L, 247141147L, 4671608614L, 899953916L, 247141146L, 53147548L, 4671608612L,
4671608609L, 311881848L, 206093625L, 201496240L, 4168192169L, 4671608607L, 53075606L, 687156431L,
4671608604L, 53076244L, 4671608602L, 53076245L, 4671608605L, 53076246L, 53076247L, 2834093713L,
260707354L, 53076250L, 53041668L, 697180303L, 697180302L, 260707356L, 697180301L, 260707355L,
697180300L, 2834093720L, 53060461L, 260707363L, 697180298L, 60742947L, 2834816929L, 60742945L};
for (long nodeId : expectedArrays) {
expectedResults.add(nodeId);
}
int iter = 100;
for (int i = 0; i < iter; i += 1) {
System.out.println(String.format("Running test: %d", i));
actual = Router.shortestPath(graph,
testParam.get("start_lon"), testParam.get("start_lat"),
testParam.get("end_lon"), testParam.get("end_lat"));
assertEquals("expected and actual share the same size", expectedResults.size(), actual.size());
for (int j = 0; j < actual.size(); j += 1) {
System.out.print(j + ". " + actual.get(j) + " " + expectedResults.get(j) + " ");
System.out.println(actual.get(j).equals(expectedResults.get(j)));
}
assertEquals("Your results did not match the expected results", expectedResults, actual);
}
}The result is as follows. Running test: 0
0. actual: 2421788578 expected: 2421788578 true
1. actual: 2421788572 expected: 2421788572 true
2. actual: 4235206881 expected: 4235206881 true
3. actual: 53119692 expected: 53119692 true
4. actual: 4235206880 expected: 4235206880 true
5. actual: 4235206867 expected: 4235206867 true
6. actual: 53042100 expected: 53042100 true
7. actual: 4235206864 expected: 4235206864 true
8. actual: 2421788562 expected: 2421788562 true
9. actual: 4235206857 expected: 4235206857 true
10. actual: 53109978 expected: 53109978 true
11. actual: 4235206856 expected: 4235206856 true
12. actual: 73991090 expected: 73991090 true
13. actual: 430994090 expected: 430994090 true
14. actual: 430994091 expected: 430994091 true
15. actual: 2421788520 expected: 2421788520 true
16. actual: 430994092 expected: 430994092 true
17. actual: 73991098 expected: 73991098 true
18. actual: 430994093 expected: 430994093 true
19. actual: 2421788570 expected: 2421788570 true
20. actual: 73991104 expected: 73991104 true
21. actual: 394196514 expected: 394196514 true
22. actual: 394196515 expected: 394196515 true
23. actual: 394196516 expected: 394196516 true
24. actual: 4235206860 expected: 4235206860 true
25. actual: 53047311 expected: 53047311 true
26. actual: 4235206852 expected: 4235206852 true
27. actual: 53047313 expected: 53047313 true
28. actual: 53138574 expected: 53138574 true
29. actual: 4235206851 expected: 4235206851 true
30. actual: 394196538 expected: 394196538 true
31. actual: 53100729 expected: 53100729 true
32. actual: 394196539 expected: 394196539 true
33. actual: 687179342 expected: 687179342 true
34. actual: 53024605 expected: 53024605 true
35. actual: 4235206811 expected: 4235206811 true
36. actual: 53024607 expected: 53024607 true
37. actual: 4235206809 expected: 4235206809 true
38. actual: 4168260358 expected: 4168260358 true
39. actual: 4235206801 expected: 4235206801 true
40. actual: 53050642 expected: 53050642 true
41. actual: 4235206796 expected: 4235206796 true
42. actual: 53050644 expected: 53050644 true
43. actual: 302803293 expected: 302803293 true
44. actual: 1994957632 expected: 1994957632 true
45. actual: 53085427 expected: 53085427 true
46. actual: 53085428 expected: 53085428 true
47. actual: 53085430 expected: 53085430 true
48. actual: 4559569771 expected: 240469482 false
49. actual: 53085432 expected: 4559569772 false
50. actual: 4559569769 expected: 240469597 false
51. actual: 53041552 expected: 240469840 false
52. actual: 92951634 expected: 4559569767 false
53. actual: 1237053638 expected: 1237053660 false
54. actual: 53085433 expected: 240469594 false
55. actual: 92951507 expected: 240469592 false
56. actual: 1237053582 expected: 1237053718 false
57. actual: 53085434 expected: 1994957647 false
58. actual: 53085437 expected: 240469473 false
59. actual: 240469672 expected: 240469672 true
60. actual: 430992573 expected: 430992573 true
61. actual: 53090197 expected: 53090197 true
62. actual: 430992572 expected: 430992572 true
63. actual: 2240045667 expected: 2240045667 true
64. actual: 53112624 expected: 53112624 true
65. actual: 2240045668 expected: 2240045668 true
66. actual: 1237053724 expected: 1237053724 true
67. actual: 1237053736 expected: 1237053736 true
68. actual: 95323761 expected: 95323761 true
69. actual: 95323768 expected: 95323768 true
70. actual: 1237053613 expected: 1237053613 true
71. actual: 95323772 expected: 95323772 true
72. actual: 1237053560 expected: 1237053560 true
73. actual: 2375208693 expected: 2375208693 true
74. actual: 95323788 expected: 95323788 true
75. actual: 1475224966 expected: 1475224966 true
76. actual: 1237053611 expected: 1237053611 true
77. actual: 53092590 expected: 53092590 true
78. actual: 1237053577 expected: 1237053577 true
79. actual: 4169996317 expected: 4169996317 true
80. actual: 2352069432 expected: 2352069432 true
81. actual: 266434139 expected: 266434139 true
82. actual: 53126702 expected: 53126702 true
83. actual: 1237053620 expected: 1237053620 true
84. actual: 266434152 expected: 266434152 true
85. actual: 53079228 expected: 53079228 true
86. actual: 4169996314 expected: 4169996314 true
87. actual: 280431894 expected: 280431894 true
88. actual: 1203807993 expected: 1203807993 true
89. actual: 4169996311 expected: 4169996311 true
90. actual: 4169996312 expected: 4169996312 true
91. actual: 5060959013 expected: 5060959013 true
92. actual: 5060959012 expected: 5060959012 true
93. actual: 53045882 expected: 53045882 true
94. actual: 92984207 expected: 92984207 true
95. actual: 271855224 expected: 271855224 true
96. actual: 506459086 expected: 506459086 true
97. actual: 95164561 expected: 95164561 true
98. actual: 3969482338 expected: 3969482338 true
99. actual: 4918915965 expected: 4918915965 true
100. actual: 4918915970 expected: 4918915970 true
101. actual: 506459075 expected: 506459075 true
102. actual: 302801977 expected: 302801977 true
103. actual: 682403904 expected: 682403904 true
104. actual: 212465291 expected: 212465291 true
105. actual: 3969482340 expected: 3969482340 true
106. actual: 3969482339 expected: 3969482339 true
107. actual: 212465293 expected: 212465293 true
108. actual: 302801863 expected: 302801863 true
109. actual: 506458647 expected: 506458647 true
110. actual: 2430670764 expected: 2430670764 true
111. actual: 302801824 expected: 302801824 true
112. actual: 506458653 expected: 506458653 true
113. actual: 53099316 expected: 53099316 true
114. actual: 694066168 expected: 694066168 true
115. actual: 694066169 expected: 694066169 true
116. actual: 3127028848 expected: 3127028848 true
117. actual: 4169996306 expected: 4169996306 true
118. actual: 694066171 expected: 694066171 true
119. actual: 694066172 expected: 694066172 true
120. actual: 694066174 expected: 694066174 true
121. actual: 694066175 expected: 694066175 true
122. actual: 4169996304 expected: 4169996304 true
123. actual: 694066160 expected: 694066160 true
124. actual: 4169996303 expected: 4169996303 true
125. actual: 694066163 expected: 694066163 true
126. actual: 694066176 expected: 694066176 true
127. actual: 694066177 expected: 694066177 true
128. actual: 694066178 expected: 694066178 true
129. actual: 694066179 expected: 694066179 true
130. actual: 694066180 expected: 694066180 true
131. actual: 694066149 expected: 694066149 true
132. actual: 694066181 expected: 694066181 true
133. actual: 4168192178 expected: 4168192178 true
134. actual: 694066153 expected: 694066153 true
135. actual: 694066182 expected: 694066182 true
136. actual: 694066183 expected: 694066183 true
137. actual: 4168192176 expected: 4168192176 true
138. actual: 694066156 expected: 694066156 true
139. actual: 694066184 expected: 694066184 true
140. actual: 694066185 expected: 694066185 true
141. actual: 4168192174 expected: 4168192174 true
142. actual: 1003274388 expected: 1003274388 true
143. actual: 694066082 expected: 694066082 true
144. actual: 694066083 expected: 694066083 true
145. actual: 694066084 expected: 694066084 true
146. actual: 694066085 expected: 694066085 true
147. actual: 4168192172 expected: 4168192172 true
148. actual: 694066087 expected: 694066087 true
149. actual: 694066088 expected: 694066088 true
150. actual: 694066079 expected: 694066079 true
151. actual: 694066089 expected: 694066089 true
152. actual: 694066090 expected: 694066090 true
153. actual: 694066091 expected: 694066091 true
154. actual: 694066092 expected: 694066092 true
155. actual: 694066093 expected: 694066093 true
156. actual: 694066094 expected: 694066094 true
157. actual: 694066096 expected: 694066096 true
158. actual: 694066097 expected: 694066097 true
159. actual: 694066098 expected: 694066098 true
160. actual: 694066099 expected: 694066099 true
161. actual: 694066100 expected: 694066100 true
162. actual: 694066101 expected: 694066101 true
163. actual: 53112641 expected: 53112641 true
164. actual: 957600270 expected: 957600270 true
165. actual: 53134475 expected: 53134475 true
166. actual: 2932394300 expected: 2932394300 true
167. actual: 2932394322 expected: 2932394322 true
168. actual: 2932394321 expected: 2932394321 true
169. actual: 2932394317 expected: 2932394317 true
170. actual: 899950046 expected: 899950046 true
171. actual: 3695372188 expected: 3695372188 true
172. actual: 53038057 expected: 53038057 true
173. actual: 4671608616 expected: 4671608616 true
174. actual: 247141147 expected: 247141147 true
175. actual: 4671608614 expected: 4671608614 true
176. actual: 899953916 expected: 899953916 true
177. actual: 247141146 expected: 247141146 true
178. actual: 53147548 expected: 53147548 true
179. actual: 4671608612 expected: 4671608612 true
180. actual: 4671608609 expected: 4671608609 true
181. actual: 311881848 expected: 311881848 true
182. actual: 206093625 expected: 206093625 true
183. actual: 201496240 expected: 201496240 true
184. actual: 4168192169 expected: 4168192169 true
185. actual: 4671608607 expected: 4671608607 true
186. actual: 53075606 expected: 53075606 true
187. actual: 687156431 expected: 687156431 true
188. actual: 4671608604 expected: 4671608604 true
189. actual: 53076244 expected: 53076244 true
190. actual: 4671608602 expected: 4671608602 true
191. actual: 53076245 expected: 53076245 true
192. actual: 4671608605 expected: 4671608605 true
193. actual: 53076246 expected: 53076246 true
194. actual: 53076247 expected: 53076247 true
195. actual: 2834093713 expected: 2834093713 true
196. actual: 260707354 expected: 260707354 true
197. actual: 53076250 expected: 53076250 true
198. actual: 53041668 expected: 53041668 true
199. actual: 697180303 expected: 697180303 true
200. actual: 697180302 expected: 697180302 true
201. actual: 260707356 expected: 260707356 true
202. actual: 697180301 expected: 697180301 true
203. actual: 260707355 expected: 260707355 true
204. actual: 697180300 expected: 697180300 true
205. actual: 2834093720 expected: 2834093720 true
206. actual: 53060461 expected: 53060461 true
207. actual: 260707363 expected: 260707363 true
208. actual: 697180298 expected: 697180298 true
209. actual: 60742947 expected: 60742947 true
210. actual: 2834816929 expected: 2834816929 true
211. actual: 60742945 expected: 60742945 true
java.lang.AssertionError: Your results did not match the expected results
Expected :[2421788578, 2421788572, 4235206881, 53119692, 4235206880, 4235206867, 53042100, 4235206864, 2421788562, 4235206857, 53109978, 4235206856, 73991090, 430994090, 430994091, 2421788520, 430994092, 73991098, 430994093, 2421788570, 73991104, 394196514, 39 ...
Actual :[2421788578, 2421788572, 4235206881, 53119692, 4235206880, 4235206867, 53042100, 4235206864, 2421788562, 4235206857, 53109978, 4235206856, 73991090, 430994090, 430994091, 2421788520, 430994092, 73991098, 430994093, 2421788570, 73991104, 394196514, 39 ...I have run this test case as many times as I can, and the Therefore, I checked the actual: expected: Let's focus on the difference between the two paths. The two paths are the same until the 48th actual: expected: Since the two paths are not the same at the 48th Therefore, in order to verify my guess, I checked the The So the key point now is to determine which public static void main(String[] args) {
String OSM_DB_PATH = "../library-sp18/data/berkeley-2018.osm.xml";
GraphDB g = new GraphDB(OSM_DB_PATH);
long nodeId = 53085430L; // the last right node A
double nodeLat = g.lat(nodeId);
double nodeLon = g.lon(nodeId);
System.out.println("For the A* algorithm, priority f(n) = g(n) + h(n), \n"
+ "where g(n) is the distance from start to the current node\n"
+ "and h(n) is the estimated distance from the current node to the end.\n"
+ "Here we split the priority to three parts, \n"
+ "namely f(n) = distance0 + distance1 + distance2.\n"
+ "distance0 represents the distance from the start to the last right node A (" + nodeId + " here).\n"
+ "distance1 represents the distance from the node A to one of its neighbors.\n"
+ "distance2 represents the distance from the chosen neighbor to the end.\n"
+ "Since node A and the start have been hard-coded, distance0 will never change, \n"
+ "the only thing we care about is distance1 + distance2.");
System.out.println();
long endId = 60742945L;
for (long neighbor : g.adjacent(nodeId)) {
System.out.println("neighbor's id: " + neighbor + ": ");
System.out.println("distance1 from the last right node A to this node: " + g.distance(neighbor, nodeId));
System.out.println("distance2 from this node to the end node: " + g.distance(neighbor, endId));
System.out.println("distance1 + distance2: ");
System.out.println(g.distance(neighbor, nodeId) + g.distance(neighbor, endId));
System.out.println();
}
}The result is as follows For the A* algorithm, priority f(n) = g(n) + h(n),
where g(n) is the distance from the start to the current node
and h(n) is the estimated distance from the current node to the end.
Here we split the priority into three parts,
namely f(n) = distance0 + distance1 + distance2.
distance0 represents the distance from the start to the last right node A (53085430 here).
distance1 represents the distance from node A to one of its neighbors.
distance2 represents the distance from the chosen neighbor to the end.
Since node A and the start have been hard-coded, distance0 will never change,
the only thing we care about is distance1 + distance2.
neighbor's id: 2285146649:
distance1 from the last right node A to this node: 0.0065539105439993625
distance2 from this node to the end node: 2.4273341794177696
distance1 + distance2:
2.433888089961769
neighbor's id: 53085428:
distance1 from the last right node A to this node: 0.05565059675442217
distance2 from this node to the end node: 2.473191614699802
distance1 + distance2:
2.5288422114542244
neighbor's id: 4559569771:
distance1 from the last right node A to this node: 0.004916008074508706
distance2 from this node to the end node: 2.4178080365942822
distance1 + distance2:
2.422724044668791
neighbor's id: 240469482:
distance1 from the last right node A to this node: 0.006472944746572685
distance2 from this node to the end node: 2.4174095440362278
distance1 + distance2:
2.4238824887828003According to the calculation, the 4
Since from the graph I roughly estimate In conclusion, I think your code is correct, and the tiny problem lies in the test cases. Most of the test cases are correct, but there are some test cases such as these two that are buggy. I hope this can help you. If you have any questions, please let me know. Good luck! |
Beta Was this translation helpful? Give feedback.
-
|
I'm sorry that I may have been too arbitrary before to decide the given test cases are a little buggy. I have checked the code and the test cases again. It's not that right to just imagine with my intuition that neither of the two to-be-considered neighbors of the 47th node is still unmarked (namely, not be polled out from the priority queue) before polling out the current 47th node and considering it. In my local machine, with your code (modified a little as follows), the 47th node ( // in Router.java
public static List<Long> shortestPath(GraphDB g, double stlon, double stlat,
double destlon, double destlat) {
...... // omitted
Map<Long, Integer> polledOut = new HashMap<>();
int num = 0;
while (!priorityQueue.isEmpty()) {
long v = priorityQueue.remove().id;
polledOut.put(v, num);
num += 1;
...... // omitted
if (v == endNodeId) {
...... // omitted
System.out.println("53085430L: " + polledOut.get(53085430L) + "th");
System.out.println("4559569771L: " + polledOut.get(4559569771L) + "th");
System.out.println("240469482L: " + polledOut.get(240469482L) + "th");
return path;
}
...... // omitted
}
return path; // path doesn't exist, return an empty list.
}
public static void main(String[] args) {
String OSM_DB_PATH = "../library-sp18/data/berkeley-2018.osm.xml";
GraphDB g = new GraphDB(OSM_DB_PATH);
List<Long> route = new LinkedList<>();
Map<String, Double> testParam = new HashMap<>();
testParam.put("end_lat", 37.82769961829141);
testParam.put("start_lon", -122.28525299251741);
testParam.put("start_lat", 37.85193141952368);
testParam.put("end_lon", -122.23869943366023);
route = Router.shortestPath(g, testParam.get("start_lon"), testParam.get("start_lat"),
testParam.get("end_lon"), testParam.get("end_lat"));
}It seems great that either of them can be the next node since they will not be polled out before the 47th node is polled out. However, this doesn't mean that it's the same situation as the AutoGrader. Maybe in GradeScope, I will continue to investigate this problem. |
Beta Was this translation helpful? Give feedback.
-
|
I have just calculated the shortest distance for both System.out.println(dstToStart.get(endNodeId));before the final Just take case 1 as an example. the shortest path distance (which is not equal to great-circle distance mentioned in Part III and implemented as a static method in PS: If you are curious about how to obtain the I found out that the 48th nodes in With this tiny modification, I finally succeeded in passing the test case more than 1000 times. So now I'm convinced I obtained the true Now I tend to believe that there are probably some bugs lying in the test cases. In order to make my point more persuasive, I considered test case 2 as well. (You can mark 3 nodes
|
Beta Was this translation helpful? Give feedback.
-
|
Thank you very much and sorry for the late replay. You can try the test case following and you may find that the path of the expected seems more reasonable Here is some part of the actual path which I think is very strange. |
Beta Was this translation helpful? Give feedback.
-
|
Probably the staff solution considered the max-speed or one-way tags. On the other hand, we are demanded to pretend that there are no max-speed restrictions and all roads are two-way. From my personal point of view, I guess that's why your Another interesting thing discovered: |
Beta Was this translation helpful? Give feedback.
-
|
Maybe the I may continue with the new test case someday. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you very much for helping me out! |
Beta Was this translation helpful? Give feedback.
I have just calculated the shortest distance for both
actualandexpected, which can be implemented and printed out bybefore the final
pathreturned.Just take case 1 as an example.
the shortest path distance (which is not equal to great-circle distance mentioned in Part III and implemented as a static method in$3.6663282543965448$ . In comparison, the shortest path distance is larger for $3.6676323939880024$ .
GraphDB. the shortest path distance is the "navigation" distance) foractualisexpectedwhich isPS: If you are curious about how to obtain the
expectedpath's distance, the implementation is as follows.I found out that the 48th node…