Tideman Voting Client

tideman.c

#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];

// 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);
// Added functions
bool makes_a_loop(int head, int tail);
string get_winner(int head);

int main(int argc, string argv[])
{
    /*
    // UNIT TESTING
    candidate_count = 3;
    int ranks[candidate_count];
    int attempted_tests = 0;
    int passed_tests = 0;

    candidates[0] = "Alice";
    candidates[1] = "Bob";
    candidates[2] = "Charlie";

    if (vote(0, "Alice", ranks)) {
        passed_tests++;

        if (ranks[0] == 0) {
            passed_tests++;
        }
    }
    attempted_tests++;
    attempted_tests++;

    if (!vote(1, "Larry", ranks)) {
        passed_tests++;
    }
    attempted_tests++;

    if (vote(1, "Bob", ranks)) {
        passed_tests++;
        if (ranks[1] == 1) {
            passed_tests++;
        }
    }
    attempted_tests++;
    attempted_tests++;

    if (vote(2, "Alice", ranks)) {
        passed_tests++;
        if (ranks[2] == 0) {
            passed_tests++;
        }
    }
    attempted_tests++;
    attempted_tests++;

    // =============================================
    // record_preferences unit tests
    // =============================================

    int ballot11[] = {2, 1, 0};
    int ballot12[] = {2, 1, 0};
    int ballot13[] = {1, 2, 0};

    record_preferences(ballot11);
    record_preferences(ballot12);
    record_preferences(ballot13);

    if (preferences[0][0] == 0 &&
        preferences[0][1] == 0 &&
        preferences[0][2] == 0 &&
        preferences[1][0] == 3 &&
        preferences[1][1] == 0 &&
        preferences[1][2] == 1 &&
        preferences[2][0] == 3 &&
        preferences[2][1] == 2 &&
        preferences[2][2] == 0) {
        passed_tests++;
    } else {
        printf("Alice beats Alice: %i\n", preferences[0][0]);
        printf("Alice beats Bob: %i\n", preferences[0][1]);
        printf("Alice beats Charlie: %i\n", preferences[0][2]);
        printf("Bob beats Alice: %i\n", preferences[1][0]);
        printf("Bob beats Bob: %i\n", preferences[1][1]);
        printf("Bob beats Charlie: %i\n", preferences[1][2]);
        printf("Charlie beats Alice: %i\n", preferences[2][0]);
        printf("Charlie beats Bob: %i\n", preferences[2][1]);
        printf("Charlie beats Charlie: %i\n", preferences[2][2]);
    }
    attempted_tests++;

    for (int i = 0; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count; j++) {
            preferences[i][j] = 0;
        }
    }

    int ballot1[] = {0, 1, 2};
    int ballot2[] = {0, 1, 2};
    int ballot3[] = {0, 1, 2};
    int ballot4[] = {1, 2, 0};
    int ballot5[] = {1, 2, 0};
    int ballot6[] = {2, 0, 1};
    int ballot7[] = {2, 0, 1};
    int ballot8[] = {2, 0, 1};
    int ballot9[] = {2, 0, 1};

    record_preferences(ballot1);
    record_preferences(ballot2);
    record_preferences(ballot3);
    record_preferences(ballot4);
    record_preferences(ballot5);
    record_preferences(ballot6);
    record_preferences(ballot7);
    record_preferences(ballot8);
    record_preferences(ballot9);

    if (preferences[0][1] == 7 && preferences[1][0] == 2 && preferences[1][2] == 5 && preferences[2][1] == 4 && preferences[2][0] == 6 && preferences[0][2] == 3) {
        passed_tests++;
    } else {
        printf("Alice beats Bob: %i", preferences[0][1]);
        printf("Bob beats Alice: %i", preferences[1][0]);
    }
    attempted_tests++;


    // =============================================
    // add_pairs unit tests
    // =============================================

    add_pairs();

    if (pair_count == 3) {
        passed_tests++;
    } else {
        printf("Pair count: %i\n", pair_count);
    }

    attempted_tests++;


    // =============================================
    // sort_pairs unit tests
    // =============================================

    candidate_count = 2;
    preferences[0][0] = 0;
    preferences[0][1] = 2;
    preferences[0][2] = 0;

    preferences[1][0] = 2;
    preferences[1][1] = 0;
    preferences[1][2] = 0;

    preferences[2][0] = 0;
    preferences[2][1] = 0;
    preferences[2][2] = 0;

    add_pairs();
    sort_pairs();
    if (pairs[0].winner == 0 && pairs[1].winner == 1) {
        passed_tests++;
    } else {
        printf("Pair count: %i\n", pair_count);
        printf("Pair 0 winner: %i\n", pairs[0].winner);
        printf("Pair 1 winner: %i\n", pairs[1].winner);
    }

    candidate_count = 3;

    attempted_tests++;

    record_preferences(ballot1);
    record_preferences(ballot2);
    record_preferences(ballot3);
    record_preferences(ballot4);
    record_preferences(ballot5);
    record_preferences(ballot6);
    record_preferences(ballot7);
    record_preferences(ballot8);
    record_preferences(ballot9);
    add_pairs();
    sort_pairs();

    // =============================================
    // lock_pairs unit tests
    // =============================================

    lock_pairs();
    if (locked[0][1] && locked[2][0] && !locked[1][2]) {
        passed_tests++;
    } else {
        printf("Alice -> Bob: %d\nCharlie -> Bob: %d\nBob -> Charlie: %d\n", locked[0][1], locked[2][0], locked[1][2]);
    }

    attempted_tests++;

    // =============================================
    // lock_pairs unit tests
    // =============================================

    if (strcmp(get_winner(0), "Charlie") == 0) {
        passed_tests++;
    } else {
        printf("%s\n", get_winner(0));
    }

    attempted_tests++;

    if (passed_tests == attempted_tests) {
        printf("Success: %i of %i tests passed", passed_tests, attempted_tests);
    } else {
        printf("Fail: %i of %i tests passed", passed_tests, attempted_tests);
    }
    printf("\n");
    // END OF UNIT TESTS
    */
    // 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 array for each new vote a voter makes
bool vote(int rank, string name, int ranks[])
{
    /*
    SPEC:
    The function takes arguments rank, name, and ranks. If name is a match for the name of a valid candidate, then you should update the ranks array to indicate that the voter has the candidate as their rank preference (where 0 is the first preference, 1 is the second preference, etc.)
    Recall that ranks[i] here represents the user’s ith preference.
    The function should return true if the rank was successfully recorded, and false otherwise (if, for instance, name is not the name of one of the candidates).
    You may assume that no two candidates will have the same name.
    */

    // Store the candidate number in the rank array at the slot indicated
    int candidate_index = -1;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i], name) == 0)
        {
            candidate_index = i;
            break;
        }
    }

    // If there isn't a candidate by the name provided, return false
    if (candidate_index == -1)
    {
        return false;
    }

    // Update ranks[rank] and return true
    ranks[rank] = candidate_index;
    return true;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    /*
    The function is called once for each voter, and takes as argument the ranks array, (recall that ranks[i] is the voter’s ith preference, where ranks[0] is the first preference).
    The function should update the global preferences array to add the current voter’s preferences. Recall that preferences[i][j] should represent the number of voters who prefer candidate i over candidate j.
    You may assume that every voter will rank each of the candidates.
    */
    // Update each slot in the global preferences array to show the last voter's preferences -- adding 1 to the number in each slot
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i; j < candidate_count; j++)
        {
            if (i != j) {
                preferences[ranks[i]][ranks[j]]++;
            }
        }
    }

    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    /*
    The function should add all pairs of candidates where one candidate is preferred to the pairs array. A pair of candidates who are tied (one is not preferred over the other) should not be added to the array.
    The function should update the global variable pair_count to be the number of pairs of candidates. (The pairs should thus all be stored between pairs[0] and pairs[pair_count - 1], inclusive).
    */
    // Compare all candidates to each other in preferences array
    // If there is a preference, record the winner and loser in the "pairs" array
    pair_count = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i; j < candidate_count; j++)
        {
            if (preferences[i][j] != preferences[j][i])
            {
                pair_count++;
                if (preferences[i][j] > preferences[j][i])
                {
                    pairs[pair_count - 1].winner = i;
                    pairs[pair_count - 1].loser = j;
                }
                else
                {
                    pairs[pair_count - 1].winner = j;
                    pairs[pair_count - 1].loser = i;
                }
            }
        }
    }

    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    /*
    The function should sort the pairs array in decreasing order of strength of victory, where strength of victory is defined to be the number of voters who prefer the preferred candidate. If multiple pairs have the same strength of victory, you may assume that the order does not matter.
    */
    // Precondition: pairs array is fully populated
    // Outcome: pairs array is sorted from strongest to weakest victory
    // Selection sort pairs array in place
    // Going left to right through the unsorted pairs until reaching end:
    for (int i = 0; i < pair_count; i++)
    {
        int max_strength = pairs[i].winner - pairs[i].loser;
        int strongest_pair = i;
        for (int j = i; j < pair_count; j++)
        {
            // * Record the "strength": winner preference - loser preference
            int strength = preferences[pairs[j].winner][pairs[j].loser] - preferences[pairs[j].loser][pairs[j].winner];
            if (strength < 0) { strength = strength * -1; }
            if (strength > max_strength)
            {
                // * If that strength is higher than the existing strongest, save that pair's key and strength
                max_strength = strength;
                strongest_pair = j;
                // * Look at the next pair and do it again
            }
            // * Once the end of the pairs is reached, swap the first unsorted pair with the strongest pair, and move the unsorted pair marker right
            pair tmp = pairs[i];
            pairs[i] = pairs[strongest_pair];
            pairs[strongest_pair] = tmp;
        }
    }
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    /*
    The function should create the locked graph, adding all edges in decreasing order of victory strength so long as the edge would not create a cycle.
    */
    // Starting with the first pair, record the pair ("original pair") and repeat until we find the end of the winner -> loser trail
    for (int i = 0; i < pair_count; i++)
    {
        int winner_to_lock = pairs[i].winner;
        int loser_to_lock = pairs[i].loser;
        // If following the loser trail of this loser has an end, lock the pair
        if (!makes_a_loop(winner_to_lock, loser_to_lock))
        {
            locked[winner_to_lock][loser_to_lock] = true;
        }
    }
    return;
}

// Does following locked wins by tail lead to an unlocked win?
bool makes_a_loop(int head, int tail)
{
    for (int i = 0; i < pair_count; i++)
    {
        // If the tail has won any locked match-ups vs head...
        if (pairs[i].winner == tail && locked[pairs[i].winner][pairs[i].loser])
        {
            if (pairs[i].loser == head)
            {
                return true;
            }
            else
            {
                return makes_a_loop(head, pairs[i].loser);
            }
        }
    }
    // If the tail has not won any locked match-ups, return true
    return false;
}

// Get the name of the person who's never lost
string get_winner(int head)
{
    // Find the strongest locked win
    for (int i = 0; i < pair_count; i++)
    {
        // If the head has lost any locked match-ups...
        if (pairs[i].loser == head && locked[pairs[i].winner][pairs[i].loser])
        {
            return get_winner(pairs[i].winner);
        }
    }
    // If the head has not lost any locked match-ups, return true
    return candidates[head];
}

// Print the winner of the election
void print_winner(void)
{
    /*
    The function should print out the name of the candidate who is the source of the graph. You may assume there will not be more than one source.
    */
    printf("%s\n", get_winner(0));
}