CS50x 2022 Problem Set 3 — Tideman

step-by-step guide to the ‘Tideman’ problem in CS50

Photo by Arnaud Jaegers on Unsplash

NOTE: This guide assumes you are attempting to solve PSet 3 in CS50 and are familiar with the problem description, which will not be repeated here.

Summary:
The Tideman election problem is a continuation of the ‘Plurality’ lab in Week 3 of the CS50x course. Yet, it is a significantly more challenging problem to solve due to one key difference: A Tie-Breaking mechanism.

In short, the Tideman Election includes more complex logic that does more than account for total votes. It pits candidates against each other in pairs, considers the strength of preference of one candidate over another, then sorts the pairs to determine the winner.

Objective:
Complete 6 functions: vote, record_preferences, add_pairs, sort_pairs, lock_pairs, print_winner; all of which when combined, will help determine the winner of a Tideman Election.

Functions (From CS50)
vote
— The function takes arguments rank, name, and ranks. If name is a match for the name of a valid candidate, then you should update the ranksarray to indicate that the voter has the candidate as their rank preference (where 0 is the first preference, 1 is the second preference, etc.)
— ranks[i] here represents the user’s ith preference.
— The function should return true if the rank was successfully recorded, and false otherwise (if, for instance, name is not the name of one of the candidates).

record_preferences
— The function is called once for each voter, and takes as argument the ranks array, (recall that ranks[i] is the voter’s ith preference, where ranks[0] is the first preference).
— The function should update the global preferences array to add the current voter’s preferences. Recall that preferences[i][j] should represent the number of voters who prefer candidate i over candidate j.

add_pairs
— The function should add all pairs of candidates where one candidate is preferred to the pairs array. A pair of candidates who are tied (one is not preferred over the other) should not be added to the array.
— The function should update the global variable pair_count to be the number of pairs of candidates. (The pairs should thus all be stored between pairs[0] and pairs[pair_count - 1], inclusive).

sort_pairs
— The function should sort the pairs array in decreasing order of strength of victory, where strength of victory is defined to be the number of voters who prefer the preferred candidate. If multiple pairs have the same strength of victory, you may assume that the order does not matter.

lock_pairs
— The function should create the locked graph, adding all edges in decreasing order of victory strength so long as the edge would not create a cycle.

print_winner
— The function should print out the name of the candidate who is the source of the graph. You may assume there will not be more than one source.

Function Explanations

vote

The vote function is called once for EVERY ranking of a candidate (j), casted by a voter (i). This is represented by the nested loop contained in the main function. I.E If there were 3 candidates and 3 voters, vote would be called 3 times/voter, to determine each voters 1st [0], 2nd [1], 3rd [2] ranking, for a total of 9 times. false is returned if an invalid candidate is entered.

vote does 2 things
1. determine if candidate is valid
2. update ranks array with voter’s preference

The order of candidates is defined by the user as command line arguments when the program is executed. Their order in the candidates array, which determines their [index], is what will eventually be stored in the ranks array. ./tideman Alice Bob Charlie gives rise to Alice[0], Bob[1], Charlie[2]. A vote which ranks Charlie, Bob, Alice in that order, is represented in ranks array as [2, 1, 0].

// Iterate through candidates 
for (int i = 0; i < candidate_count; i++)
{
    // Check candidate is valid
    if (strcasecmp(candidates[i], name) == 0)
    {
        // Store the INDEX of candidates.
        ranks[rank] = candidate_index;
        return true;
    }
}
// ranks = [0, 2, 1] => 1. Alice, 2. Charlie, 3. Bob
return false;

Figure 1: Ranks matrix for a given set of ballots

record_preferences

As the voter’s preference is recorded only once a SINGLE ballot is cast, This function is only called once/voter, outside of the loop which calls vote. Voter’s preference of candidate (i) over candidate (j) is then recorded and tallied.

record_preferences does 1 thing
1. update preferences[i][j] array (2D array)

A nested loop must be used here, as a comparison must be made for the preferred (i) candidate over the other (j). Two things to note: 1. A candidate cannot be preferred over itself. 2. Last candidate is not preferred over anyone. 1 means we can stop the outer loop before the final candidate, and 2 means we have to start the inner loop (j) from (i+1), as a preference is tallied only when j is to the right of i. Once these conditions are met, the loop will increase the count in preferences[preferred_candidate][candidate] whose indexes are obtained from ranks[i] and ranks[j].

// Iterate through ranks array. stop before the last, as last candidate is not preferred over anyone
for (int i = 0; i < candidate_count - 1; i++)
{
    int preferred_candidate = ranks[i];
        for (int j = i + 1; j < candidate_count; j++)
        {
            int candidate = ranks[j];
            if (!preferences[preferred_candidate][candidate])
            {
                // update count if doesn't exist 
                preferences[preferred_candidate][candidate] = 1;
            }
            else
            {
                // increase count
                preferences[preferred_candidate][candidate]++;
            }
        }
}
return;

Figure 2: Preferences Matrix Populated

add_pairs

This is where it begins to get complicated. add_pairs must populate pairs array with the pair typedef struct defined in main which is an object containing the index of the winner and loser. The pair_count must be updated when a pair is created. However, if a draw is encountered, a pair SHOULD NOT be added.

Similarly to add_preferences, a nested loop must be used, with the nested loop starting from (i+1) and counting up to the total number of candidates. One special thing to note is that because comparing A — B is essentially the same as B — A, we can prevent repeat checks of preferences, by stopping the outer loop at the midpoint of the total number of candidates (round up for even numbers).

We also note that candidates do not need to be checked against themselves. With this in mind, the inner loop thus first rules out a (i != j) — self check and a (preferences[i][j] != preferences[j][i]) — draw. Once that is done, a check is done to determine if the number of voters who prefer candidate i over candidate j — preferences[i][j] is more than voters who prefer candidate j over candidate i — preferences[j][i], in which case i is the winner. A reverse check is done, in which case j is the winner.

The pair struct is updated with the indexes of the winners and losers, and as the global variable pair_count == 0 , it must be incremented ONLY once a pair has been created, in order for pairs array to be built sequentially.

// iterate through preferences array. only need to proceed halfway as bottom is repeated but in reverse.
for (int i = 0; i < ceil(candidate_count / 2.0); i++)
{
    // prevent adding repeat pairs by moving one index ahead.
    for (int j = i + 1; j < candidate_count; j++)
    {
        if (i != j && preferences[i][j] != preferences[j][i])
        {
            // DO NOT ADD pair if it is a draw OR if already exists
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
            }
            // update global var pair_count
            pair_count++;
        }
    }
}
return;

Figure 3: Illustration of progression of add_pairs

sort_pairs

Each pair of winner and loser has a ‘strength’ preference. The larger the margin of voter preference of the winner over the loser, the ‘stronger’ the victory. The strength can be calculated using the preferences array, where strength = preferences[winner][loser] — preferences[loser][winner]. sort_pairs must sort the pairs in decreasing strength of victory.

Here it is up to us to use any sorting algorithm we prefer. Assuming you have gone through Week 3’s lectures, there are 3 at your disposal: selection sort, bubble sort, merge sort. I decided to use merge sort, but as it’s discretionary I will not cover the logic, which is a quick google search away. This video helped me a LOT.

For my implementation, a strength array was created which was used as a ‘reference’ array and mapped to pairs with the index. Both strength and pairs array were passed into my vanilla merge_sort function and sorted simultaneously.

void sort_pairs(void)
{
    // loop through pairs array
    int strength[pair_count];
    for (int i = 0; i < pair_count; i++)
    {
        // calculate strength of victory
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        strength[i] = preferences[winner][loser] - preferences[loser][winner];
    }
    // use the index of the strength array, sort pairs at the same time.
    // implement your own sort function here
    merge_sort_recur(pairs, strength, 0, pair_count - 1);
    return;
}

lock_pairs

This function was the one I could not solve myself, and had to resort to help online in order to get it right. The reason is because there is a recursive logic (could also be done non-recursively) to lock pairs, and it’s difficult to wrap your head around. In short, lock_pairs should iterate through the pairs array, check if the loser(1st step) of the current pair is a winner(2nd step) of another pair that was locked previously, and if so, check AGAIN if the loser(2nd step) of the 2nd pair is a winner (3rd step)…. until either of these conditions break the recursion:

1. the end of a chain is reached (pair is LOCKED)
2. the chain cycles back to the winner(1st step) of the first pair (skip pair)

With this in mind, there is a need to define a separate recursive function check_cycle that accepts a winner and a loser, in order to determine the presence of any locked pairs. As long as locked[loser][j] is true, indicating a prior locked pair, check_cycle calls itself recursively until there isn’t any more locked pairs to check, and false will be returned at the end of the for loop. Otherwise, a cycle is encountered when a loser of prior locked pair represented by (j) == winner of the initial pair, which returns true.

As the conditions above suggest, there are TWO base cases that break the recursion.

1. recursive function finishes iterating through an entire chain of locked pairs without encountering a cycle. return false
2. winner encounters itself in a cycle (winner == loser). return true

bool check_cycle(int winner, int loser)
{
    // (BASE CASE 1)
    // check that the previous locked in loser, is not the same as the current winner. indicates a loop.
    
    if (winner == loser)
    {
        return true;
    }
    // using indices of winner/loser, we check first if loser has won in any previously locked pair, and if yes, start building out a chain
    for (int j = 0; j < candidate_count; j++)
    {
        // if current loser has won in a previously locked pair, a cycle may exist. otherwise just carrying on checking for locked edges
        if (locked[loser][j])
        {
            // 'j' is the 'loser' of the next cycle down.
            // we carry on the check recursively with the new loser
            if (check_cycle(winner, j))
            {
                return true;
            }
        }
    }
    // (BASE CASE 2) - no cycles exist, the loop ends.
    return false;
}

lock_pairs

Once check_cycle is complete, implementing it in lock_pairs is trivial, iterating through the pairs array which will provide the information to pass as arguments into check_cycle.

void lock_pairs(void)
{
    // update locked[winner][loser] in decreasing order of victory strength, as long as there is no cycle
    for (int i = 0; i < pair_count; i++)
    {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        if (!check_cycle(winner, loser))
        {
            // lock in edge
            locked[winner][loser] = true;
        }
    }
    return;
}

print_winner

The final function can be a little tricky, and has a small detail that is very easy to miss. Recall that at this point, once all pairs have been successfully locked in, there should only be ONE source. I.E a candidate that beats every other candidate, and who has NO arrows pointing toward them (graphical representation). In the locked array, this means that the candidate has no true values in their COLUMN.

Figure 4: Locked Matrix representing winner.

Figure 5: Graphical representation of winner

Determining the winner is thus trivial, we simply iterate through the locked[i][j] array, and find the candidate with the highest count of false.

void print_winner(void)
{
    int winner;
    int max = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        int falses = 0; // keep track of falses per candidate
        for (int j = 0; j < candidate_count; j++)
        {
            if (!locked[j][i])
            {
                falses++;
            }
        }
        
        if (falses > max)
        {
            max = falses;
            winner = i;
        }
    }
    printf("%s\n", candidates[winner]);
    
    return;
}

There are many other helper functions I created along the way to help me visualise the arrays like print_preferences, print_pairs etc. which really helped me debug my solutions. You may find it useful doing the same.

Conclusion

This problem is a LOT more difficult than the prior weeks, so don’t give up if you find yourself struggling. While none of these functions can be considered the ‘best’, I certainly am a fair bit more comfortable now with sorting and recursion. It still will take some time for all the logic to set in, but I hope seeing all green for check50 will give you the same endorphin rush as it did for me. On to Week 4!