 Calculate All Possible Routes
This function is a helper function for a brute force method of finding the shortest path between a set of five points. If the five points are numbered 0 through 4, a route is a unique ordering of the numbers 0 through 4. There are 120 such orderings (5 * 4 * 3 * 2 * 1), including ones that are the reverse of others. Each of the five positions in a route is called a slot, and the number in a given slot is called a stop.
The routes are numbered 0 through 119 and a lower-numbered route always has lower stops in earlier slots, except that a route cannot repeat a lower-numbered route. For example, the first route will be 0 1 2 3 4, the second will be 0 1 2 4 3, the third will be 0 1 3 2 4, and the last will be 4 3 2 1 0.
With 5 entries in a route, any given choice of stop in the first slot allows 24 possible choices for the others (4 * 3 * 2 * 1). So, the first 24 routes have stop 0 in the first slot, the next 24 have stop 1 in the first slot, and so on.
Then, for the 24 routes with stop 0 in the first slot, the first 6 have stop 1 in the second slot, the next 6 have stop 2 in the second slot, and so on. For the 24 routes with stop 1 in the first slot, the first 6 have stop 0 in the second slot, the next 6 have stop 2 in the second slot, and so on.
The function is passed a route number between 0 and 119. It is also passed an array that can hold 5 integers. The function should fill in the 5 places in the array with the numbers 0 through 4, arranged according to the route number. The function always fills in the array the same way for a given route number.
Source Code
1. void
2. fill_route(
3. int route_number,
4. int slots[5]) {
5.
6. int stops_available[5];
7. int i, j, k, factor, slot, this_stop;
8.
9. for (i = 0; i < 5; i++) {
10. stops_available[i] = i; // all unused at first
11. }
12.
13. for (slot = 0; slot < 5; slot++) {
14.
15. // For each slot, see how many consecutive
16. // routes have the same stop in that slot. It's
17. // the number of slots left factorial, so this
18. // next loop calculates (4 - slot)!.
19. factor = 1;
20. for (j = 4-slot; j > 0; j--) {
21. factor *= j;
22. }
23. this_stop = route_number / factor;
24.
25. // Find the (this_stop+1)'th stop still left in
26. // stops_available. The first time through the
27. // outer loop (slot == 0) this will just be
28. // stops_available[this_stop], but as entries in
29. // stops_available[] are used and marked with -1
30. // that will change.
31. k = this_stop;
32. for (j = 0; j < 5; j++) {
33. if (stops_available[j] != -1) {
34. if (k == 0) {
35. stops_available[j] = -1;
36. slots[slot] = stops_available[j];
37. break;
38. }
39. --k;
40. }
41. }
42. route_number = route_number % factor;
43. }
44. }
Suggestions
Note where the local variables are used, especially i, j, and k. Examine the calculation of factorial on lines 20 and 21 to ensure that the algorithm is correct. Think of what else acts as a loop variable for the main if from lines 13-43. Is it initialized and updated correctly? Lines 35 and 36 have the same expression appearing on the left and right side of an assignment in quick succession. Is this done correctly?
Hints
Because the code is dividing and taking the modulo of the route number, it might be mathematically simplest to try with a route number of 0. That is, the function is called as fill_route(0, slots) where slots[] is an array of 5 ints. Because there are 24 choices for a given stop in the first slot, a number just higher than 24 is a good test. Walk through the code to calculate route 25: The function is called as fill_route(25, slots) where slots[] an array of 5 ints.
Explanation of the Bug
The code to fill in slots[slot] and "use up" a stop, on lines 36 and 37,
stops_available[j] = -1;
slots[slot] = stops_available[j];
does it in the incorrect order, which is an F.location bug. The effect is to set slots[slot] to -1. The two lines of code need to be swapped:
slots[slot] = stops_available[j];
stops_available[j] = -1;
This manifests itself with any route number, so the same behavior should have been observed with both hints: The resulting slots[] array has -1 in all five positions. However, running through the code with different route numbers should help you understand how this (admittedly confusing) algorithm works, because everything up until the actual assignment to slots[] is correct.
|
