1

I've been stuck on this function of the PSET for a couple of days now. I have met every requirement in check50 except for the one that says, ":( lock_pairs skips final pair if it creates a cycle; lock_pairs did not correctly lock all non-cyclical pairs"

Here is my code:

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdbool.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);
bool makes_cycle(int x, int y);
bool makes_cycle2(int tmp, int y);

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 every candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // Check if the name matches the candidates name ignoring case
        if (strcasecmp(name, candidates[i]) == 0)
        {
            // Store the index of that name into the user's "rank"th ranks array and return true
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // Loop through everybody in the voter's ranks
    for (int i = 0; i < candidate_count; i++)
    {
        // For every person after the person we're looking at in the voter's rank
        for (int j = i + 1; j < candidate_count; j++)
        {
            // Update preferences array
            preferences[ranks[i]][ranks[j]]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // Initialize variable "position" to keep track of position in pairs array
    int position = 0;
    // For every votable candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // For every votable candidate
        for (int j = 0; j < candidate_count; j++)
        {
            // If the people who prefer candidate[i] over candidate[j] is not 0
            if (preferences[i][j] > 0 && preferences[i][j] > preferences[j][i])
            {
                // Increment pair_count
                pair_count++;
                // Add the pair to the pairs array at index "position"
                pairs[position].winner = i;
                pairs[position].loser = j;
                // Increment positions for the next pair
                position++;
            }
        }
    }
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // Initialize a buffer pair struct
    pair temp;
    // Initialize variable to store value for selection sort
    int most = 0;
    // For every pair, organize the array by descending strength of victory
    for (int i = 0; i < pair_count; i++)
    {
        // For every pair, figure out largest strength of victory and store that in the firstmost index of the array
        for (int j = i; j < pair_count; j++)
        {
            // Access the winner and loser values as coordinates in the 2d preferences array
            int x = pairs[j].winner;
            int y = pairs[j].loser;
            // Find the strength of the candidate's victory
            int diff = preferences[x][y] - preferences[y][x];
            // If strength of victory is greatest yet, switch  values of the firstmost index with current index
            if (diff > most)
            {
                most = diff;
                temp.winner = pairs[i].winner;
                temp.loser = pairs[i].loser;
                pairs[i].winner = pairs[j].winner;
                pairs[i].loser = pairs[j].loser;
                pairs[j].winner = temp.winner;
                pairs[j].loser = temp.loser;
            }
        }
    }
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Initialize every value to false in locked_pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }
    // For every pair
    for (int i = 0; i < pair_count; i++)
    {
        // Initialize variables to the winner and loser values in pairs
        int x = pairs[i].winner;
        int y = pairs[i].loser;
        // If locking an edge does not create a cycle
        if (makes_cycle(x, y) == false)
        {
            // Lock in the edge
            locked[x][y] = true;
        }
    }
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // Search for the source of the graph by finding a person over whom nobody has an edge
    // For every candidate (horizontal on 2d locked array)
    for (int i = 0; i < candidate_count; i++)
    {
        // For every candidate (vertical on 2d locked array)
        for (int j = 0; j < candidate_count; j++)
        {
            // If nothing in the horizontal array of that candidate is true
            if (locked[j][i] == true)
            {
                break;
            }
            else if (locked[j][i] == false && j == candidate_count - 1)
            {
                printf("%s\n", candidates[i]);
                return;
            }
        }
    }
    return;
}


// If locking in an edge makes a cycle return false; otherwise return true
bool makes_cycle(int x, int y)
{
    // Store the value of y in a temp variable for now
    int tmp = x;
    bool makes_cycle = makes_cycle2(tmp, y);
    if (makes_cycle)
    {
        return true;
    }
    return false;
}

bool makes_cycle2(int tmp, int y)
{
    // If, when inserted into the x column, the value of y points to something, go to it and see if it leads to y
    // For every candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // If, when inserted into the x column, the value of y points to something
        if (locked[y][i] == true)
        {
            // Set y equal to that value
            y = i;
            // Check again until the value of y in the x column never edges over anything
            if (y == tmp)
            {
                return true;
            }
            // Call the function again FIGURE OUT POSITION THING
            makes_cycle2(tmp, y);
        }
    }
    return false;
}

I know the variable names are vague and there are several inefficiencies, but trying to fix these just led to more issues than before, so I just undid a couple hours of work to get back to the inefficient but more complete code. Could someone please explain why I am able to lock in a middle value correctly but not a final value? Thank you in advance for any advice you give me!

PS: I have asked this question in the discord server and someone said that where I changed the y variable in makes_cycle2() was where I was going wrong since my if condition would be messed up if I did that. If someone could explain what that means in addition to giving feedback on my code, it would be greatly appreciated! I hope you have a great day!

2

This is one of those times when I would recommend starting over. Try and break it down in terms of what you need your function to do, and build some pseudocode first. Some pointers:

  1. First, recursion is a good way of solving this. But chaining two functions out of lock_pairs() is a bit redundant. Try and have just one makes_cycle().
  2. What's the job of lock_pairs()? Probably to iterate through each existing winner/loser pair, marking it true in locked_pairs if the the loser does not already beat the winner in the existing locked pairs (either directly or via other pairs). So you should have a makes_cycle() function that you pass the winner and loser of each pair to, returning true if the loser beats the winner somehow already.
  3. Then, how should your makes_cycle function work? Well, its first return condition is simple. If the locked_pair[loser][winner] is true, just return true! But if it's not, what should we do next? We should look at everyone the loser beats, and see if they beat the winner? So makes_cycle should iterate through all locked_pairs[loser][?] (that evaluate true), passing each candidate the loser beats to another call to makes_cycle(), but with the original winner. If any of these candidates beat the original winner, it will return true and we should also return true to pass it back up the chain. Once you implement this it should be recursive by nature.
  4. If you complete this loop without returning true, then all that's left is to return false.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .