PSET 3 - Tideman: Lock Pairs Function

Question

So basically I've got ': )' on everything except

: ( lock_pairs skips final pair if it creates cycle

Cause lock_pairs did not correctly lock all non-cyclical pairs

: ( lock_pairs skips middle pair if it creates a cycle

Cause lock_pairs did not correctly lock all non-cyclical pairs

However, I did two tests, one from the page that the problem set is on (https://gyazo.com/4a4c519ab79d62d4785ec1c978c62590) and got the right answer, Charlie, (https://gyazo.com/7547a1902883ca9963685a1585d829c7)

I found another test case and decided to run it (https://gist.github.com/nicknapoli82/2379634e87f24399ed1ed12c4c2e8c9a) and got the right answer again, (https://gyazo.com/4bb056f8084ecb03779751efb27522ed)

Does anyone know why those 2 frowns are still there? Is it a bug with my code or is something wrong with the checker?

#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] = {0};

// 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 find_number(int num_to_find, int num_list[], int array_size);
int find_source(void);
bool find_source2(int num);

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[])
{
    bool name_check = false;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] =  i;
            name_check = true;
        }
    }
    if (name_check)
    {

        return true;
    }
    else
    {
        return false;
    }
    // TODO
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for (int i = 0; i < candidate_count; i++)
    {
        int current_candidate_index = find_number(i, ranks, candidate_count);
        for (int j = 0; j < candidate_count; j++)
        {
            if (i == j)
            {
                preferences[i][j] = 0;
            }
            if (current_candidate_index < find_number(j, ranks, candidate_count))
            {
                preferences[i][j]++;
            }
        }
    }
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            if (preferences[i][j] == preferences[j][i])
            {
                continue;
            }
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                // pairs[pair_count-1].strength = preferences[i][j]-preferences[j][i];
                pair_count++;
            }
        }
    }
    printf("%i pairs\n", pair_count);
}

// Sort pairs in decreasing order by strength of victory - Selection Sort
void sort_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        int largest = i;
        int largest_diff = 0;
        int current_diff = 0;
        for (int j = i; j < pair_count; j++)
        {
            largest_diff = preferences[pairs[largest].winner][pairs[largest].loser] - preferences[pairs[largest].loser][pairs[largest].winner];
            current_diff = preferences[pairs[j].winner][pairs[j].loser] - preferences[pairs[j].loser][pairs[j].winner];
            if (largest_diff < current_diff)
            {
                largest = j;
            }
        }
        pair largest_pair = pairs[largest];
        pairs[largest] = pairs[i];
        pairs[i] = largest_pair;
    }
}


// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        locked[pairs[i].winner][pairs[i].loser] = true;
        if (find_source() == -1)
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            printf("%d ", locked[i][j]);
        }
        printf("\n");
    }
}

// Print the winner of the election
void print_winner(void)
{
    string winner = candidates[find_source()];
    printf("%s\n", winner);
    // TODO
    return;
}

// CHecks function for a certain number, returns the index

int find_number(int num_to_find, int num_list[], int array_size)
{
    for (int i = 0; i < array_size; i++)
    {
        if (num_to_find == num_list[i])
        {
            return i;
        }
    }
    printf("Something went horribly wrong.");
    return -1;
}

int find_source(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        bool lost = false;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[j][i] == true)
            {
                lost = true;
            }
        }
        if (!lost && find_source2(i))
        {
            return i;
        }
    }
    return -1;
}

bool find_source2(int num)
{
        bool lost = false;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[num][j] == true)
            {
                lost = true;
            }
        }
        return lost;
}

Answer 1

The logic of find_source won't really achieve the objective.

For each candidate, if no one beats that candidate, it will return false without checking subsequent candidates. However, pairs are locked in following the sorted order.

So, for example, if candidate 2 beats 3, 3 beats 4, and 4 beats 2, you have a cycle (which lock_pairs should avoid), but find_source will start with candidate 1, determine no one beats them, and return false.