Solution to https://cs50.harvard.edu/x/2023/psets/3/tideman/

tideman.c

// #include <cs50.h> // rewrote with scanf and typedef
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef const char *string;

// 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);

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 preferences array
    for (int i = 0; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count; j++) {
            preferences[i][j] = 0;
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    // int voter_count = get_int("Number of voters: ");
    int voter_count;
    printf("Number of voters: ");
    scanf("%d", &voter_count);

    // Query for votes
    for (int i = 0; i < voter_count; i++) {
        // ranks[i] is voter's ith preference
        int ranks[MAX];

        // Query for each rank
        for (int j = 0; j < candidate_count; j++) {
            // string name = get_string("Rank %i: ", j + 1);
            printf("Rank %i: ", j + 1);
            char name[20];
            scanf("%s", &name);

            if (!vote(j, name, ranks)) {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        printf("--- recording preferences:\n");
        record_preferences(ranks);

        printf("\n");
    }

    printf("--- adding pairs:\n");
    add_pairs();
    printf("--- sorting pairs:\n");
    sort_pairs();
    for (int i = 0; i < pair_count; i++) {
        pair p = pairs[i];
        printf(" -- %s (%d) wins with %s (%d)\n", candidates[p.winner],
               preferences[p.winner][p.loser], candidates[p.loser],
               preferences[p.loser][p.winner]);
    }

    printf("--- locking pairs:\n");
    lock_pairs();
    printf("--- printing winner:\n");
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[]) {
    int candidate_index = -1;
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(candidates[i], name) == 0) {
            candidate_index = i;
            break;
        }
    }
    if (candidate_index == -1) {
        return false; // name given didn't match any candidate
    }

    for (int prev_rank = 0; prev_rank < rank; prev_rank++) {
        if (ranks[prev_rank] == candidate_index) {
            return false; // voted for the same candidate twice
        }
    }

    ranks[rank] = candidate_index;
    return true;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[]) {
    for (int win_rank = 0; win_rank < candidate_count - 1; win_rank++) {
        for (int lose_rank = win_rank + 1; lose_rank < candidate_count;
             lose_rank++) {
            printf(" -- winner %s ranked: %d, loser %s ranked: %d\n",
                   candidates[ranks[win_rank]], win_rank,
                   candidates[ranks[lose_rank]], lose_rank);

            preferences[ranks[win_rank]][ranks[lose_rank]] += 1;
        }
    }

    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void) {
    for (int cand_a = 0; cand_a < candidate_count - 1; cand_a++) {
        for (int cand_b = cand_a + 1; cand_b < candidate_count; cand_b++) {
            int a_preference_margin = preferences[cand_a][cand_b] // wins of a
                                      -
                                      preferences[cand_b][cand_a]; // wins of b
            if (a_preference_margin == 0)
                continue; // don't add a pair if it's a tie

            if (a_preference_margin > 0)
                pairs[pair_count] = (pair){.winner = cand_a, .loser = cand_b};
            else
                pairs[pair_count] = (pair){.winner = cand_b, .loser = cand_a};

            pair_count++;
        }
    }

    return;
}

// Comparison function to sort by strength of victory descending
//      strength of victory is voters who prefer the winner over loser
//      (ignore the votes where they prefer loser over winner)
// Return value:
//      <0  The element pointed to by p1 goes before p2
int compare_pairs(const void *p1, const void *p2) {
    const pair *pair1 = (const pair *)p1;
    const pair *pair2 = (const pair *)p2;
    int strength1 = preferences[pair1->winner][pair1->loser];
    int strength2 = preferences[pair2->winner][pair2->loser];

    // If strength1 larger, return negative
    return strength2 - strength1;
}

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

// Made this function for convenient early return
bool would_create_cycle(int new_from, int new_to) {
    // check for cycle by traversing all paths starting at new_to
    // and seeing if we get to new_from
    //
    // to avoid rearranging nodes_to_check, it will be used as
    // Last-In-First-Out (LIFO) queue, making it Depth-First-Search (DFS)
    int nodes_to_check[MAX]; // we can reach them from some visited node
    nodes_to_check[0] = new_to;
    int nodes_to_check_count = 1;

    int current_node;
    do {
        current_node = nodes_to_check[--nodes_to_check_count];

        if (current_node == new_from)
            return true; // cycle found

        // add all nodes we can visit from this one
        for (int j = 0; j < candidate_count; j++) {
            if (locked[current_node][j]) {
                // set after last one and increment count
                nodes_to_check[nodes_to_check_count++] = j;
            }
        }
    } while (nodes_to_check_count > 0);

    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void) {
    for (int pair_i = 0; pair_i < pair_count; pair_i++) {
        // true locked[i][j] means i wins with j, or an arrow from i to j
        int new_from = pairs[pair_i].winner;
        int new_to = pairs[pair_i].loser;

        printf(" -- checking cycle from %s to %s\n", candidates[new_from],
               candidates[new_to]);
        if (!would_create_cycle(new_from, new_to)) {
            locked[new_from][new_to] = true;
            printf(" -- locked in %s wins with %s\n", candidates[new_from],
                   candidates[new_to]);
        }
    }

    return;
}

// Print the winner of the election
void print_winner(void) {
    for (int candidate = 0; candidate < candidate_count; candidate++) {
        bool some_arrow_towards_this = false;
        for (int opponent = 0; opponent < candidate_count; opponent++) {
            if (locked[opponent][candidate]) {
                some_arrow_towards_this = true;
                break;
            }
        }
        if (!some_arrow_towards_this) {
            printf("%s\n", candidates[candidate]);
            return;
        }
    }

    printf("ERROR: No winner found\n");
    return;
}