1

I'm looking for a little help to check my logic on this problem set.

My program currently passes all the check50 tests up until I have to lock in the pairs to the locked array.

You must lock all pairs in order (which check50 confirms mine are), up until the point that locking in the next pair would cause a loop in the votes system.

My logic is this. In order to not have a loop, there must be at least one candidate that is not beaten by any other candidate in a two candidate stand off.

Therefore, I must stop locking pairs at the point in which the loser for that pair is the final candidate that hasn't yet lost (if indeed this ever happens).

To achieve this, I first create an array of unique losing candidates ,but omit the final candidate to lose (if indeed this happens).

I then proceed to copy each pair into the array, only after having checked if the loser for that pair is in my list of 'permitted loser'. When/if I come across a loser that isn't in my list, I return to main.

I have checked through the logic of my code multiple times, and can't see an issue there.

There very well could be an issue with the code, and if so then I will just continue trying to correct it myself, but I just wanted to get some other opinions on the logic. Clearly if there is a hole in the logic then checking and re-checking my code is pointless.

Any thoughts would be much appreciated!!

1

I don't exactly understand your logic, I found something that feels somewhat simpler in an answer on the new cs50 ed platform. The approach is: For a cycle to appear when you lock a new edge A->B, there would have to already exist a path from B->A.

So my code checks the nodes reachable from B, over any number of steps over already locked edges (avoiding some duplicate checks, but as there are no cycles so far, it would at least be finite). If A is in that set reachable from B, I discard the pair.

| improve this answer | |
  • can you please ellaborate on the approach? I am also unable to find the correct logic of this function. – Neev Mehta Apr 2 at 18:26
0

This logic does not work, because the loops can have branches. So you could have loops with branches that make them look like a 6 or a 9. The simplest way I found to Lock pairs into the candidate graph in order, without creating cycles, was to create a function that detects loops by iterating throughout the whole loop via two nested for loops. One for loop to check if the original strand of code forms a loop another for loop to see if a branch of that code created a loop. These for loops reset with goto commands after they found the next iteration of the loop.

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .