CS50 Pset3 Tideman - Lock pair and print winner

Question

I have been facing issues on the lock_pair and print_winner on the Tideman pset3 (context here: https://cs50.harvard.edu/x/2020/psets/3/tideman/#:~:text=check50%20cs50/problems/2020/x/tideman ). Tried my best to debug but I can't seem to skip the pairs that create a cycle. Please seek all the help.

:) tideman.c exists

:) tideman compiles

:) vote returns true when given name of candidate

:) vote returns false when given name of invalid candidate

:) vote correctly sets rank for first preference

:) vote correctly sets rank for all preferences

:) record_preferences correctly sets preferences for first voter

:) record_preferences correctly sets preferences for all voters

:) add_pairs generates correct pair count when no ties

:) add_pairs generates correct pair count when ties exist

:) add_pairs fills pairs array with winning pairs

:) add_pairs does not fill pairs array with losing pairs

:) sort_pairs sorts pairs of candidates by margin of victory

:) lock_pairs locks all pairs when no cycles

:( lock_pairs skips final pair if it creates cycle

lock_pairs did not correctly lock all non-cyclical pairs

:( lock_pairs skips middle pair if it creates a cycle

lock_pairs did not correctly lock all non-cyclical pairs

:( print_winner prints winner of election when one candidate wins over all others

print_winner did not print winner of election

:( print_winner prints winner of election when some pairs are tied

print_winner did not print winner of election

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.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;
        }
    }

    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");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

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

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for(int r = 0; r < candidate_count; r++)
    {
        for(int rc = 0; rc < candidate_count; rc++)
        {
            if(r < rc)
            {
                preferences[ranks[r]][ranks[rc]]++;
            }
        }
    }
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for(int row = 0; row < candidate_count; row++)
    {
        for(int column = 0; column < candidate_count; column++)
        {
            if(preferences[row][column] > preferences[column][row])
            {
                pairs[pair_count].winner = row;
                pairs[pair_count].loser = column;
                pair_count++;
            }
        }
    }
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    int maxindex;
    for(int a = 0; a < pair_count - 1; a++)
    {
        maxindex = a;
        int largestdiff = preferences[pairs[a].winner][pairs[a].loser] - preferences[pairs[a].loser][pairs[a].winner];

        for(int b = a + 1; b < pair_count; b++)
        {
            if(preferences[pairs[b].winner][pairs[b].loser] - preferences[pairs[b].loser][pairs[b].winner] > largestdiff)
            {
                largestdiff = preferences[pairs[b].winner][pairs[b].loser] - preferences[pairs[b].loser][pairs[b].winner];
                maxindex = b;
            }
        }
        pair max = pairs[maxindex];
        pairs[maxindex] = pairs[a];
        pairs[a] = max;
    }
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    //Set everything to false first
    for(int row = 0; row < candidate_count; row++)
    {
        for(int column = 0; column < candidate_count; column++)
        {
            locked[row][column] = false;
        }
    }

    //Set the first pair to true
    locked[pairs[0].winner][pairs[0].loser] = true;

    //Iterate each pair and skip if there is a cycle
    for(int b = 1; b < pair_count; b++)
    {
        for(int c = b - 1; c > -1; c--)
        {
            if(pairs[b].winner == pairs[c].loser)
            {
               locked[pairs[b].winner][pairs[b].loser] = false;
               break;
            }
        }
        locked[pairs[b].winner][pairs[b].loser] = true;
    }
}

// Print the winner of the election
void print_winner(void)
{
    string winner = candidates[0];
    for(int column = 0; column < candidate_count; column++)
    {
        for(int row = 0; row < candidate_count; row++)
        {
            if(locked[row][column] == true)
            {
                winner = candidates[column + 1];
                break;
            }
            else
            {
                winner = candidates[column];
                if(row == candidate_count)
                {
                    break;
                }
            }
        }
    }
    printf("%s\n", winner);
}

Answer 1

First, you don't need to set all locked pairs to false in the lock_pairs function. The main function already does that. DRY. Second, you are not correctly checking for cycles. Given a pair A beats B, you should iterate over all candidates who lost to B. Then you should iterate over all candidates who lost to the candidates who lost to B. Then iterate to the candidates who lost to the ones who lost to the ones who lost to B, and so on. If, at any time, A pops up, you immediately ends the loop. It is a cycle. The pair A beats B should not be locked. Else, if the iteration ends without finding A, it's not a cycle, and you can lock the pair