PSet3 - Tideman (one approach)

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

// 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
    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: ");
#ifdef REDIR
printf ("%d\n", voter_count);
#endif
    // 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);

#ifdef REDIR
printf ("%-8s", name);
#endif
            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    puts ("\n(A)lice (B)ob (C)harlie  -  preferences\n\n   A  B  C");
    for (int k = 0; k < candidate_count; k++) {
        putchar ('A' + k);
        for (int l = 0; l < candidate_count; l++)
            printf ("  %d", preferences[k][l]);
        putchar ('\n');
    }
    putchar ('\n');

    add_pairs();

    puts ("Pre-sort Pair Order:");
    for (int k = 0; k < pair_count; k++)
        printf ("   (%c, %c)\n", 'A' + pairs[k].winner, 'A' + pairs[k].loser);
    putchar ('\n');

    sort_pairs();

    puts ("Post-sort Pair Order:");
    for (int k = 0; k < pair_count; k++)
        printf ("   (%c, %c)\n", 'A' + pairs[k].winner, 'A' + pairs[k].loser);

    lock_pairs();

    putchar ('\n');

    print_winner();

    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    int idx = 0;
    for (; idx < candidate_count; idx++)
        if (strcmp (name, candidates[idx]) == 0)
            break;
    if (idx == candidate_count)
        return false;

    ranks[rank] = idx;

    return true;
}

// 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 = 0; j < candidate_count; j++)
            if (j != i && preferences[i][j] > preferences[j][i]) {
                pairs[pair_count].winner = i;
                pairs[pair_count++].loser = j;
            }
}

int cmppairs (const void *a, const void *b)
{
    const pair *pa = a, *pb = b;
    /* sort descending on preferences value (conditional prevents possible overflor)
     * equivalent to:
     *   preferences[pa->winner][pa->loser] - preferences[pb->winner][pb->loser]
     */
    return (preferences[pa->winner][pa->loser] < preferences[pb->winner][pb->loser]) -
           (preferences[pa->winner][pa->loser] > preferences[pb->winner][pb->loser]);
}

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

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int cycle[pair_count];  /* VLA to capture occurrence of arrow for candidate */
    memset (cycle, 0, pair_count * sizeof *cycle);

    for (int i = 0; i < pair_count; i++) {
        if (i == pair_count - 1) {              /* if last pair, check cycle */
            int sum = 0;
            /* sum current candidates with arrows */
            for (int j = 0; j < pair_count; j++)
                sum += cycle[j];
            /* if single candidate unlocked & arrow would lock candidate's edge */
            if (sum == i && cycle[pairs[i].loser] == 0)
                break;  /* don't lock edge */
        }
        /* mark arrow (edge) on losing candidate, so source stays zero */
        locked[pairs[i].loser][pairs[i].winner] = true;
        cycle[pairs[i].loser] = 1;
    }
}

// Print the winner of the election
void print_winner(void)
{
    for (int i = 0; i < candidate_count; i++) {
        printf ("%-8s", candidates[i]);
        for (int j = 0; j < candidate_count; j++)
            printf ("  %d", locked[i][j] ? 1 : 0);
        putchar ('\n');
    }

    for (int i = 0; i < candidate_count; i++) {
        int j = 0;
        for (; j < candidate_count; j++)
            if (locked[i][j])
                break;
        if (j == candidate_count) {
            printf ("\nWinner: %s\n", candidates[i]);
            return;
        }
    }
}

/**
Compile to allow redirecting file as input:

gcc -Wall -Wextra -pedantic -Wshadow -std=c11 -Ofast -DREDIR -o tideman tideman.c -lcs50

Testing data file "votes.txt":

9
Alice
Bob
Charlie
Alice
Bob
Charlie
Alice
Bob
Charlie
Bob
Charlie
Alice
Bob
Charlie
Alice
Charlie
Alice
Bob
Charlie
Alice
Bob
Charlie
Alice
Bob
Charlie
Alice
Bob

Example Use/Output:

./tideman Alice Bob Charlie < votes.txt
Number of voters: 9
Rank 1: Alice   Rank 2: Bob     Rank 3: Charlie
Rank 1: Alice   Rank 2: Bob     Rank 3: Charlie
Rank 1: Alice   Rank 2: Bob     Rank 3: Charlie
Rank 1: Bob     Rank 2: Charlie Rank 3: Alice
Rank 1: Bob     Rank 2: Charlie Rank 3: Alice
Rank 1: Charlie Rank 2: Alice   Rank 3: Bob
Rank 1: Charlie Rank 2: Alice   Rank 3: Bob
Rank 1: Charlie Rank 2: Alice   Rank 3: Bob
Rank 1: Charlie Rank 2: Alice   Rank 3: Bob

(A)lice (B)ob (C)harlie  -  preferences

   A  B  C
A  0  7  3
B  2  0  5
C  6  4  0

Pre-sort Pair Order:
   (A, B)
   (B, C)
   (C, A)

Post-sort Pair Order:
   (A, B)
   (C, A)
   (B, C)

Alice     0  0  1
Bob       1  0  0
Charlie   0  0  0

Winner: Charlie

*/