1

I worked with pset3 and I think there are nothing wrong with my code, but check 50 says it has 2 problems on my code.

1.:( lock_pairs skips final pair if it creates cycle
2.:( lock_pairs skips middle pair if it creates a cycle

All examples which I can imagine could pass the test with this code... This is my sorting part:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    
    for(int i =0;i<pair_count;i++)
    {
     locked[pairs[i].winner][pairs[i].loser]=true;
     int cycle=0;
     for(int w=0;w<candidate_count;w++)
     {
        int false_count=0;
        for(int l=0;l<candidate_count;l++)
        {
         if(locked[l][w]==false)
         {
          false_count++;
         }
        }
        if(false_count==candidate_count)
        {
            cycle ++;
            printf("cycle %i\n",cycle);
        }
     }
     if(cycle==0)
     {
      locked[pairs[i].winner][pairs[i].loser]=false; 
     }
    }
    
    return;
}

and here is my code. Can you explain why my code is not correct?

#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(candidates[i],name)==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-1;i++)
    {
     for(int j=1;i+j<candidate_count;j++)
     {
     preferences[ranks[i]][ranks[i+j]]++;
     }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // TODO
    for(int i=0;i<candidate_count-1;i++)
    {
     for(int j=1;i+j<candidate_count;j++)
     {
       if(preferences[i][i+j]>preferences[i+j][i])
       {
           pairs[pair_count].winner=i;
           pairs[pair_count].loser=i+j;
           pair_count++;
       }
       else if(preferences[i][i+j]<preferences[i+j][i])
       {
           pairs[pair_count].winner=i+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 r=0;r<pair_count;r++)
    {
    int i=0;
    int z=0;
    for(int j=0;j<pair_count;j++)
    {
     if(preferences[pairs[j+r].winner][pairs[j+r].loser]>i)
     {
      i=preferences[pairs[j+r].winner][pairs[j+r].loser];
     }
    }
    for(int y=0;y<pair_count;y++)
    {
     if(preferences[pairs[y+r].winner][pairs[y+r].loser]==i)
     {
      z =y+r;
     }
    }
    int w=pairs[r].winner;
    int l=pairs[r].loser;
    pairs[r].winner=pairs[z].winner;
    pairs[r].loser=pairs[z].loser;
    pairs[z].winner=w;
    pairs[z].loser=l;
    }

}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    
    for(int i =0;i<pair_count;i++)
    {
     locked[pairs[i].winner][pairs[i].loser]=true;
     int cycle=0;
     for(int w=0;w<candidate_count;w++)
     {
        int false_count=0;
        for(int l=0;l<candidate_count;l++)
        {
         if(locked[l][w]==false)
         {
          false_count++;
         }
        }
        if(false_count==candidate_count)
        {
            cycle ++;
            printf("cycle %i\n",cycle);
        }
     }
     if(cycle==0)
     {
      locked[pairs[i].winner][pairs[i].loser]=false; 
     }
    }
    
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // TODO
    int l=0;
     int w=0;
    while(w!=candidate_count&&l!=candidate_count)
    {
     if(locked[w][l]==true)
     {
       w=0;
       l++;
     }
     else//if(locked[w][l]=false)
     {
       if(w==candidate_count-1)
       {
        printf("%s\n",candidates[l]);
       }
       w++;
     }
    }
    
    
    return;
}

Thank you!!

1
  • *This is my lock_pairs part: – Keiyeung Law Feb 18 at 12:01
0

I think I have found your issue. false_count can never equal candidate_count, so cycle will always equal 0. Your middle loop is for(int w = 0; w < candidate_count; w++) which means the loop will stop as soon as w == candidate_count evaluates to true. I think you want your loop to include this last iteration, so you need to change it to w <= candidate_count. This will allow your line if(false_count==candidate_count) to have the opportunity to be true and increase the value of cycle.

Hope that helps. If it does, feel free to accept the answer by clicking the check mark next to it, but if not let me know and I'll try to help some more.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .