Step back, because this is the WORST week in CS50! It relies heavily on recursion (something I am VERY BAD with), so we work out other hefty and lengthy ways to work out what should be basic problems. Prepare for headaches!
Yes, I'm looking at you, Tideman. Plurality
N A V I G A T I O N
This was to represent a basic voting system.
User adds arguments to the command that generate a list of candidates for the election. You then supply the number of voters at the first prompt. After this, the user enters their vote by the candidate's name. Our job was to locate and increment the vote for these candidates then analyze and print the winner(s). Here is the code:
#include <cs50.h>
#include <stdio.h> #include <string.h> // Max number of candidates #define MAX 9 // Candidates have name and vote count typedef struct { string name; int votes; } candidate; // Array of candidates candidate candidates[MAX]; // Number of candidates int candidate_count; // Function prototypes bool vote(string name); void print_winner(void); int main(int argc, string argv[]) { // Check for invalid usage if (argc < 2) { printf("Usage: plurality [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].name = argv[i + 1]; candidates[i].votes = 0; } int voter_count = get_int("Number of voters: "); // Loop over all voters for (int i = 0; i < voter_count; i++) { string name = get_string("Vote: "); // Check for invalid vote if (!vote(name)) { printf("Invalid vote.\n"); } } // Display winner of election print_winner(); } // Update vote totals given a new vote bool vote(string name) { // TODO for (int i = 0; i < candidate_count; i++) { if (strcmp(candidates[i].name, name) == 0) { ++candidates[i].votes; return true; } } return false; } // Print the winner (or winners) of the election void print_winner(void) { // TODO // Get highest vote count int win = -1; for (int i = 0; i < candidate_count; i++) { if (candidates[i].votes > win) { win = candidates[i].votes; } } // Print any candidates with this win count. for (int i = 0; i < candidate_count; i++) { if (candidates[i].votes == win) { printf("%s\n", candidates[i].name); } } return; } This went pretty straight forward with a couple of quick for loops to scan the structs. Here is what the execution and output of the program looks like: plurality/ $ ./plurality Alice Bob Number of voters: 1 Vote: Me Invalid vote. Alice Bob plurality/ $ ./plurality Alice Bob Charlie Number of voters: 5 Vote: Alice Vote: Charlie Vote: Bob Vote: Bob Vote: Alice Alice Bob
|
|
This was one of the most gut-wrenching assignments for me. I spent almost two days concocting one of the functions in this. Surely simply because I do NOT understand recursion and because I refused to create axillary helper functions to solve this.
This assignment was to implement a 'Tideman' voting structure. The user enters candidates that will be voted for. Then the user inputs a number of voters. You then enter each candidate for each voter in the order in which they favor said candidates. It then calculates the favoritism in order by rank and then slowly rids candidates for calculation based on 50% of the vote.
The hardest part in implementing this was the lock_pairs() function. You need to analyze all of the votes to assess for any possible looped candidate votes not to create any logic problems when determining a winner. This chain can become intricate since you can have up to 9 candidates. I am sure recursion would have helped greatly when tracing down the chain, but I knew I would just fail at that.
So, after a few failed attempts I generated this visual aide to assist me with creating my function (Visio):
This assignment was to implement a 'Tideman' voting structure. The user enters candidates that will be voted for. Then the user inputs a number of voters. You then enter each candidate for each voter in the order in which they favor said candidates. It then calculates the favoritism in order by rank and then slowly rids candidates for calculation based on 50% of the vote.
The hardest part in implementing this was the lock_pairs() function. You need to analyze all of the votes to assess for any possible looped candidate votes not to create any logic problems when determining a winner. This chain can become intricate since you can have up to 9 candidates. I am sure recursion would have helped greatly when tracing down the chain, but I knew I would just fail at that.
So, after a few failed attempts I generated this visual aide to assist me with creating my function (Visio):
... all that was left was to devise a way to generate linear code that would actually make this plan work! After a few more failed attempts, this is what I created. (Baseline code generated by CS50 staff. I was responsible for functions marked with "// TODO" comments.):
#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 - DONE
// Write single vote into ascending ranks by candidate index.
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 - DONE
// Iterate through each candidate.
// They are voted above anyone below them.
// Do not need to analyze after last to end (-1)
for (int i = 0; i < candidate_count - 1; i++)
{
// Only need to assess ranks after (+1)
for (int c = i + 1; c < candidate_count; c++)
{
++preferences[ranks[i]][ranks[c]];
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
// Evaluate weight of votes, determine winners.
for (int i = 0; i < candidate_count; i++)
{
for (int c = 0; c < candidate_count; c++)
{
// Do not evaluate against one's self.
if (!(i == c))
{
// Do not evaluate if competitors are equal.
if (!(preferences[i][c] == preferences[c][i]))
{
// Write new pairs depending victors.
if (preferences[i][c] > preferences[c][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = c;
++pair_count;
}
}
}
}
}
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
// Placeholder
pair holder;
int key;
// Analyze pairs.
for (int i = 0; i < pair_count; i++)
{
// Start at second for testing.
for (int c = i + 1; c < pair_count; c++)
{
int leftItem = preferences[pairs[i].winner][pairs[i].loser];
int rightItem = preferences[pairs[c].winner][pairs[c].loser];
if (rightItem > leftItem)
{
holder.winner = pairs[c].winner;
holder.loser = pairs[c].loser;
pairs[c].winner = pairs[i].winner;
pairs[c].loser = pairs[i].loser;
pairs[i].winner = holder.winner;
pairs[i].loser = holder.loser;
}
}
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
bool loop = false;
// Set leading pair as a lock.
if (i == 0)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
else
{
// Scan proposed lock to make sure it doesn't cylically create a link.
int w = pairs[i].winner;
int l = pairs[i].loser;
int trail[MAX];
int val = 0;
bool trace = true;
for (int c = 0; c < candidate_count; c++)
{
if (locked[c][w])
{
trail[val] = c;
++val;
// Start a trace.
int t = c;
while (trace)
{
trace = false;
for (int s = 0; s < candidate_count; s++)
{
if (locked[s][t])
{
trail[val] = s;
++val;
t = s;
trace = true;
break;
}
}
}
// Check current trail for matches.
for (int v = 0; v < val; v++)
{
if (trail[v] == l)
{
loop = true;
}
}
}
}
if (!loop)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
}
return;
}
// Print the winner of the election
void print_winner(void)
{
// TODO
// Scan locked for value with no pointers pointing back.
for (int i = 0; i < candidate_count; i++)
{
for (int ii = 0; ii < candidate_count; ii++)
{
if (locked[i][ii])
{
bool trigger = false;
// Scan for any locks that point to this winner.
for (int s = 0; s < candidate_count; s++)
{
for (int ss = 0; ss < candidate_count; ss++)
{
if ((locked[s][ss]) && (ss == i))
{
trigger = true;
break;
}
}
if (trigger)
{
break;
}
}
// If no cyclic pointbacks, winner.
if (!trigger)
{
printf("%s\n", candidates[i]);
return;
}
}
}
}
return;
}
#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 - DONE
// Write single vote into ascending ranks by candidate index.
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 - DONE
// Iterate through each candidate.
// They are voted above anyone below them.
// Do not need to analyze after last to end (-1)
for (int i = 0; i < candidate_count - 1; i++)
{
// Only need to assess ranks after (+1)
for (int c = i + 1; c < candidate_count; c++)
{
++preferences[ranks[i]][ranks[c]];
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
// TODO
// Evaluate weight of votes, determine winners.
for (int i = 0; i < candidate_count; i++)
{
for (int c = 0; c < candidate_count; c++)
{
// Do not evaluate against one's self.
if (!(i == c))
{
// Do not evaluate if competitors are equal.
if (!(preferences[i][c] == preferences[c][i]))
{
// Write new pairs depending victors.
if (preferences[i][c] > preferences[c][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = c;
++pair_count;
}
}
}
}
}
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
// TODO
// Placeholder
pair holder;
int key;
// Analyze pairs.
for (int i = 0; i < pair_count; i++)
{
// Start at second for testing.
for (int c = i + 1; c < pair_count; c++)
{
int leftItem = preferences[pairs[i].winner][pairs[i].loser];
int rightItem = preferences[pairs[c].winner][pairs[c].loser];
if (rightItem > leftItem)
{
holder.winner = pairs[c].winner;
holder.loser = pairs[c].loser;
pairs[c].winner = pairs[i].winner;
pairs[c].loser = pairs[i].loser;
pairs[i].winner = holder.winner;
pairs[i].loser = holder.loser;
}
}
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
// TODO
for (int i = 0; i < pair_count; i++)
{
bool loop = false;
// Set leading pair as a lock.
if (i == 0)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
else
{
// Scan proposed lock to make sure it doesn't cylically create a link.
int w = pairs[i].winner;
int l = pairs[i].loser;
int trail[MAX];
int val = 0;
bool trace = true;
for (int c = 0; c < candidate_count; c++)
{
if (locked[c][w])
{
trail[val] = c;
++val;
// Start a trace.
int t = c;
while (trace)
{
trace = false;
for (int s = 0; s < candidate_count; s++)
{
if (locked[s][t])
{
trail[val] = s;
++val;
t = s;
trace = true;
break;
}
}
}
// Check current trail for matches.
for (int v = 0; v < val; v++)
{
if (trail[v] == l)
{
loop = true;
}
}
}
}
if (!loop)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
}
return;
}
// Print the winner of the election
void print_winner(void)
{
// TODO
// Scan locked for value with no pointers pointing back.
for (int i = 0; i < candidate_count; i++)
{
for (int ii = 0; ii < candidate_count; ii++)
{
if (locked[i][ii])
{
bool trigger = false;
// Scan for any locks that point to this winner.
for (int s = 0; s < candidate_count; s++)
{
for (int ss = 0; ss < candidate_count; ss++)
{
if ((locked[s][ss]) && (ss == i))
{
trigger = true;
break;
}
}
if (trigger)
{
break;
}
}
// If no cyclic pointbacks, winner.
if (!trigger)
{
printf("%s\n", candidates[i]);
return;
}
}
}
}
return;
}
Drumroll, please...
Here is the outcome:
tideman/ $ ./tideman Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob
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
Charlie
That's the end of Week 3! Cannot wait to see how much more difficult this gets! Love every second of learning. I hope if you're reading along that you are enjoying it just as much and that this information as helping you achieve your academic goals in this classroom.
Special thanks to Ed-x for existing and offering such amazing courses at incredible prices. Thanks to Harvard for providing such top-of-the-line courses.
All of my love to Mr. David Malan and all of his incredible staff for creating and generating such excellent course material. You can tell the love and work that was put into all of the course content to be able to present it in such a professional and understandable manner. You guys are the foundation that inspires.
Extra special shout-out to curiouskiwi on the CS50 Discord! You do not know how many times you have helped me throughout the years. I have taken and re-taken this course. A few times as an audit, and then when I stopped for over a year because I could not figure out what to do as my Final for my certification. You may not remember me, but I will always remember you!
0 Comments
Leave a Reply.
- Scratch
Weeks nav
Week 0
Author
Jonathan Styles (4verageGamer) is just a simple student of all things IT-related during this pursuit of completing the CS50 class from Harvard.