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

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.