ccs50
CS50 Pset 3 Tideman - lock function. Check50 says my lock function doesn't work, but it does?
Here is my answer for the CS50 tideman problem. For complete problem statement please visit the CS50 link at https://cs50.harvard.edu/x/2023/psets/3/tideman/
#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
int j = 0;
int a = 0;
int c = 0;
for (int i = 0; i < candidate_count; i++)
{
while (j < candidate_count)
{
if (j == candidate_count || i == candidate_count - 1)
{
break;
}
while (a < candidate_count)
{
if (j == ranks[a+1])
{
c++;
break;
}
a++;
}
if (c > 0)
{
preferences[ranks[i]][j]++;
}
while (c > 0)
{
c--;
}
while (a > i)
{
a--;
}
j++;
}
while (j > 0)
{
j--;
}
a++;
a += i;
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
int a = 0;
int j = 0;
for (int i = 0; i < candidate_count; i++)
{
while (j < candidate_count)
{
if (preferences[i][j] > preferences[j][i])
{
pairs[a].winner = i;
pairs[a].loser = j;
a++;
pair_count++;
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[a].winner = j;
pairs[a].loser = i;
a++;
pair_count++;
}
j++;
}
while (j > 0)
{
j--;
}
j++;
j += i;
}
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
for (int j = 0; j < pair_count - i; j++)
{
if (preferences[pairs[j].winner][pairs[j].loser] < preferences[pairs[j+1].winner][pairs[j+1].loser])
{
pair winner = pairs[j];
pairs[j] = pairs[j+1];
pairs[j+1] = winner;
}
}
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
int c = 0;
for (int i = 0; i < pair_count; i++)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
for (int j = 0; j < candidate_count; j++)
{
for (int a = 0; a < pair_count; a++)
{
if (j == pairs[a].loser)
{
c++;
break;
}
}
}
if (c == pair_count)
{
locked[pairs[pair_count - 1].winner][pairs[pair_count - 1].loser] = false;
}
return;
}
// Print the winner of the election
void print_winner(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
int c = 0;
for (int j = 0; j < pair_count; j++)
{
if (i == pairs[j].loser && locked[pairs[j].winner][pairs[j].loser] == true)
{
break;
}
else
{
c++;
}
if (c == pair_count)
{
printf("%s\n", candidates[i]);
}
}
}
return;
}
Check50 says my lock function doesn't prevent cycles. The problem is, it works when I test it. And I'm not testing with random inputs, but with the usage CS50 gives you. In Tideman, it's a voting system that works based on the preferences of every voter. An example is what if Alice beats Bob 7-2, Bob beats Charlie 5-4, and Charlie beats Alice 6-3. The one with the biggest victory is considered first (alice to bob), so we can image an arrow pointing from alice to bob.
Then the next biggest victory is considered, (charlie to alice) so we can add an arrow from charlie to alice.
Finally, we add an arrow from Bob to Charlie.
Since it's a loop, we don't know who the winner is. So we erase the arrow that won with the smallest victory, (bob to charlie with a 5-4 victory).
Since there are no arrows pointing to Charlie, he's the winner. To replicate this scenario, CS50 tells you to put in these inputs.
I put in these inputs, And this is what I got.
The exact same result. Charlie wins. CS50 also says that to check your work, you should also test with this input.
Heres what happens when I test it.
It's correct. So I think my codes's all good, right? But look at what check50 says.
It says that my code fails to end the cycle. But it works with their own examples. This is why I have no idea what's even wrong with it.
Solution
To directly address your questions first, as one of the error messages says, lock_pairs should skip middle pair if it creates a cycle. But in your implementation, you just lock all of them to start with. Then at the end, you check if the last pair needs to be unlocked. This may be why it's failing you. Another minor thing, the sort_pairs() may potentially cause array index out of bound because you allow j to be pair_count-1. but you are referencing j+1 which will be pair_count.
The following is a complete program to show a different algorithm for the lock_pairs() function as well as how the record_preferences() and add_pairs() can be simplified. I added plenty of inline comments to help explain the algorithms. Hope this helps.
#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[])
{
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[])
{
//assume rank[1] and rank[2] are ith and jth candidate
//it means this voter prefers ith candidate over jth candidate
//hence we have preferences[i][j]++
//so, we just need to loop through all the pairs once
for(int i=0; i < candidate_count-1; i++)
{
for(int j=i+1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
for(int i=0; i < candidate_count-1; i++)
{
for(int j=i+1; j < candidate_count; j++)
{
// just loop through all pairs and see which candidate
// is the winner and loser
if(preferences[i][j] == preferences[j][i])
{
continue;
} else if(preferences[i][j] > preferences[j][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = j;
pair_count++;
}
else
{
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)
{
for (int i = 0; i < pair_count; i++)
{
for (int j = 0; j < pair_count - i - 1; j++)
{
if (preferences[pairs[j].winner][pairs[j].loser] < preferences[pairs[j+1].winner][pairs[j+1].loser])
{
pair winner = pairs[j];
pairs[j] = pairs[j+1];
pairs[j+1] = winner;
}
}
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// remember the losers found while locking in the pairs
bool losers[MAX];
// we need to make sure loser_count is less that candidate_count
// if locking in a pair causes loser_count to be equal to
// candidate_count we should skip that pair.
int loser_count=0;
// no one is a loser before we start
for(int i=0; i < candidate_count; i++)
{
losers[i] = false;
}
for (int i = 0; i < pair_count; i++)
{
if(losers[pairs[i].loser] == true)
{
// ith pair's loser is already a loser before
// we are not adding more losers, safe to lock the pair
locked[pairs[i].winner][pairs[i].loser] = true;
}
else if(loser_count < candidate_count-1)
{
// still has room for one more loser, lock in the pair
locked[pairs[i].winner][pairs[i].loser] = true;
losers[pairs[i].loser] = true;
loser_count++;
}
// else locking this pair would form a loop
}
return;
}
// Print the winner of the election
void print_winner(void)
{
bool winners[MAX];
// no one is a loser before we start
for(int i=0; i < candidate_count; i++)
{
winners[i] = true;
}
// loop through all locked pairs to find all the losers
// record what we find in the winners array
for (int i = 0; i < candidate_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
if(locked[i][j] == true)
{
winners[j] = false;
}
}
}
// print the winner
for(int i=0; i < candidate_count; i++)
{
if(winners[i] == true)
{
printf("%s\n", candidates[i]);
break;
}
}
return;
}
- Understanding the difference in timing of two functions that increment each element of an integer array
- Why MSVC generates warning C4127 when constant is used in "while" - C
- Executing a user-space function from the kernel space
- Why must the variable used to hold getchar's return value be declared as int?
- mpirun -np 4 ./a.out doesn't use all my cores (ubuntu 24.04LTS)
- Shadowing an iterator inside a for loop has undefined (?) behaviour in C
- Sleep for N seconds and wait for keypress
- Dereference twice in gdb
- Is this declaration UB?
- return type defaults to 'int' [-Wimplicit-int]
- What is the scope of `fesetround()`?
- Which specific optimization flag causes libm functions to be treated as pure?
- How to render text in SDL2?
- Why would you use 'extern "C++"'?
- Strange Behavior Compiler Ignoring NULL Check Unless I Print Something in the if Statement
- Fast inverse square root using fixed point instead of floating point
- What is the const qualifier attached to in C: the memory area or the pointer?
- GCC options for strictest C code?
- How to do an explicit fall-through in C
- How do compilers treat CONST qualifier when the pointer points to a memory location obtained with malloc()?
- C: cmocka headers - how to unittest?
- Why in C when I print a double with a one decimal it round it to the next number
- Android C to Java SWIG unable to compile: incompatible types: byte cannot be converted to SWIGTYPE_p_uint8_t
- GNU Make in Ubuntu giving fatal error: rpc/types.h: No such file or directory
- How can I exclude non-numeric keys? CS50 Caesar Pset2
- How change every struct in an array of pointers?
- Optimized 2x2 matrix multiplication: Slow assembly versus fast SIMD
- Simple frame by frame video decoder library
- GCC no longer implements <varargs.h>
- Contents of IO buffer unknown == unsafe?