Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
My attempt at clarifying how cycles work for the Tideman algorithm

A Way to Look at Tideman Lock Pairs

I've observed that there is a little bit of a disconnect in understanding what it is that needs to be done to properly implement the lock_pairs function for cs50 Tideman. The goal of this little write-up is simply an attempt at explaining what the problem actually is, and why a cycle imposes a problem.

First:
If you are unfamiliar with the actual problem, or have not read through the entire cs50 Tideman problem description. Then I think you should start there.
cs50 Tideman

Second:
This little write-up is only narrowing in on the idea of cycles, and a way to think about what a cycle is and determine if locking a pair in the pairs array would create that cycle. This does not talk about any other part of the Tideman problem.

lock_pairs Purpose:
The function lock_pairs does one thing, and one thing only. That is update the locked array for all the pairs that should get locked. The lock_pairs function does not know anything about the Tideman problem itself. The function does not know what a source is, it does not care who the eventual winner the Tideman algorithm would pick. It does one thing. It decides whether to lock a pair, or not lock a pair.

I'm saying this explicitly because I see a lot of people make the mistake of inferring the logic the Tideman algorithm would use to take shortcuts in the lock_pairs function. So don't do that. I've also see people conflate the extra ideas that the Tideman algorithm uses, that creates confusion in what it is the lock_pairs function is actually doing.

Once again. lock_pairs doesn't know what a source is, and doesn't care who the eventual winner would be. It is the function that creates the guide (locked) that you can later determine who the winner is.

So what is a cycle?
As explained in the cs50 Tideman problem description. A cycle is is when the winner of a pair can be traced through the graph of what is already locked and get back to that same winner.

Wait... Graph. Maybe that term means something in the realm of computer science.
Wikipedia Graph(abstract data type)

Ok. Don't let that overwhelm you. Just realize that a graph is an idea of how to conceptualize and order data for a problem that can provide a solution in a new way.

So what does a graph have to do with this problem? Lets dig into that with a little bit of a real example.

Consider this:
Candidates = [a, b, c, d]
Sorted Pairs = [(d, a), (a, b), (b, c), (c, a), (d, b), (d, c)]
Note for the Sorted Pairs. If you test and your sorted order is slightly different than this. That is ok based on differences in the sorting algorithm.

We take each pair one pair at a time and determine whether to lock it or not.
When we take a pair, we are in a sense creating a graph, using the locked array as our guide. As more pairs get locked, we have more pairs we may have to check. Our goal is to create a chain, from winner through loser and see if we can get back to our original winner. If we can that is a cycle, and if not then no cycle is created.

So what would that look like?

Taking the first pair (d, a) we take the winner d and see if a wins in any pair that is locked. Since no pairs are locked (this is our first pair) a never wins. So we can lock (d, a). The chain formed would look as follows.
d -> a

Taking the second pair (a, b) we perform the same algorithm. b is never found to win in any locked pair though. So we can safely lock.
a -> b

Taking the third pair (b, c) we do the same once again. c is never found to win in any locked pair though. So we can safely lock.
b -> c

Taking the fourth pair (c, a). a is found to win against another candidate and that pair is locked. So we build a chain starting with c, though a, and see how far it takes us.
c -> a -> b -> c
In this case we find that using the previously locked pairs, we can create a chain from c and get back to c. So we shouldn't lock this pair. It is a cycle.

Taking the fifth pair (d, b) we once again do the same.
d -> b -> c
Because the pair (c, a) was not locked prior to checking our pair (d, b) we can safely lock this pair.

Taking the final pair (d, c) we do the same one more time.
d -> c
And we can lock the final pair.

So considering the above we locked all but one pair. Pair (c, a) was found to create a cycle.

Our final graph would look something like this

a
d b
c

Takeaway
The primary thing I hope you observe in the above is the simple logic we can apply to determine what forms a cycle, and what does not. Every time we find a new link in the chain, we have to re-examine all the pairs once again to see if the newly found loser would win against any other candidate in any locked pair. If we find one, we create a new link in the chain and repeat the process.

For every pair we consider. We are creating a new graph and attempting to traverse from the original winner, back to that same original winner. Even though the ultimate result is one big graph.

Please note. This is a very simple example, and it is possible that you have to check more than one chain when looking for a cycle. For example if a candidate wins agains multiple other candidates, but also loses.

Why recursion is helpful
The reason recursion can help in solving this type of problem is based on how each recursive function remembers where it left off if you continue to call it over an over. I do believe this cs50 short video explains how that memory works pretty well. So every time you find you should create a new link in the chain, you can recursively call your function to look for a cycle and all the frames remember where they left off.

I hope my couple thoughts are helpful in aiding you in solving the Tideman problem. Feel free to let me know if you see any error in my above explanation of things, or if you feel I could/should add anything I didn't touch on.

Feel free to use the text4.txt file to test your own solution to the Tideman problem.
To use the file just download to your folder where you tideman program exists and run as
./tideman a b c d < test4.txt

5
a
c
b
d
b
c
d
a
d
c
a
b
d
a
b
c
d
b
c
a
@nicknapoli82
Copy link
Author

nicknapoli82 commented Apr 17, 2021

@mark-w-newton
Sure. It actually doesn't matter what direction you go. I don't believe any assertion was made that says otherwise.

@Ishan-Mehta
Copy link

Ishan-Mehta commented Apr 23, 2021

@nicknapoli82
I think there is a something wrong with this explanation here...

Taking the fifth pair (d, b) we once again do the same.
d -> b -> c
Because the pair (c, a) was not locked prior to checking our pair (d, b) we can safely lock this pair.

I think that even if (for instance) the pair (c, a) was locked prior to checking the pair (d, b), there was no problem in locking the pair (d, b). Suppose that we locked the pair (c, a) and now we are checking the next pair (d, b). This pair (d, b) is not going to create any cycle if it is locked. So, it doesn't matter if the pair (c, a) is locked or not.

@nicknapoli82
Copy link
Author

nicknapoli82 commented Apr 23, 2021

@Ishan-Mehta
I believe your question was answered on the cs50 discord server, but I may as well say here.

From this short excerpt

Taking the fourth pair (c, a). a is found to win against another candidate and that pair is locked. So we build a chain starting with c, though a, and see how far it takes us.
c -> a -> b -> c
In this case we find that using the previously locked pairs, we can create a chain from c and get back to c. So we shouldn't lock this pair. It is a cycle.

Taking the fifth pair (d, b) we once again do the same.
d -> b -> c

If we had locked the previous pair (c, a), then the chain for pair (d, b) would look like this
d->b->c->a->b->c
which would still contain a cycle in its own right. It just happens to be an subset of the larger chain now. Thats all.

Your correct in entertaining the idea that the candidate d would never be found more than once, but the entire algorithm relies on the fact that no cycles should ever exist to begin with.

@yallahh
Copy link

yallahh commented Apr 25, 2021

Thanks for writing this up, it's been very helpful.

Taking the first pair (d, a) we take the winner d and see if a wins in any pair that is locked

I think you mean we take the loser a?

@Ishan-Mehta
Copy link

Ishan-Mehta commented Apr 25, 2021

@Ishan-Mehta
I believe your question was answered on the cs50 discord server, but I may as well say here.

From this short excerpt

Taking the fourth pair (c, a). a is found to win against another candidate and that pair is locked. So we build a chain starting with c, though a, and see how far it takes us.
c -> a -> b -> c
In this case we find that using the previously locked pairs, we can create a chain from c and get back to c. So we shouldn't lock this pair. It is a cycle.

Taking the fifth pair (d, b) we once again do the same.
d -> b -> c

If we had locked the previous pair (c, a), then the chain for pair (d, b) would look like this
d->b->c->a->b->c
which would still contain a cycle in its own right. It just happens to be an subset of the larger chain now. Thats all.

Your correct in entertaining the idea that the candidate d would never be found more than once, but the entire algorithm relies on the fact that no cycles should ever exist to begin with.

OK got it! Thanks!

@RaihanAminRana
Copy link

RaihanAminRana commented May 26, 2021

Thank you for the clarification

@luongvmanh
Copy link

luongvmanh commented Jun 21, 2021

This was really helpful, thanks!

I think it's fair to say that a step wise way to describe this process is:

  1. Look at a pair
  2. If the loser is not a winner in any existing locked pair, then lock the pair
  3. If the loser is a winner in an existing locked pair:
  4. Look at that pair
  5. If the loser is not a winner in any existing locked pair, then lock the pair
  6. If the loser is a winner in an existing locked pair:
  7. Look at that pair
  8. etc, etc etc . . .

Clearly, recursion would be helpful/useful here. Now I've just got to get my brain wrapped around that! :)

I don't think this is the right way. As you can see step 1, 2, 3 are good because you are considering the current pairs but other steps are not right because the pairs you're looking at now has been locked before, so "then lock the pair" for what?

@catDadCoder
Copy link

catDadCoder commented Jun 22, 2021

OMG thanks so much for this test case. Finding it hard to debug without a proper example!

@RandyKdev
Copy link

RandyKdev commented Aug 2, 2021

Thanks for the clarification :)

@luongvmanh
Copy link

luongvmanh commented Aug 9, 2021

Your explanation has helped me to solve the lock_pair part. Thank you very much #nicknapoli82 because I had been stuck at this part for months. You were right, Lock_pair is only for "locked" and another function (recursive function is very helpful) is to check whether there's a cycle or not. This check function will check one pair at a time (this input from the lock_pair function) with a base case and a recursive base ( a loop to check if the Loser of the current pair is the Winner of any previous locked pair). Though my results are different as you said due to the sort_pair algorithm, it's still true.

@TS-code-netizen
Copy link

TS-code-netizen commented Aug 19, 2021

Thank you Nick!

@DmytroHusak
Copy link

DmytroHusak commented Aug 30, 2021

@nicknapoli82
Hello. Could you please tell me whether a cyclical graph always has only three edges (considering this problem, at least)? I haven't seen more than that once. I used this source https://tideman.netlify.app/ to test my program extensively, including going through locked array, and everything seemed to work as it should. However, I still encounter this annoying problem with the last pair. I preferred loops to recursion.
Thank you in advance!

@nicknapoli82
Copy link
Author

nicknapoli82 commented Aug 30, 2021

@DmytroHusak
No. A cycle in a graph may have any number of edges to actually form a cycle and the minimum needed would be three in this problem.
The minimum is three because if pair(a, b) exists then pair(b, a) can not exist. So using this logic we would need at least three candidate nodes in the graph to form a cycle.
a->b->c->a In the simplest form.

What we can say for the maximum number of edges that may form a cycle would depend on the number of candidates, or nodes in the graph. So if we have MAX or 9 candidates. Then we could have something like
a->b->c->d->e->f->g->h->i->a

@daniswhoiam
Copy link

daniswhoiam commented Sep 1, 2021

For everyone still having the ":( lock_pairs skips final pair if it creates cycle" error, this might be due to the following error in your code / logic: If the other lock_pairs tests are working, then you are probably on the right path but not checking for a special edge case.
Consider the previously mentioned graph:

case 14:  //lock final pair test
            pair_count = 7;
            pairs[0].winner = 0; pairs[0].loser = 1;  
            pairs[1].winner = 1; pairs[1].loser = 4;  
            pairs[2].winner = 4; pairs[2].loser = 2;  
            pairs[3].winner = 4; pairs[3].loser = 3;  
            pairs[4].winner = 3; pairs[4].loser = 5;  
            pairs[5].winner = 5; pairs[5].loser = 1; // interesting moment (1)  
            pairs[6].winner = 2; pairs[6].loser = 1; 

If you write it out on paper, you will see that from the number 4 the graph splits and you can either go to 2 or to 3.
Now, with the incomplete logic your code is probably looking for "leafs", i.e. numbers that are only "losers" and not "winners", only (to be precise: only the first leaf).

However, this might result in the code to end prematurely. In the above case, because 2 < 3, the code would go to number 2 before 3. 2 is a leaf at the moment of the check (1). Then, having found this leaf that causes no loop, the code terminates.
This leads to the code not checking the next branch, i.e. 3, which would lead to the proper conclusion, that at (1) a loop would be created.

Long story short: You need to include logic into your code to check every available branch, and if one causes circularity, not lock the pair.

Wrong:

for (int i = 0; i < candidate_count; i++)
    {
        if(locked[loser][i])
        {
            return is_circle(i, winner);
        }
    }

Correct:

for (int i = 0; i < candidate_count; i++)
    {
        bool result = false;
        if (locked[loser][i])
        {
            result = check_circular(i, winner);
        }
        if (result || i == candidate_count - 1) // Only return result if all branches checked or the last checked branch showed circularity
        {
            return result;    
        }
    }

Note: These are excerpts of a recursive helper function to check for circularity and not the complete code.

@CS50Mana
Copy link

CS50Mana commented Sep 17, 2021

thank you very much vor this explanation , I was stuck with lock function for a week, finally I got the answer thanks to your post.

@ngannguyen1009
Copy link

ngannguyen1009 commented Sep 21, 2021

case 16: //lock all pairs if no cycles
pair_count = 4;
pairs[0].winner = 4; pairs[0].loser = 2;
pairs[1].winner = 0; pairs[1].loser = 3;
pairs[2].winner = 1; pairs[2].loser = 0;
pairs[3].winner = 3; pairs[3].loser = 4;

pairs[3].loser = pairs[0].winner, and pairs[3].winner = pairs[1].loser

Therefore follow the cycle code check, pair[3] should not locked, but on the graph should lock

How can I solution this?

Please help, thank you guys
Here my code:

image

@sha9189
Copy link

sha9189 commented Oct 2, 2021

Thanks a lot! This post helped me a lot!

@shumai9
Copy link

shumai9 commented Oct 13, 2021

Thank you both @nicknapoli82 and @daniswhoiam for sharing the gist very helpful.

@yaakovmeir
Copy link

yaakovmeir commented Oct 23, 2021

thank you so much I got the code right but I hade a problem and running your code helped me

@KaizokuRuffy
Copy link

KaizokuRuffy commented Oct 25, 2021

The logic of Tiedeman election is kind of stupid (not directing at any particular person. Just saying). So instead of having to not lock pairs if it creates a cycles it would be a better idea to not lock pairs if doing so we end up with no source. Just because a pairs creates a cycle doesn't mean that it causes for there to be no source.
In @nicknapoli82 's example (c, a) pair is rejected because it creates a cycle. But ultimately if we reject it or not d is always the winner since d didn't lose any of its head-head matchups. Am i wrong?

@KindLivingSon
Copy link

KindLivingSon commented Dec 1, 2021

Screen Shot 2021-12-01 at 7 03 15 PM

Please, help me, please, I don't understand why checker writing this, I check algorithm and all pairs locked with no cycles.

@KaizokuRuffy
Copy link

KaizokuRuffy commented Dec 1, 2021

@KindLivingSon I see that you are having problem with tideman problem. You say you have checked algorithm and all pairs locked with no cycles. But you might have accidentally chosen a particular test case which is true for your algorithm. So go to this link and check for that test case against your algorithm. The instruction are given on how to use that test case which presides in text file since giving manual input is tiresome. Take this, "Here are the pairs, in my codes sorted order, that should be locked or not locked. The end is the winner.
This is considering the order of my pairs specifically. If your tied pairs are ordered different, the winner my be different." into consideration and check for the winner accordingly by taking into account the sorted pairs generated by your algorithm. Hope you don't get SEG FAULT.

@KaizokuRuffy
Copy link

KaizokuRuffy commented Dec 1, 2021

@KindLivingSon You probably have to modify the line 201 and 203 if conditions. Because what you have right there solves a very very tiny piece of the puzzle. That is why your algo is not satisfying all the test cases. In those two if conditions you are asserting that check for in the locked pairs that if the winner of the pair to be locked is the loser of ith locked pair then increment and if the loser of pair to be locked is the winner increment. But why should win == pairs[i].loser why can't win == pairs[i].winner ?? Same goes for los also. What you should do is add win == pairs[i].winner and los == pairs[i].loser as two if conditions. But doing this alone will not solve the problem, in fact other two test cases for locked pairs might return false. By using the four if conditions you are merely checking for both win and loss if either of them are winner or loser of ith locked pair which doesn't accomplish what you want to find which is to check for cycles. So think of a way to do that by using four if conditions as the base. And also in lock_pairs you are first checking for cycle and then locking pair if !cycler() which is wrong approach. Because you can't check whether locking a pair creates cycle before actually locking them. First you have to lock the pair for which you are going to check whether locking them will create cycle and then call cycler inside if condition. In case that if case becomes true change locked [pairs[i].winner] [pairs[i].loser] == false. Please bear with long passage i just want to be sure so as not to confuse you any further.

@MuhammedZakir
Copy link

MuhammedZakir commented Dec 1, 2021

@KindLivingSon: I think your algorithm for checking cycles is wrong. You're not following the cycte, but rather cross-checking the "winner" and "loser" against loser and winner in locked pairs. For instance, for below pairs, it wouldn't lock the last pair even though it should.

pairs[0].winner = 4; pairs[0].loser = 2; // pair3.loser  == winner => check2 becomes 1
pairs[1].winner = 0; pairs[1].loser = 3; // pair3.winner == loser  => check1 becomes 1
pairs[2].winner = 1; pairs[2].loser = 0;
pairs[3].winner = 3; pairs[3].loser = 4;

One thing I don't understand is that if I am right, then lock_pairs skip final pair ... test should also fail. But it didn't for you, so I might be wrong.


You can find tests used by check50 for lock_pairs() here

For testing my functions, I did what check50 did -- copying my code from tideman.c to testing.c and running it. Adding a few printfs to make output more verbose helped a lot.

P.S. One more reason I am recommending tests used by check50 is that I was able to produce a tideman problem that would create a cycle using my lock_pairs function, but it passed all tests of check50.

@KindLivingSon
Copy link

KindLivingSon commented Dec 3, 2021

Thanks, a lot! Tideman done!

@KaizokuRuffy
Copy link

KaizokuRuffy commented Dec 4, 2021

@KindLivingSon Amazing! Nice to hear that. Can you send screenshot of your locked pairs function ? I am curious so has to how you solved the problem. Since there is not only one-way to write that function i want to see what method you used. Thanks!

@NitzanShwartz
Copy link

NitzanShwartz commented Dec 13, 2021

Hey,

Thank you very much, it helped a lot!

@simonasSab
Copy link

simonasSab commented Jan 8, 2022

You will go down in history as the man who saved the world from the Tideman!

@IzitoI
Copy link

IzitoI commented Jan 16, 2022

@MuhammedZakir Could you explain what you mean by "Don't return from function, only check if it creates a cycle". I'm having the same issue. Thank you very much ;)

@MuhammedZakir
Copy link

MuhammedZakir commented Jan 21, 2022

@MuhammedZakir Could you explain what you mean by "Don't return from function, only check if it creates a cycle". I'm having the same issue. Thank you very much ;)

Sorry that was worded wrongly. What I wanted to say was that, in the loop, he/she wrote return checkCycle(winner, i);. If you do that, the program will exit from the loop early - before checking all pairs. To fix this, you just need to remove return from that statement.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment