cs50 Problem Set 3 - Tideman Solution

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

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: ");

    // 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[])
{
    // TODO
    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[])
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[j]] += 1;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // TODO
    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++;
            }
        }
    }
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        int max = i;
        for (int j = i + 1; j < pair_count; j++) {
            if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[max].winner][pairs[max].loser])
            {
                max = j;
            }
        }
        pair temp = pairs[i];
        pairs[i] = pairs[max];
        pairs[max] = temp;
    }
    return;
}

bool is_circle(int loser, int winner)
{
    // Base Case 1: if path exist
    if (loser == winner) {
        return true; // it forms a cycle
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if(locked[loser][i]) //check if loser is locked with a candidate
        {
            return is_circle(i, winner); // check if that candidate is locked with  winner
        }
    }

    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 (!is_circle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }

    }
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        bool isLoser = false;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[j][i])
            {
                isLoser = true;
                break;
            }

        }

        if (isLoser) continue;
        if(!isLoser) 
        {
            printf("%s\n", candidates[i]);
        }
    }
    return;
}

Now everything is fine

bool cycle(int winner, int loser)
{
    // if path exist
    if (locked[loser][winner] == true) 
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        // check if winner is locked
        if(locked[i][winner]) 
        {
            return cycle(i, loser); 
        }
    }
    return false;

Changing it to
return cycle(loser, i);
worked for me... because then you are checking whether that specific candidate (candidate i) has lost to the original loser, thus creating a cycle/circle...

Now everything is fine

bool cycle(int winner, int loser)
{
    // if path exist
    if (locked[loser][winner] == true) 
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        // check if winner is locked
        if(locked[i][winner]) 
        {
            return cycle(i, loser); 
        }
    }
    return false;

Can you please elaborate on why the former didn't work and this worked? I am breaking my head over it. Thanks

Now everything is fine

bool cycle(int winner, int loser)
{
    // if path exist
    if (locked[loser][winner] == true) 
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        // check if winner is locked
        if(locked[i][winner]) 
        {
            return cycle(i, loser); 
        }
    }
    return false;

Can you please elaborate on why the former didn't work and this worked? I am breaking my head over it. Thanks

Because my version checks if pair is locked, so graph exists, previous version just checks if candidate is returns to himself. This is wrong, we should check for pairs not for alone candidate. It's hard for me to explain, everything was clear for me when I draw the table of pairs and mark locked cells, that's how I understand the algorithm. Maybe this will work for you, good luck! ;)

Now everything is fine

bool cycle(int winner, int loser)
{
    // if path exist
    if (locked[loser][winner] == true) 
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        // check if winner is locked
        if(locked[i][winner]) 
        {
            return cycle(i, loser); 
        }
    }
    return false;

I think it's wrong because the loop is checking only on the first 'i' value which is locked with winner for possible circle but not all 'i' values.

ranks[rank] = i;
what does this mean?

ranks[rank] = i
ranks -> array
rank -> a int showing the preference by voter -> go to line 81 which is substitute as j in there
i -> a int referring to the index of the candidate

it basically mean updating the ranks array from the for loop. In that array candidate index will be matched with the voter's preference.
Hopefully that does make sense

What is the point of doing ranks[rank] = i ? Isn't the function only returning true or false, so isn't assigning ranks[rank] = i going to change nothing?

ranks[rank] = i;
what does this mean?

ranks[rank] = i
ranks -> array
rank -> a int showing the preference by voter -> go to line 81 which is substitute as j in there
i -> a int referring to the index of the candidate
it basically mean updating the ranks array from the for loop. In that array candidate index will be matched with the voter's preference.
Hopefully that does make sense

What is the point of doing ranks[rank] = i ? Isn't the function only returning true or false, so isn't assigning ranks[rank] = i going to change nothing?

Check This!
Values of global variables can be changed from functions.

يبن الستين شرموطة الحل مش شغال يلعن كسمك خلتني الف حوالين نفسي