My attempt at clarifying how cycles work for the Tideman algorithm

cs50_Tideman_cycle-explanation.md

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

test4.txt

5
a
c
b
d
b
c
d
a
d
c
a
b
d
a
b
c
d
b
c
a

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.

Thank you Nick!

@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!

@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

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.

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.

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:

Thanks a lot! This post helped me a lot!

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

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

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?

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

@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.

@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.

@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

• https://github.com/cs50/problems/blob/2021/x/tideman/testing.c#L250-L293
• https://github.com/cs50/problems/blob/2020/x/tideman/__init__.py#L91-L107

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.

Thanks, a lot! Tideman done!

@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!

Hey,

Thank you very much, it helped a lot!

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

@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 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.

I stuck on tideman for maybe a month (or I can say as long as i can remember) and this post really help me to finish tideman. To all the people here, especially @nicknapoli82 @daniswhoiam @MatchYouPikchu @Amanda-Fl , thank you so much!

I can't believe it! I just figured lock_pairs thanks in no small part to this post! Trying to solve this without maths or graph theory background was really hard so I'm immensely thankfull!

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.

this was exactly what I needed to solve this final bug - thank you!

Hi - I managed to solve the recursive function, but I have a different question:

If I set up my test case in a txt file and try this:
To use the file just download to your folder where you tideman program exists and run as ./tideman a b c d < test4.txt

It doesn't work. Do you need to add any extra code to main for this to work?

It doesn't work.

I actually haven't run this, but looking at the test4.txt, I suspect it is because the number of voters given is 5, but there are only 4 sets of votings given. However, if that's the case, then someone should report this above and probably would have been fixed already. So I don't know.

If I am right, then changing 5 to 4 in the first line of test4.txt should fix this.

Do you need to add any extra code to main for this to work?

No extra code. If it stil doesn't work, then please post what you get when executing ./tideman a b c d < text4.txt.

I actually haven't run this, but looking at the test4.txt, I suspect it is because the number of voters given is 5, but there are only 4 sets of votings given. However, if that's the case, then someone should report this above and probably would have been fixed already. So I don't know.

If I am right, then changing 5 to 4 in the first line of test4.txt should fix this.

No extra code. If it stil doesn't work, then please post what you get when executing ./tideman a b c d < text4.txt.

You are right. changing to 4 works. I also tried it with a version I made named input.txt
5 Alice Bob Charlie Smith Alice Charlie Bob Smith Smith Bob Alice Charlie Smith Bob Alice Charlie Charlie Smith Bob Alice

It's a bit trippy because the output looks like it doesn't respond to the input file but the code works:

tideman/ $ ./tideman Alice Bob Charlie Smith < input.txt Number of voters: Rank 1: Rank 2: Rank 3: Rank 4: Rank 1: Rank 2: Rank 3: Rank 4: Rank 1: Rank 2: Rank 3: Rank 4: Rank 1: Rank 2: Rank 3: Rank 4: Rank 1: Rank 2: Rank 3: Rank 4:

You are right. changing to 4 works.

Good to know!

I also tried it with a version I made named input.txt

You need to use newlines instead of spaces, just like in test4.txt. This is done this way because of the way the code handles input.

This post was really helpful to me. Before reading the concept you shared, I have been struggling to understand how the locked pair algorithm works. Thank you very much. I made it.

Thank you so much for this post. The example you provided with a bigger graph really helped me understand what was going on. I was checking if the locked matrix has a single column with all false values to determine if there are cycles before reading your post.

Thnx a lot for this interesting explanation. It provided the right nudge I was need to implement the solution!!!

Thank you so much for this post. The example you provided with a bigger graph really helped me understand what was going on. I was checking if the locked matrix has a single column with all false values to determine if there are cycles before reading your post.

@Aliu9742 this is my strategy as well, but I'm getting two errors with the lock_pairs function. how did you change your strategy?

@abbasmaheryar, I created a separate function called is_valid_connection(a, b) that returns true if the new connection a -> b doesn't create a cycle, and false if the new a -> b connection does create a cycle. As the post mentions, recursion is probably the best option to solve this problem. This function would have to check what candidates are connected to the losing candidate b. Say if c and d are connected to b, the function would then have to check who is connected to c and d. The function stops calling itself either when it finds a dead end in the graph or it finds a cycle. What helped me understand the post is draw out the example it provides connection by connection and then draw a couple examples of my own.

Really thanks bro!

Your explanation blow up my head when I got to understand.

[a][b]
[c][a] // the loser here has already won on a locked pairs but it won't create a cycle
[c][b]

is there something else that I need to check ??

Thank you so much, bro! You help me correctly understand the requirement! After staring at your messages and struggling with various tools (paper, excel, whiteboard) for a whole day, I finally figure out the solution!!!
This problem set is so challenging and fascinating for me. I guess I can keep going and become a freelance coder in the soon future after this battle.
What a moment!

bro, thank you so much! I was stuck at this locked function for 3 days. Today I see this post so I tried again and I finally solved this now. Just summited it now. This post is really helpful!

Thanks a lot!!!!!! I was stuck at the lock_pair for like two days. It helps a lot!

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

Just Check for a candidate that has not any edges pointing towards them, in other words, check for a candidate that isn't in all pairs.loser places, if found, lock all edges and print the source's name, if not, then there is no source

It doesn't. The recursive function in this case is a helper one called within the function with void as input.

I'm trying to solve the tideman problem for the CS50x.(https://cs50.harvard.edu/x/2020/psets/3/tideman/). I tried to avoid using recursion. When I run check50 all the tests is passed except the one below:

:( lock_pairs skips final pair if it creates cycle lock_pairs did not correctly lock all non-cyclical pairs

I've tried to find the bug using debug50 but couldn't find anything.

heres the code below:

//lock pairs into the candidate graph in order without creating cycles
void lock_pairs(void)
{ 
    int winner,loser;
    for (int i=0;i<pair_count;i++)
    {
        winner=pairs[i].winner;
        loser=pairs[i].loser;
        if (cycle(winner,loser)==false)
        {
            locked[winner][loser]=true;
            printf("%i is locked over %i\n",winner,loser);
        }
    }
    return;
}
bool cycle(int winner , int loser)
{
    int start,end;
    start=winner;
    end=loser;
    bool loop=true;
    while (loop)
    {
        int n=0;
        while (n<candidate_count)
        {
            if (locked[end][n]==true)
            {
                end=n;
                if (end==winner)
                {
                    loop=false;
                    return true;
                }
                n=-1;
            }
            n+=1;
        }
        if (n==candidate_count)
        {
            loop=false;
            return false;
        }
    }
    return false;
} 

Make it one recursive function. It is much better.

Make it one recursive function. It is much better.

Thank you 🖤

@arafatrahman216, The condition end == winner is not always true. you can use the tests at the following URL to help, https://github.com/cs50/problems/blob/2020/x/tideman/testing.c

@arafatrahman216, The condition end == winner is not always true. you can use the tests at the following URL to help, https://github.com/cs50/problems/blob/2020/x/tideman/testing.c

Thank you. End stores the value of n, which is the loser for locked[end][n]==true condition. If the ultimate loser is the winner of the pair, then it creates a cycle.

Thanks for your explanation. I think there's a typo in this line:
...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....

Thanks a lot for the explanation!
time to go back and fight with that piece of code again :D

@daniswhoiam, thank you for that addition. I knew exactly what the problem was with the code not searching all branches, but I could have never come up with that magic on my own. I still can't fully wrap my head around it. Gonna debug it over and over till I understand.

Of course, thank you @nicknapoli82 too. I needed your explanation to even get a foothold with the lock_pairs function.

My problem is my code works; both the test case on cs50x and your test case give me correct answer but for some reason, on the last test check in cs50x, it's telling me I am wrong. I have no idea why.

EDIT: Never mind, figured it out right after I typed this. The rubber duck thing actually does work it seems.

@daxellwells
just a reminder : do not forget to exit (return) after printing the first winner in case of a tie election

Great article Nicholas, thank you so much for it! Put me on the right track form the beginning!

I wanted to say a HUGE THANK YOU to @nicknapoli82, @daniswhoiam and every single person who contributed to this thread. It was a huge help in helping to break down and understand the problem better. And everyones great attitude here definitely kept me excited to keep trying.
For anyone reading this, you got this.

This is such a clean and clear explanation, thanks a lot!

Can someone tell me if my pseudo code is on the right track??

https://codeshare.io/xvQY1d

Thank you so much! This really helps me understand the requirement and finally solve the problme!

Thank you so much! This really helps me understand the requirement and finally solve the problem!

I really don't understand how everyone is so instantly enlightened after reading the above. Maybe I'm just dense, but I just keep going around and around for a week now, and am no closer to solving sort_pairs.

Can someone at least confirm if this task can be achieved within lock_pairs, or does it indeed require a new function to facilitate the recursion, as suggested by most people?

Thank you so much! This really helps me understand the requirement and finally solve the problem!

I really don't understand how everyone is so instantly enlightened after reading the above. Maybe I'm just dense, but I just keep going around and around for a week now, and am no closer to solving sort_pairs.

Can someone at least confirm if this task can be achieved within lock_pairs, or does it indeed require a new function to facilitate the recursion, as suggested by most people?

I wrote a new function that uses recursion. I think the most important takeaway of this explanation is how it determine whether a pair should be locked or not, and I impletented that logic with code.

My order of sorted pairs is different, but sorted, and it results in a different graph, but with the correct winner and the graph is correct according to the sorted pair.

I will attach a screenshot as well of the output

My code:
#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
int winner;
int loser;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: tideman [candidate ...]\n");
return 1;
}

// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX)
{
    printf("Maximum number of candidates is %i\n", MAX);
    return 2;
}
for (int i = 0; i < candidate_count; i++)
{
    candidates[i] = argv[i + 1];
}

// Clear graph of locked in pairs
for (int i = 0; i < candidate_count; i++)
{
    for (int j = 0; j < candidate_count; j++)
    {
        locked[i][j] = false;
    }
}

// Clear prefernces array
for (int i = 0; i < MAX; i++)
{
    for (int j = 0; j < MAX; j++)
    {
        preferences[i][j] = 0;
    }
}

pair_count = 0;
int voter_count = get_int("Number of voters: ");

// Query for votes
for (int i = 0; i < voter_count; i++)
{
    // ranks[i] is voter's ith preference
    int ranks[candidate_count];

    // Query for each rank
    for (int j = 0; j < candidate_count; j++)
    {
        string name = get_string("Rank %i: ", j + 1);

        if (!vote(j, name, ranks))
        {
            printf("Invalid vote.\n");
            return 3;
        }
    }

    record_preferences(ranks);

    printf("\n");
}
printf("\n");
printf("Preferences: \n");
printf(" \t");
for (int i = 0; i < candidate_count; i++)
{
    printf("%i\t", i);
}
printf("\n\n");

for (int i = 0; i < candidate_count; i++)
{
    printf("%i\t", i);
    for (int j = 0; j < candidate_count; j++)
    {
        printf("%i\t", preferences[i][j]);
    }
    printf("\n");
}

printf("Pairs: \n");
add_pairs();
for(int i = 0; i < pair_count; i++)
{
    printf("Winner: %i\n", pairs[i].winner);
    printf("Loser: %i\n", pairs[i].loser);
    printf("\n");
}
sort_pairs();
printf("Sorted\n");
for(int i = 0; i < pair_count; i++)
{
    printf("Winner: %i\n", pairs[i].winner);
    printf("Loser: %i\n", pairs[i].loser);
    printf("\n");
}
lock_pairs();
printf("\n");
printf("lock: \n");
printf(" \t");
for (int i = 0; i < candidate_count; i++)
{
    printf("%i\t", i);
}
printf("\n\n");
for (int i = 0; i < candidate_count; i++)
{
    printf("%i\t", i);
    for (int j = 0; j < candidate_count; j++)
    {
        printf("%i\t", locked[i][j]);
    }
    printf("\n");
}
print_winner();
return 0;

}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
for (int candidateNumber = 0; candidateNumber < candidate_count; candidateNumber++)
{
if (strcmp(name, candidates[candidateNumber]) == 0)
{
ranks[rank] = candidateNumber;
return true;
}
}

return false;

}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
for (int rank = 0; rank < candidate_count; rank++)
{
int rankedCandidate = ranks[rank];
for (int candidate = rank + 1; candidate < candidate_count; candidate++)
{
preferences[rankedCandidate][ranks[candidate]]++;
}
}

return;

}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
pair_count = 0;

for (int i = 0; i < candidate_count; i++)
{
    for (int j = i; j < candidate_count; j++)
    {
        if (preferences[i][j] > preferences[j][i])
        {
            pairs[pair_count].loser = j;
            pairs[pair_count++].winner = i;
        }
        else if (preferences[j][i] > preferences[i][j])
        {
            pairs[pair_count].loser = i;
            pairs[pair_count++].winner = j;
        }
    }
}

return;

}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
for (int i = pair_count; i > 0; i--)
{
for (int j = i; j > 0; j--)
{
int winningCandidate = pairs[j].winner;
int losingCandidate = pairs[j].loser;
int previousWinningCandidate = pairs[j - 1].winner;
int previousLosingCandidate = pairs[j - 1].loser;
int candidateVotes = preferences[winningCandidate][losingCandidate] - preferences[losingCandidate][winningCandidate];
int previousCandidateVotes = preferences[previousWinningCandidate][previousLosingCandidate] - preferences[previousLosingCandidate][previousWinningCandidate];
if (candidateVotes > previousCandidateVotes)
{
pair temp = pairs[j];
pairs[j] = pairs[j - 1];
pairs[j - 1] = temp;
}
}
}

return;

}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
for (int i = 0; i < pair_count; i++)
{
bool skip = false;
int winner = pairs[i].winner;
int loser = pairs[i].loser;
locked[winner][loser] = true;

    // Checking for cycle in the EXISTING graph
    for (int column = 0; column < pair_count; column++)
    {
        if (locked[loser][column])
        {
            for (int row = 0; row < pair_count; row++)
            {
                if (locked[row][winner])
                {
                    skip = true;
                }
            }
        }
    }
    if (skip)
    {
        locked[winner][loser] = false;
    }
}

return;

}

// Print the winner of the election
void print_winner(void)
{
for (int column = 0; column < pair_count; column++)
{
int zeroCount = 0;
for (int row = 0; row < pair_count; row++)
{
if (locked[row][column] == false)
{
zeroCount++;
}
}
if (zeroCount == pair_count)
{
printf("%s\n", candidates[column]);
break;
}
}
return;
}

I'm new to coding and had to look up a solution otherwise it would have taken too long. This is the solution I found (courtesy of ddanner97):

bool cycle_pairs(int endCase, int start){
    
    if (endCase == start){
        
        return true;
        
    }
    
    for(int i = 0; i < candidate_count; i++){
        
        //check if each position in array is true/false
        //if true go onto next check
        if(locked[endCase][i]){
            //recursively check with current candidate as new end argument 
            //this loops until false is returned or base case is triggered, thus creating cycle and returning true
            if(cycle_pairs(i, start)){
                 
                 return true;
                 
            }
        }
  
    }
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for(int i = 0; i < pair_count; i++){
        
        if (!cycle_pairs(pairs[i].loser, pairs[i].winner)){
            
            locked[pairs[i].winner][pairs[i].loser] = true;
            
        }
        
    }
    return;
}

Using your reasoning, I hope I can provide an explanation of the logic in the context of a concrete example:

'For i number of candidates, if the strongest path is (0,1), (1,2), (2,3), (3,4) and (5,0). The first 4 pairs are locked in. Then as (5, 0) is only pair to pass first check ((0) [endcase], (1) [i]) call cycle_pairs recursively for ((1) (i) , (5) (start)). As (1, 2) is locked, recursively cycle (2, 5) etc.... until recursively cycle 5,5 which returns true. Similarly, if strongest path is (0,1), (1,5) and (5,0), (0, 1) and (1,5) are locked. (5, 0) passes first check, so call cycle_pairs (1,5). when i = 5, locked (1, 5) is true and cycle pairs ((i) (5), (5) returns true recursively. Thus in both instances, including the first instance where intermediate pairs connect the two cycling candidate pairs, the cycle pairs function always returns true if a cycle exists.'

It was really helpful, thank you so very much!!!

Your explanation was key for my completion of Tideman, thank you so much for your work! Extremely clear and concise, with the right amount of information and example for someone to figure this out by themselves. Nicknapoli82++

Thanks a lot man! When reading the tideman background, I got the false idea that a cycle is when there is no source for the graph. I've been working with that assumption for 3 or 4 days. Your explanation helped a bunch. props.

Makes no sense to me that the course teaches recursion without also teaching about how recursion works in the call stack.
The video you linked to should accompany the recursion video in the course instead of being shown later on.
Also they should've given a link to the concepts from graph theory that they used in the problem, I didn't even know graph theory was a thing until hours into working on the problem.
Maybe there is a "supplementary resources" page I am missing out on or something.
Thanks for going through the trouble of writing your clarification, I found it very useful

@nicknapoli82
Thanks for the info,

I understanded the general idea but I cannot convert it to code I see that I should use recursion but I cannot find how to use it
could anybody give me some clues or more details
and why my code is wrong?

Huge thanks for the explanation. What a challenge! Couldn't have done it without these tools.

https://github.com/cs50/problems/blob/fbf699155e3283e743b5ec50b833d014833edd83/tideman/testing.c#L250-L258
https://tideman.netlify.app/

Thanks to those who posted them

I have been stuck on this problems for months. It was relatively easy until lock_pair. I understand in principle what I need to do but I am struggling so so hard to translate it into code.
I do agree there is a fallacy in how this particular module is taught as it doesn't prepare you for understanding how recursion really works. There isn't even a preparatory exercise/lab before throwing you to the lions.

Edit: Finally solved it after making sure only the recursive cycle function stopped if a cycle was found BUT still checking for any remaining non-cyclical pairs by allowing the lock_pairs for-loop to complete. (Hint: cycleCreated for lock_pair is unnecessary)
(In hindsight, this was such a rookie mistake due to not understanding the questions fully😩)

Huge thanks to this thread since I was able to get a better understanding on how to approach the lock_pair question!
After a lot of trial and error, I almost got all of the requirements solved except for lock_pairs skips middle pair if it creates a cycle.
From my understanding, I think it may have something to do with how the code should break after a cycle has been found but everything seems to be working fine even when I tested it using case 15 from https://github.com/cs50/problems/blob/2020/x/tideman/testing.c.
Is there perhaps something else I might be missing?

void lock_pairs(void)
{
    // TODO
    int winner;
    int loser;
    bool cycleCreated = false;
    for (int i = 0; i < pair_count; i++)
    {
        if (cycleCreated == false)
        {
            winner = pairs[i].winner;
            loser = pairs[i].loser;
            // printf("Accessing Pair: %i | Winner: %i | Loser: %i\n", i, winner, loser);

            if (!cycle(winner, loser))
            {
                // printf("No Cycles created. Locking %i | %i\n", pairs[i].winner, pairs[i].loser);
                locked[pairs[i].winner][pairs[i].loser] = true;
            }
            else
            {
                cycleCreated = true;
            }
        }
        else
        {
            break;
        }
    }

    //  DEBUG
    // for (int x = 0; x < candidate_count; x++)
    // {
    //     for (int y = 0; y < candidate_count; y++)
    //     {
    //         printf("%s VS %s: %i\n", candidates[x], candidates[y], locked[x][y]);
    //     }
    // }
    return;
}

bool cycle(int winner, int loser)
{
    bool cycleCreated = false;
    if(loser == winner)
    {
        printf("Cycle when winner is %i and loser is %i\n",winner, loser);
        cycleCreated = true;
    }
    else
    {
        for (int i = 0; i < candidate_count; i++)
        {
            printf("Checking %i | %i\n", loser,i);
            if (locked[loser][i] == true)
            {
                printf("Potential cycle when loser is %i\n",i);
                cycleCreated = cycle(winner,i);
                if (cycleCreated)
                {
                    break;
                }
            }
        }
    }
    return cycleCreated;
}

lock_pairs skips middle pair if it creates a cycle Error:

case 15 and state of locked array after testing:

Initially, I created the below code (pseudocode) for checking the base case:

    for (int t = 0; t < pair_count; t++)

    {

        for (int z = t + 1; z < pair_count; z++)

        {

            if (pairs[t].loser == pairs[z].winner)

            {

                return true;

            }

        }

    }

After raising threads on Reddit , it became clear that instead of pairs array, I need to refer to locked array in order to lock. Still I am wondering if suppose there are only 3 pairs. If I understand correctly, above way of mine might work correct for the first 3 instances at least as for any sample pairs, first two are going to be locked and question of if cycle exists or not comes with the third. Third pair can be checked for lock or not even from the above code.

From the fourth pair, my way will fail (might or might not depending on the pair elements), and for correct results, definitely need to look from locked pairs.

Yo @nicknapoli82 I cannot thank you enough for posting this. I was stuck on this problem forever because after reading and watching the problem set instructions over and over, I took away an incorrect understanding of what a cycle is. I could not have solved this problem without your explanation. Thanks!

Makes no sense to me that the course teaches recursion without also teaching about how recursion works in the call stack.

This concerned me too. I knew about the recursion/call stack from earlier work and was really surprised that it wasn't explained in week 3.

I have been stuck on this problems for months. It was relatively easy until lock_pair. I understand in principle what I need to do but I am struggling so so hard to translate it into code. I do agree there is a fallacy in how this particular module is taught as it doesn't prepare you for understanding how recursion really works. There isn't even a preparatory exercise/lab before throwing you to the lions.

check out the practice problem "Recursive (atoi)" in week 3. It's a small but challenging recursive problem. It might help you wrap your head around recursion. Also check out the "Call Stack" video in week 4 (which I think should have been a part of week 3). It will really help with the "backwards" way recursion works (same with this Computerphile video".

I would like to thank you for this post. It helps me to understand and solve the problem.

Thank you so much!! I've been stuck for a MONTH on this lock_pairs function, this was the final thing I needed to get it perfect.

i had a doubt if anyones willing to clarify, the cycle check, do u do it to all the pairs or only the pairs that have already been locked, i mean while running through the program to check if it will create a cycle, do u only consider the pairs that have already been locked or all the pairs possible, dk how to write it any better than this but the c->d->b->c, in this would u consider d to b if it hadnt been locked, or b to c if it hadnt been locked or just leave it

    int check_cycle(int w, int x, int y) {
        if (x == w) {
            locked[w][y] = false;
            return 0;
        }
        for (int i = 0; i<candidate_count; i++) {
            if (locked[x][i] == true) {
                return check_cycle(w, i, y);
            }
        }
        return 0;
    }

This seems to work except for "lock_pairs skips final pair if it creates cycle" any idea?

Thanks so much! I'd been on this problem for 3 days. Your explanation helped a lot

Thank you kind person!

Thank you so much for the clarification, helped a lot!

Thank you! This explanation is golden.

You helped me a lot mate. Cheers!

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.

Thank you for this... This quoted part and the Tideman Testing tool finally allowed me to finished this problem.