· 5 years ago · Aug 29, 2020, 08:16 PM
1
2// Update preferences given one voter's ranks
3void record_preferences(int ranks[])
4{
5 // if I have candidates A B C D (and I enumerate them as: A = 0, B = 1, C = 2, D = 3):
6 // every voter will rank 4 candidates in their vote --> amount of rankings = candidate_count = strlen(ranks) = 4
7 //
8 // if voter1's vote = A, D, C, B
9 // ranks[0] = A = 0
10 // ranks[1] = D = 3
11 // ranks[2] = C = 2
12 // ranks[3] = B = 1
13 //
14 // So: --> [winner, looser]: --> preferences[winner][looser] counters I need to process:
15 // A beats B, C and D --> [A,D] [A,C] [A,B] --> preferences[0][3]++, preferences[0][2]++, preferences[0][1]++
16 // D beats C, B --> [D,C] [D,B] --> preferences[3][2]++, preferences[3][1]++,
17 // C beats B --> [C,B] --> preferences[2][1]++
18 //
19 // In a generic way, the [winner, looser] pairs I need to process are:
20 // 1st place: [ranks[0], ranks[1]] , [ranks[0], ranks[2]] , [ranks[0], ranks[3]]
21 // 2nd place: [ranks[1], ranks[2]] , [ranks[1], ranks[3]]
22 // 3rd place: [ranks[2], ranks[3]]
23 //
24 // We can see that:
25 // In 1st place: [ranks[w], ranks[l]] iterations are w = 0 and l = 1, 2, 3
26 // In 2nd place: [ranks[w], ranks[l]] iterations are w = 1 and l = 2, 3
27 // In 3rd place: [ranks[w], ranks[l]] iterations are w = 2 and l = 3
28 //
29 // (w stands for winner, l for looser)
30 //
31 // this means (0 <= W <= 2) hence (0 <= W < 3) hence (0 <= W < candidate_count - 1)
32 // (1 <= L <= 3) hence (1 <= L < 4) hence (1 <= L < candidate_count)
33
34
35}
36
37// Record pairs of candidates where one is preferred over the other
38void add_pairs(void)
39{
40 // From our previous example, voter1's vote = A, D, C, B
41 // After the first iteration (voter1), our preferences[w][l] array should look this way:
42 //
43 // | l=0 l=1 l=2 l=3
44 // --------------------------------
45 // w=0 | - +1 +1 +1
46 // w=1 | 0 - 0 0
47 // w=2 | 0 +1 - 0
48 // w=3 | 0 +1 +1 -
49 //
50 // (we ignore the middle diagonal as it's comparing a candidate against himself).
51 // voter1 prefers candidate A over the rest, hence its preferences over, for example, D, are:
52 // preferences[A][D] = preferences[w=0][l=3] = +1
53 // preferences[D][A] = preferences[w=3][l=0] = 0
54 //
55 // After all voters voted, our preferences array could look something like:
56 // | l=0 l=1 l=2 l=3
57 // --------------------------------
58 // w=0 | - 3 0 1
59 // w=1 | 2 - 1 0
60 // w=2 | 0 4 - 2
61 // w=3 | 4 2 3 -
62 //
63 // We need to translate these results into winner/loser pairs.
64 // For that, we use a "pairs" array that has a "winner" and "loser" attributes
65 // So, for our A,D pair example:
66 // preferences[A][D] = 1 --> pairs[AD].loser = A
67 // preferences[D][A] = 4 --> pairs[AD].winner = D
68 // (we won't be able to use chars as an array index, we will use an equivalent number)
69 //
70 // Ok, but how many pairs do we have?
71 // Let's identify all the possible combinations
72 //
73 // | A B C D
74 // ------------------------------------------
75 // A | A,A A,B A,C A,D
76 // B | B,A B,B B,C B,D
77 // C | C,A C,B C,C C,D
78 // D | D,A D,B D,C D,D
79 //
80 // But we don't need to pair a candidate with himself (middle diagonal)
81 // Neither we need B,A if we already have the A,B pair, as our array has the "winner", "loser" attributes (B,A will just be the opposite of A,B)
82 //
83 // | A B C D
84 // ------------------------------------------
85 // A | (IGNORE) A,B A,C A,D
86 // B | (IGNORE) (IGNORE) B,C B,D
87 // C | (IGNORE) (IGNORE) (IGNORE) C,D
88 // D | (IGNORE) (IGNORE) (IGNORE) (IGNORE)
89 //
90 // Now we need to name our pairs, and we have to use index numbers, as "pairs" is an array.
91 // So, our new names will be:
92 //
93 // | A B C D
94 // ------------------------------------------
95 // A | (IGNORE) pairs[0] pairs[1] pairs[2]
96 // B | (IGNORE) (IGNORE) pairs[3] pairs[4]
97 // C | (IGNORE) (IGNORE) (IGNORE) pairs[5]
98 // D | (IGNORE) (IGNORE) (IGNORE) (IGNORE)
99 //
100 // I think we might have been able to use another order, but we scan matrices from
101 // left to right, top to bottom so the above convention makes the most sense
102 //
103 // Notice something interesting, we have 6 elements, and "pairs" was declared as:
104 // pair pairs[MAX * (MAX - 1) / 2];
105 // why is “pairs” declared this way?
106 // We have 4 candidates, so pairs is sized to 4 * (4 - 1) / 2 = 6, which is in fact, our amount of pairs
107 // MAX * (MAX - 1) / 2 is the formula for a Gaussian sum, that basically
108 // counts the elements on the upper diagonals:
109 // 6 = 3 + 2 + 1 = 4*(4-1)/2
110 // (3 is counting pairs[0], pairs[3], and pairs[5])
111 // (2 is counting pairs[1] and pairs[4])
112 // (1 is counting pairs[5])
113 //
114 // Remember we need to relate our "preferences" matrix with our "pairs" matrix with number notation
115 //
116 // If:
117 // preferences[A][D] = 1 --> pairs[AD].winner = D
118 // preferences[D][A] = 4 --> pairs[AD].loser = A
119 //
120 // Using our number's notation, it will be:
121 // preferences[0][3] = 1 --> pairs[2].winner = 3
122 // preferences[3][0] = 4 --> pairs[2].loser = 0
123 //
124 // remember we need to ignore a tie (per exercise statement)
125
126}
127
128// Lock pairs into the candidate graph in order, without creating cycles
129void lock_pairs(void)
130{
131
132 // It's probably useful to read some graph theory first, and becoming familiar with terms like "adjacency matrix" "Depth First Search" "transverse". And also see "How to Detect Cycle in Directed Graph"
133 // There's some theory behind this function that we didn't see yet in the course.
134 // Grabbing pen an paper to draw the examples I gonna explain, it will make your life much easier
135
136 // How we detect a cycle?
137 // If the edge A-->B exists, a cycle exists if there's a way to depart from B and reach A
138 // The key here is to understand that the edges to build this alternative way to reach "A" HAVE TO BE LOCKED
139 // why? Because we already sorted them by victory strength, so we start processing good guys, locking them, then look if any of the next ones create a loop
140 // The locked array is our graph, and it’s dynamic, it’s empty on the first iteration (that’s why we can safely lock the first edge, it has nothing to cycle with), and starts getting bigger (or equal, if we don’t lock) over the next iterations (edges being processed), therefore we have to do more tests for later edges in order to safely lock them.
141 // for instance, we first process A-->B, there's no locked edge yet as it's the first one, so we lock it. Then, we process B-->C
142 // let´s say we lock A-->B, the next question we ask is if B-->C generates a loop in our graph (which is only A-->B, so we ask if the edge B-->C == B-->A) it’s not, so we lock B-->C.
143 // Read this exercise's description part carefully:
144 // "Tideman algorithm must be careful to avoid creating cycles in the candidate graph. How does it do this? The algorithm locks in the strongest edges first, since those are arguably the most significant. In particular, the Tideman algorithm specifies that matchup edges should be “locked in” to the graph one at a time, based on the “strength” of the victory (the more people who prefer a candidate over their opponent, the stronger the victory). So long as the edge can be locked into the graph without creating a cycle, the edge is added; otherwise, the edge is ignored."
145
146 // It's important to notice that every time we process an edge, we are asking if it's a bad guy (generates a cycle)
147 // we take an edge, for example, F-->E
148 // the simplest case would be this cycle: E-->F-->E (2 opposite edges: E-->F, F-->E)
149 // we process E-->F, it's the first one so no alternative way to reach E departing from F, so we lock it.
150 // but then we process F-->E so there's a cycle (E-->F-->E) as E-->F was already locked, so we don't lock F-->E
151 // LET'S CALL THIS, THE BASE CASE, as it's the simplest one, but this concept will be important for recursion
152
153 // the next case that could happen is this cycle: E-->F-->H-->E (3 edges: E-->F, F-->H, H-->E)
154 // we process E-->F, as it's the first one, we lock it.
155 // we process F-->H, as F-->H != F-->E, we lock it.
156 // but then we process H-->E which closes a loop in our graph of already locked edges (E-->F-->H), so we don't lock it.
157
158 // And so on...
159
160 // take into account that edges come sorted but not "pre-hooked" as my previous examples.
161 // You might receive:
162 // iteration 0: E-->F
163 // iteration 1: Y-->Z
164 // iteration 2: Z-->K
165 // iteration 3: F-->E <--LOOP! E-->F-->E
166
167 // But this doesn't change our solution's approach, we need to see if the edge being processed fits in the extremes of some chain that we can build with 1, 2 or n of the already good processed edges
168
169 // There are several ways to do this, but one of simplest ones is:
170 // We are processing H-->E
171 // does E-->H exist in the locked array? If so, we found a 2 edges cycle (E-->H-->E), so we skip locking H-->E
172 // if not, let's look in the locked array if we can find a good guy to hook up at the beginning of our bad guy, and see if the new extremes generate a loop
173 // Let's say, we found F-->H in locked, ok, we hook it up, now we have F-->H-->E (good guy hooked behind bad guy)
174 // now, we check if E-->F exists among our good guys (is E-->F locked?) if so, we found a 3 edges cycle (E-->F-->H-->E), so we skip locking H-->E
175 // if not, hook up another good guy at the beginning of the chain and check the new extremes
176 // And so on...
177 // If there’s no good guys left to hook up, then it’s safe to lock H-->E
178
179 // Pseudo code:
180 // We create the function closesloop and call it inside lock_pairs to see whether the current edge generates a loop
181 // Call lock_pairs:
182 // loop all pairs from 0 to pair_count (remember, they are already sorted by victory strength)
183 // ask if the pair being processed creates a cycle [call closesloop(pairs[i].winner, pairs[i].loser)]
184 // if winner-->looser doesn't create a cycle, then lock it (locked[pairs[i].winner][pairs[i].loser] = true)
185 // if it creates a cycle, just ignore it, the locked matrix is previously defaulted to false by the code provided by cs50 <--(while this is true, don't ignore it, set it to false, see my notes at the end on how check50 works)
186
187 // Call closesloop:
188 // we receive the parameters (pairs[i].winner, pairs[i].loser) and call it (A, B) for clarity
189 // We are processing A-->B, so (Base case) is locked[B][A] = true? If so, return true as there’s a cycle A-->B-->A
190 // if not, loop through the already locked edges, and search for an edge pointing to our edge's tail (for example, C-->A):
191 // C-->A is locked, hook it up behind, and call closesloop recursively:
192 // This is an important step, we now have C-->A-->B, and have to look if B-->C was previously locked, in order to avoid the cycle C-->A-->B-->C, if so, A-->B should not be locked.
193 // In order for that to be our next question (is B-->C locked?), we need to call closesloop(C,B) recursively so its base case will ask if locked[B][C] = true (if B-->C locked)
194 // if there's no remaining edge in the locked array to hook up (the loop ended), just return false, we can lock A-->B
195
196 // Pseudo code again, the same example, but closer to code language:
197
198 // Call lock_pairs, loop from 0 to pair_count:
199 // 1. call closesloop(A,B):
200 // Is B-->A locked? No >>> loop through locked to find ?-->A >>> Nothing? Ok we are out of the loop, return false
201 // >>> closesloop(A,B) == false, we can lock A-->B
202 // locked = {A-->B}
203 // 2. call closesloop(B,C) >>> Is C-->B locked? No >>> loop through locked to find ?-->B >>> Found A-->B, Ok hook it: A-->B-->C and call recursively closesloop(A,C)
204 // 2.1 call closesloop(A,C):
205 // Is C-->A locked? No >>> loop through locked to find ?-->A >>> Nothing? Ok we are out of the loop, return false
206 // >>> closesloop(A,C) == false >>> return false to closesloop(B,C)
207 // >>> closesloop(B,C) == false, we can lock B-->C
208 // locked = {A-->B, B-->C}
209
210 // I think we are getting the idea, and it's getting a little verbose. If you already got it, great, let recursion do its magic for further cases, and you can skip the example below, if not, let's do one more example with a nice table, this is the table I used to debug (old school, pen and paper).
211 // let's say we have the following edges in order of strength (desc):
212 // 1-->2
213 // 2-->3
214 // 3-->1
215
216 // (We see there's a cycle: 1-->2-->3-->1)
217
218 // (It's read left to right, top to bottom)
219 // iteration locked array closesloop(A,B) B-->A in locked? ?-->A in locked? Result
220 // 0 {} 1-->2 2-->1 not in locked No, no ?-->1 in locked return false to lock_pairs, which locks 1-->2
221 // 1 {1-->2} 2-->3 3-->2 not in locked Yes, 1-->2 in locked hook it behind (1-->2-->3) and call recursively closesloop(1,3)
222 // 1.1 {1-->2} 1-->3 3-->1 not in locked No, no ?-->1 in locked return false to closesloop(2,3) which returns false to lock_pairs, and locks 2-->3
223 // 2 {1-->2, 2-->3} 3-->1 1-->3 not in locked Yes, 2-->3 in locked hook it behind (2-->3-->1) and call recursively closesloop(2,1)
224 // 2.2 {1-->2, 2-->3} 2-->1 1-->2 in locked this logic isn't reached return true to closesloop(3,1) which returns true to lock_pairs, and skips locking 3-->1
225
226 // check50 notes:
227 // there are 2 important things to know about how check50 tests this function, that I realized them while debugging
228 // 1. assume pairs[i].winner might be == pairs[i].loser
229 // Even though I added logic in add_pairs to prevent it, check50 seems to test tideman functions separately, so we need to prevent these cases
230
231 // 2. Don't assume locked[pairs[i].winner][pairs[i].loser] == false by default
232 // even though this is done at the beginning by the code provided by cs50, again, check50 seems to be overwriting it with nothing
233 // So basically write either true or false on every locked[pairs[i].winner][pairs[i].loser] when they are iterated
234 // 3. (bonus) when I solved 2, logic for 1 wasn't needed (it makes sense that our lock_pairs function doesn’t lock a-->a)... check it just in case...
235
236 // If check50 fails to pass "final pair" or "middle pair" and you already did the above:
237 // Here are the graphs used in check50 for the middle pairs and final pairs check.
238
239 // Middle Pair - https://i.imgur.com/mdsDidq.png
240
241 // Final Pair - https://i.imgur.com/OJosjRe.png
242
243 // Source: comments in https://www.reddit.com/r/cs50/comments/hcmlsi/cs50_tideman_my_code_seems_right_but_lock_pairs/
244}
245