CS50 Solution pset3 tideman

tideman.c

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

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];
bool lock = true;

// 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);
int comparator(const void *a, const void *b);
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 and the preferences array from garbage values
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
            preferences[i][j] = 0;
        }
    }

    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 i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[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 = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }
}

// function used for sort
int comparator(const void *a, const void *b)
{
    pair *ab = (pair *)a;
    pair *ba = (pair *)b;

    // uses pointers to access the preferences and check how much a candidate wins over another
    return (preferences[ba->winner][ba->loser] - preferences[ab->winner][ab->loser]);
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    qsort(pairs, pair_count, sizeof(pair), comparator);
}

bool has_cycle(int winner, int loser)
{
    while (winner != -1 && winner != loser)
    {
        bool found = false;
        for (int i = 0; i < candidate_count; i++)
        {
            if (locked[i][winner])
            {
                found = true;
                winner = i;
            }
        }
        if (!found)
        {
            winner = -1;
        }
    }
    if (winner == loser)
    {
        return true;
    }
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    //TODO
    for (int i = 0; i < pair_count; i++)
    {
        if (!has_cycle(pairs[i].winner, pairs[i].loser))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}

// Print the winner of the election
void print_winner(void)
{
    //TODO
    for (int col = 0; col < MAX; col++)
    {
        bool found_source = true;
        for (int row = 0; row < MAX; row++)
        {
            if (locked[row][col] == true)
            {
                found_source = false;
                break;
            }
        }
        if (found_source)
        {
            printf("%s\n", candidates[col]);
            return;
        }
    }
    return;
}

@chu999 it just break the loop. Meaning that there is no cycle on locking that relation

Although this code passes all the checks made on CS50, it seems to me that the has_cycle function is incomplete. Meaning it misses some cases where there is a cycle. Let me show with an example:

Imagine there are 4 candidates: A, B, C and D (for simplicity). The ordered pairs are (represented as {winner, loser}):

1. {A, D}
2. {A, B}
3. {C, B}
4. {D, C}
5. {B, D}
6. {A, C}

If you draw this simple diagram, you'll see that the fifth pair, {B, D}, is a pair that cannot be drawn, because it would create the cycle B -> D -> C -> B.

Even though that is the case, the function has_cycle seems to miss this case, and incorrectly returns false (meaning there is no cycle formed by adding the pair {B, D}.

It seems to me that the proper way to write such a function would be by using recursion. Although I could not figure out how to write it yet.

Please let me know if I am missing something or if someone figured out how to write this function using recursion.

Hi,
I'm not sure about whether my answer would be suitable to solve your doubt regarding 6 votes for the 4 candidates thing, yet I have figured out the recursive version of has_cycle()...

---

bool has_cycle(int original_winner, int current_loser)
{
    if (current_loser == original_winner)
        return true;

    for (int i = 0; i < pair_count; ++i)
    {
        if (pairs[i].winner == current_loser && locked[pairs[i].winner][pairs[i].loser])
        {
            if (has_cycle(original_winner, pairs[i].loser))
                return true;
        }
    }
    return false;
}

We are given a winner and a loser, original_winner and current_loser respectively, I'd talk about the base case later.
We'll make a recursive call has_cycle(original_winner /* this doesn't change */, pair[i].loser) for each new pair in pairs, where the current_loser is the winner, if that pair already has a edge locked in.

Now in the recursive call to has_cycle, if the original_winner that we passed in while calling the function in lock_pairs() is the same as the current_loser in the recursive call, this means we have circled around, thus a cycle exists, and we return true.

If no cycle exists, it returns false.

Test for some randomized testcases at this website, where the graph has a red edge, and do a dry-run of the above recursive algorithm on that graph. That might help you understand it better.

Hope the answer helped :)

Thanks :)