tideman.c

#include <cs50.h>
#include <stdio.h>
#include <string.h>

#define MAX 9  // max number of candidates that can be in the election. 9

int preferences[MAX][MAX];  // preferences[i][j] is a 2d array to represent the number of voters who prefer candiate[i] over candidate[j], using an adjacency matrix

bool locked[MAX][MAX];  // 2d boolean array, used to keep track of the candidate graph. if locked[i][j] == TRUE, we've locked in the edge pointing from candidate "i" to candidate "j"

typedef struct  // a struct used to declare each pair, which has a winner & loser
{
    int winner;
    int loser;
}
pair;

string candidates[MAX];  // array of strings, for the candidates names, candidate[0] is the 1st candidate. candidate[1] is the 2nd candidate etc...
pair pairs[MAX * (MAX - 1) / 2];  // array of the MAX amount of candidates * (MAX amount of candidates - argc) / 2, so we can fit all of the pair structs in each index of pairs[]

int pair_count;  // global variables: pair_count & candidate_count, representing the number of "pairs" & number of "candidates" in the arrays: pairs[] & candidates[]
int candidate_count;

bool vote(int rank, string name, int ranks[]);  // function prototypes
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);
bool check_cycle(int winner, int loser);

int main(int argc, string argv[])
{
    if (argc < 2)  // check for invalid usage
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    candidate_count = argc - 1;  // populate array of candidates
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }

    for (int i = 0; i < candidate_count; i++) // loop through & populate the candidates[] array
    {
        candidates[i] = argv[i + 1]; // take user input for their "candidate" in argv (+1 to exclude ".\tideman") + store it in the candidate[] array
    }

    for (int i = 0; i < candidate_count; i++)  // outer nested forloop, to go through 1 row (i) of locked[][] at a time
    {
        for (int j = 0; j < candidate_count; j++)  // inner nested loop, to go through every column (j) of locked[][] before the outer loop executes again, to check the next row
        {
            locked[i][j] = false;  // set the current element at locked[i][j] to FASLE
        }
    }

    pair_count = 0;  // set pairs_count at the start of main() to equal 0.
    int voter_count = get_int("Number of voters: ");
    printf("\n");

    for (int i = 0; i < voter_count; i++)  // outer nested forloop, to go through every voter declared
    {
        int ranks[candidate_count];  // creates a seperate array of ranks[] for the voter at "i", with as many elements equal to "candidate_count". ranks[i] is this voter's ith preference

        for (int j = 0; j < candidate_count; j++)  // inner loop to query for the current voters prefered candidates, until this matches the candidate_count. it will then store these in this voters ranks[] preferences
        {
            string name = get_string("Candiate prefered rank %i: ", j + 1);  // record the candidate rank for the current "voter" at "j" (+1 to make it count from voter 1 insteaf of voter 0).
            if (!vote(j, name, ranks))  // the current value of "j" here represents the current voter being checked, the candidate "name" they picked & the current "ranks[]" 1d array for this voter. This is passed into vote()
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }
        printf("Current ranks array %d %d %d:", ranks[0], ranks[1], ranks[2]);
        printf("\n");
        record_preferences(ranks);

    }
    printf("\n");
    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}


bool vote(int rank, string name, int ranks[])  // update ranks given a new vote. this function takes in the arguments "rank", "name", and "ranks[]"" as mentioned on line 79
{
    for (int i = 0; i < candidate_count; i++)  // loop through against every potential candidate in the election
    {
        if (strcmp(candidates[i], name) == 0)  // check if the user's inputted "name" inpuuted on line 78 matches the current candidate in the candidates[] array looped through above. if TRUE (== 0)
        {
            ranks[rank] = i; // here "i" represents the index of current candidate in the candidates[] array. we update the ranks[] array with the ith candidate index, indicating this voter's current candidate preference to record.
            return true;  // function will return TRUE after grabbing this ith candidate + storing it in the correct index of the ranks[] array (first candidate voter picked into ranks[0], second into ranks[1] etc)
        }
    }
    return false;  // return FALSE if the above is not met, so this vote() function is looped through again in main()
}
void record_preferences(int ranks[])  // record each voter's preferences[][] by referencing their previous ranks[]
{
    printf("\n");
    for (int i = 0; i < candidate_count; i++)   // outer forloop to increment "i" (for the row candidate) from 0, representing the current index of the candidate rank[] we want to reference in the 2d preferences[HERE][] array accurately
    {
        for (int j = 0; j < candidate_count; j++)  // inner forloop to increment a j counting variable (for the column candidate) from 0 to represent the current index of the candidate rank[] we want to reference in the 2d preferences[][HERE] array accurately
        {
            if (i < j)
            {
                preferences[ranks[i]][ranks[j]]++; // add 1 tally mark to prefrences[i][j] in accordance to the current value of the counting variables i and j in the nested forloops, in context to the candidates in the 1d ranks[] array
            }
        }
    }
}

void add_pairs(void)  // Record pairs of candidates where one is preferred over the other
{
    for (int i = 0; i < candidate_count; i++) // outer forloop to increment a i counting variable (for the row candidate) from 0 to represent the current index of the candidate in the rows of preferences[HERE][]
    {
        for (int j = 0; j < candidate_count; j++)  // inner forloop to increment a j counting variable (for the column candidate) from 0 to represent the current index of the candidate in the columns of preferences[][HERE]
        {
            if (preferences[i][j] > preferences[j][i])  // if whatever is in preferences[i][j] has a greater value than in preferences[j][i] (that the candidate in preferences[i](Row) has more tally marks than the candidate in preference [j](Column)
            {
                pairs[pair_count].winner = i;  // update the [current index] of the pairs[] array and set the value taken from preferences[i] (column) to be the winner
                pairs[pair_count].loser = j;  // update the [current index] of the pairs[] array and set the value taken from preferences[j] (row) to be the loser
                pair_count++; // update 1 count to the paircount to tally the total number of pairs counted in this program
            }
        }
    }
    return;
}

void sort_pairs(void)
{
  while (1)  // this while loop is set to "true (1)" and it'll run forever until an exit condition is met
  {
      int swapped = 0;  // counting variable to indicate if a swap has been currently performed going through the bubble sort or not. This is set to 0 at the start of this while loop every time.
      pair temp;  // declaring a temp variable to store variables we want to swap in

      for (int i = 0; i < pair_count -1; i++)  // Loop through entire array of pairs[]. In a bubble sort , we need to -1 off of the pair_count being checked against. Because there's nothing to compare the last element to.
      {
          // check if the margin difference between the candidate.winner - the candidate.loser in [i] is LESS THAN the margin difference between the candidate.winner - the candidate.loser in [i + 1]
          if (preferences[pairs[i].winner][pairs[i].loser] - preferences[pairs[i].loser][pairs[i].winner] < preferences[pairs[i + 1].winner][pairs[i + 1].loser] - preferences[pairs[i].loser][pairs[i].winner])
          {
              temp = pairs[i];  // take the data in pairs[i] and move it inside of temp
              pairs[i] = pairs[i + 1];  // take the data in pairs[i + 1] and move it to pairs[i]
              pairs[i + 1] = temp;  // take the data we stores in temp and move it into [i +1] to complete the swap.
              swapped = 1;  // update swapped to == 1 to indicate the full swap has been coomplete
          }
      }

      if (swapped == 0) // check if swapped equals "false"
      {
          break;  // if it does, break the loop
      }
  }
}

void lock_pairs(void)  // lock pairs into the candidate graph in order, without creating cycles
{
    for (int i = 0; i < pair_count; i++)  // forloop through pairs[], to get the pairs with the highest strengh of victory (starting with pairs[0])
    {
        if (!check_cycle(pairs[i].winner, pairs[i].loser))  // if (no cycle will be created using check_cycles()) for the current .winner @ pairs[i] and .loser @ pairs[i]
        {
            locked[pairs[i].winner][pairs[i].loser] = true;  // set locked(for this)[.winner][.loser] at pairs[i] to TRUE, drawing a line;
        }
        printf("Locked[i][j] %s \n", locked[pairs[i].winner][pairs[i].loser] ? "true" : "false");
    }
    return;
}

bool check_cycle(int start, int end)  // "int start" is "pairs[i].winner" & "int end" is the original calling function's loser
{
    // base condition to check IF() an edge is found between the current ending node & starting node being checked
    // the base case can check IF an edge exists between two nodes anywhere but it can only do that with the help of the recursive function
    // to loop through and first check if that edge exists between all possible 2 nodes in the graph first
    if (locked[end][start] == true) // if (it finds an edge between the starting node and the ending node
    {
        return true; // return "true", indacating a edge exists between this starting node (candidate) and ending node (candidate)
    }

    // recursive case
    for (int i = 0; i < candidate_count; i++)   // loop through all the candidates in general, to see if an edge goes through (them as) any other nodes in the graph
    {
        if ((locked[i][start]) == true) // if an edge is found between the the ending node (indicated here by the candidate at [i] being looped through) and the starting node
        {
            /*
             * the check_cycles() function then calls itself, it'll pass the previous "end node" from the line above as the new "start node", with "locked[(i)][]" as the new "start" parameter.
             * it'll pass back and use the same "end node", which was originally passed into the function on line 182. (this remains unchanged). This allows us to keep track of the visited nodes + check
               the entire graph for an edge between the original ending node, and a new starting node each time
             */
            if (check_cycle(i, end) == true)
            {
                return true;
            }
        }
    }
    return false; // else return FALSE if no edges can be found betweeb the two nodes
 }

void print_winner(void) // print the winner of the election
{
    bool winner;

    for (int i = 0; i < candidate_count; i++)  // nested outer loop, through all rows in locked[i][], checking for candidate [i]
    {
        winner = true; // set winner to TRUE on each passthrough of this loop

        for (int j = 0; j < candidate_count; j++) // nested inner loop, through all of the columns in locked[][] for candidate [j] with this inner nested loop
        {
            if (locked[j][i] == true) // if at anyt point when looping through the columns of candidates in [j], if we find any candidate at j with an arrow pointing ot them from a candidate at [i]
            {
                winner = false; // assign the value of "false" to winner on this passthrough of this loop
            }
        }
        // if after looping through the entire locked[][] 2d array column by column above and every index in locked [j][i] was set to "false" as we want
        // determining candidate[j] has NO other candidates with an arrow pointing torwards them, winner is set to true
        if (winner == true)
        {
            printf("%s\n", candidates[i]);
        }
    }
    return;
}