fbpx

cs50 Pset3: Runoff step-by-step walkthrough explained

So, 10-20 hours per week they say. LIES! I spent almost 4 days stuck on Pset3 to the point I was about to give up. After trolling the internet, stack exchange, joining the slack channel, the Reddit threads and ALSO the Facebook group. It felt SO good to see this after check50. So… do you want to learn how I did it?

Unlike Plurality, when I opened this Pset and realised you had to write not one but SIX functions I freaked out! Mainly because I only know how to write basic loops and functions not put them together to make a whole program work – in unison. Luckily the cs50 guides you through each one without you having to piece together the code. You just learn how to solve each individual function separately. So here we go…


Vote

For the vote function, they want us to check if the voted candidate exists and then store this candidate into the correct location in a 2D array.


Here was my pseudocode:

- iterate through each candidate
- check if given name is existing candidate
- if name matches - add vote choice to correct location in 2-dimentional array preferences[voter][rank]
- when preference array is updated you must return true
- else return false (i.e name not a candidate)

Iterate through candidate

This will count through the total number of candidates 1 by 1. SO if there are 4 then we go from 0 to 1 to 2 to 3 and can use this to count through the name array to check.

 for (int i = 0; i < candidate_count; i++)
 

Then we needed to check if the given name is an existing candidate

If you remember in plurality we used the strcmp function from the <string.h> library. This compared two strings and if they are the same it returns 0 meaning true.

if (!strcmp(name, candidates[i].name))

Add to 2D Array

If they are the same then we should add the name in terms of [i]th of the array to the correct location in a 2-dimensional array. Which they gave to us: preferences[voter][rank]. I’ve added [i] to this 2D array as it represents the [i]th voted candidate in the array.

        preferences[voter][rank] = i;

Then you return true in the loop and then return false outside of the loop.


Tabulate

Okay, so tabulate actually F’d me up for days. For tabulate they want you to update voters’ top candidate votes count. I managed to complete the other functions before I completed tabulate. It just wouldn’t return false when “multiple candidates are eliminated”. Here is my latest pseudocode

// iterate through voter count (i.e 4 voters)
// determine whether in rank 1 or 2 
// check through each vote in rank 1 if eliminated
// if eliminated
// access rank 2
// then check the candidate 
// add vote +1
// if not eliminated add +1 vote for rank1 voted candidate
// end

Iterate through voter count

for (int i = 0; i < voter_count; i++)

Determine whether in rank 1 or 2

    int j = 0;

Remember they gave us preference[voter][rank] previously?
This means voter = i and rank = j. So int J = 0 means rank 1.

    int j = 0;

Then I decided to do a while loop to show that for EACH vote we check whether if eliminated. If they are we check rank 2 by changing the position in the array meaning we +1 to j position.

while (candidates[preferences[i][j]].eliminated == true)
    {
        j++;
    }

If the candidate is NOT eliminated and still in the game, we skip the while loop and go straight to updating the vote count for the specific candidate in rank1. The preference[i][j] is basically the voted candidate stored in a specific voter and rank position which we inputted in the earlier Vote Function.

candidates[preferences[i][j]].votes++;

Print Winner

For print_winner we want to check if a candidate has more than half the vote and if they do then print them as the winner. If they do not then we want to return false.

// half the total vote count and create a new variable 
// iterate through the candidates to check each one
// check if the candidate's total votes is more than half of the vote count
// if it is then they are the winner
// print candidate name 
// return true 
// if none of the candidates total votes is more than half the total vote count
// return false

Find out the majority

To check the number of the majority. It would need to be MORE than half. The issue with int is that it only allows whole numbers as it stands for ‘integer’ so if they became decimals then the variable rounds EVERYTHING down. What I found is that if you have odd numbers and you add 0.5 it would round any of those up. If it is an even number and you add 0.5 to the half it would still round the decimal down! I hope this makes sense? So I created a new int variable for the new sum to use.

 int majority = voter_count / 2 + 0.5;

Iterate through candidates

    for (int i = 0; i < candidate_count; i++)

Check if the candidate has more than the majority

if (candidates[i].votes > majority)

Then I realised I had to add a boolean variable to change from false to true IF there is a winning candidate already. I also had to print both the winner’s name and true to end the program. Else return false

            winner = true;
            printf("%s\n", candidates[i].name);
            return winner;

FIND_MIN

For FIND_MIN, you want to check through each candidate and find the one who is still in the election and has the lowest number of votes and return the minimum vote total of that candidate.

- Make a lowestVote variable and equal it to the first candidate vote total 
- check through each candidate
- check whether candidate is still in the game 
- if candidate is still in game
- check whether current candidate total vote is more than the next candidate total vote
- if first candidate total vote is bigger than next candidate update lowestVote variable equal to next candidate total vote 
- the loop will keep iterating through candidates
- return lowestVote total

Make a lowestVote variable and equal it to the first candidate vote total

 int lowestVoteNum = candidates[0].votes;

Then check through each candidate

    for (int m = 1; m < candidate_count; m++)

Check if the candidate is still in-game also check whether current candidate total vote is more than the next candidate total vote

if (candidates[m].eliminated == false && lowestVoteNum > candidates[m].votes)

If the first candidate total vote is bigger than the next candidate update lowestVote variable equal to next candidate total vote

            lowestVoteNum = candidates[m].votes;

Here the loop will keep iterating over each candidate to check and then eventually the lowestVote variable will contain the total number of votes that is the lowest out of all the candidates.

return lowestVoteNum;

IS_TIE

Not gonna lie this one also F’d me up. Basically ALL of these F’d me up…lol. For IS_TIE it takes the minimum vote value (which we calculated just earlier) and check if all the candidates that are not eliminated has the same number of total votes. If they do then there is a tie but if they do not then the program should return false.

- first iterate through each candidate
- check if candidate is eliminated
- if they are still in the game then add to not eliminated counter
- check if candidate total vote is the same as the smallest vote total
- if so, add to counter
- check if total still in the game is the same as candidats with same total vote as smallest vote
- if true then there is a tie for ALL remaining candidates
- if not true then return false

First iterate through each candidate

    for (i = 0; i < candidate_count; i++)

Then check if the candidate is eliminated

if (!candidates[i].eliminated)

If they are still in the game then add+1 counter of candidates not eliminated

            eliminated++;

Check if the candidate total vote is the same as the smallest vote total. If each candidate is the same as the minimum vote it means that is the ONLY vote total there is and they have no other vote total.

        if (candidates[i].votes == min)

If so, add to counter

            counter++;

Then check if the total number of candidates still in the game is the same as candidates with the same total vote as the smallest vote.

        if (eliminated == counter)

If this is true then there is a tie for ALL remaining candidates

            isTie = true;

Then return false if it is not true!

Wow, we’re getting there, right? Writing it out in one go makes it sound so easy but for me it definitely made me want to rip my eyes, hair and guts out. Now let’s get to the final one!


Eliminate

For the eliminate function you take the argument min, which is the smallest number of votes that anyone in the election currently has. The function should eliminate the candidate (or candidates) who have the smallest number of votes.

- iterate through the candidates
- if the candidate vote equals the 'min' (smallest number of votes) and are also still in the game (not eliminated)
- then eliminate them 

Iterate through the candidates

 for (int i = 0; i < candidate_count; i++)

If the candidate vote equals the ‘min’ (smallest number of votes) and are also still in the game (not eliminated)

if (!candidates[i].eliminated && candidates[i].votes == lowestNum)

Then eliminate them!

candidates[i].eliminated = true;

Completed!

There you have it! Remember to style50, check50 and debug50 your way to the end. Debug50 really helped with pinpointing and checking what EACH line did. I also used a lot of printf function to print out the current counter amounts to see if the code was working.

Thank goodness. Now onto Pset4!

Please do leave a comment down below 👇stating how long it took you to do this task as I spent almost 4 days!

close
💌 Subscribe to our newsletter and join 12 other housemates.
☕️ ️ Did you found this article helpful? If so, please feel free to buy me a coffee :)

Buy Me a Coffee at ko-fi.com
Bexa

Bexa

A forever-learner and explorer. My favourite thing in life is helping people using the skills that I have. I love blogging as it gives me a safe place to document and explore my thoughts, dreams and ideas that I am too scared to speak about IRL. I love having deep chats, internetting, art and design thingies, handcrafting, experiencing new things and learning more about people and the world we live in.

15 comments

  1. I was completely stuck at the beginning, until I saw your solution for the tabulate function. After that, it was easier I think. Going to try tideman now but I don’t think I’m going to make it haha.

  2. Oh my gosh, thank you! I completely was thinking the same thing as you… your first sentence “So, 10-20 hours per week they say. LIES! I spent almost 4 days stuck on Pset3 to the point I was about to give up.” completely resonated within my soul! LOL. Anyhow, all that to say thank you, you walked through the spots I was confused with in great clarity. Great work.

  3. I’m slightly confused with the first part of your code when checking the names.

    Is this:

    >> if (!strcmp(name, candidates[i].name))

    the same as this:

    >> if (strcmp(name, candidates[i].name) == 0)

    ?

    I’m looking at it and can’t understand why you’d check if they don’t match rather than if they do.

    1. they return 0 i.e true

    2. Same, i still don’t get it

    3. ‘if (!strcmp(name, candidates[i].name))’ means “if the function returns FALSE (i.e. is not the same)”
      whereas
      ‘if (strcmp(name, candidates[i].name) == 0) means’ “if the function returns TRUE (i.e. is the same)”

      The ‘!’ means FALSE in the first example, and ‘==0’ means true (==1 would be FALSE).
      Hope that helps!

  4. Hi thanks for your explanation. I’ve spent 3 hours just on the vote function, this does not bode well so far, yikes! In your work through, you put the return false outside of the for loop. Do you know why it does not work when when you include the return false as an else statement inside the for loop?

  5. Hey quick question for the tabulate function. is assigning int j = 0 at the beginning of the function the same as creating a nested for loop for the second for loop that loop’s over the candidate_count?
    for(int j = 0; j < candidate_count; j++)

  6. thanks, the 0.5 trick was magic.in fact you are my great CS50 tutor.

    1. A neater way is to include math.h and use round(voter_count / 2).

  7. I had given up on runoff already until i came across your article. Seeing and using your detailed pseudocode explanation got me through. THANKS! you’re a life saver

    I also realized the hardest part of coding isn’t writing the syntax. It’s thinking of the syntax.

  8. I don’t know how to thank you. This helped me so much. I was about to quit and I saw this. You saved my life. Keep up the great work!!

    //I have to be anonymous because of personal reasons

  9. Stuck on this one for 1 week. I put this on hold and try to understand C better from youtube lessons(thenewboston channel helped a lot). But I still couldn’t make this pset runoff…
    What people are thinking, they claim as “CS50 for the people who doesn’t have any coding experience” But isn’t that too much for this level? How everyone cope with this. Or am I the only dumb here

    1. Honestly, I’ve been doing cs50 for 2 years. It’s to do with training yourself to think in a way to break down problems, then solve those problems and also debugging. I’m with you girl seriously you are not alone. I pick it up and put it down as and when I got time – forget about other people and focus on what feels right for you. Take it slow if you need, take a break. You will get through it in your own pace! x

  10. I think I spent a 1-3 hrs a day for at least 6 days. Thanks for this article; you helped me get my head around what I needed to accomplish.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.