0

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;
}
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.

3
  • Hello, tysm for the response. So I took your advice and implemented another function, "find_source2" basically what this does is make sure that the candidate number has at least one victory. So in this case: if candidate 2 beats 3, 3 beats 4, and 4 beats 2, it would check candidate 1 and see that it hasn't beaten anyone else so the find_source returns -1. However, after doing this it still doesn't work, do you know why? (I edited the code above with the function so you can see it) Dec 15 '20 at 0:05
  • You might want to revisit the assignment (particularly the guide video) and work on some pseudocode to really get a solid understanding of what your functions should achieve. The job of lock_pairs isn't to identify a source (i.e. someone who isn't beaten by anyone), but rather to lock in each sorted pair so long as it doesn't create a circular path. So if your pairs were 1 beats 2, 2 beats 3, and 4 beats 1, lock_pairs() should lock them all. But if the next pair were 3 beats 4, or 3 beats 1, it shouldn't be locked, because now you have a circular path.
    – Sentox
    Dec 15 '20 at 1:45
  • In other words, if you can follow a path of winners and losers in an infinite loop upon locking a pair, you shouldn't lock that pair. Finding a source, a candidate who isn't defeated by anyone else, is the job of print_winner(), not lock_pairs().
    – Sentox
    Dec 15 '20 at 1:45

You must log in to answer this question.

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