---
tags: CS50
---

# (2022年) CS50 week3

其實之前就已經修完 CS50 了，不過因應 2022 年將課堂作業的系統
從 c9.io 換到 github codespace + vscode 整合
打算來重溫一下裡面的作業，並暖身一下 C 語言的手感

由於已經有許多前輩分享課程與作業的心得
加上官網教材的投影片、重點筆記、教學影片都非常完整
故不再做詳細的紀錄，專注在作業 (Lab, Problem sets) 上面

https://cs50.harvard.edu/x/2022/weeks/3/

---

### Lab3： [Sort](https://cs50.harvard.edu/x/2022/labs/3)

解答：

sort1 uses: bubble sort
How do you know? : used least times is best case, but other case is long time

sort2 uses: merge sort
How do you know? : in any case, used least times

sort3 uses: selection sort
How do you know? : in any case, used largest times

:::spoiler (點擊展開) 操作記錄
-- Time Complexity Table --

| type | Best | Worst. | Average |
| --------------:|:-------- |:-------- |:-------- |
| selection sort | Ω(N²) | θ(N²) | O(N²) |
| bubble sort | Ω(N) | θ(N²) | O(N²) |
| merge sort | Ω(N ㏒ᴺ) | θ(N ㏒ᴺ) | O(N ㏒ᴺ) |

-- Compares ---

**random (avg case)**

| type | 5000 | 10000 | 50000 |
| -----:| ------:| ------:| ------:|
| sort1 | 0.064s | 0.259s | 7.227s |
| sort2 | 0.005s | 0.007s | 0.020s |
| sort3 | 0.031s | 0.192s | 2.881s |

**reversed (worst case)**

| type | 5000 | 10000 | 50000 |
| -----:| ------:| ------:| ------:|
| sort1 | 0.068s | 0.211s | 5.503s |
| sort2 | 0.005s | 0.007s | 0.021s |
| sort3 | 0.030s | 0.114s | 2.847s |

**sorted (best case)**

| type | 5000 | 10000 | 50000 |
| -----:| ------:| ------:| -------:|
| sort1 | 0.009s | 0.013s | 0.013s |
| sort2 | 0.006s | 0.006s | 0.006s |
| sort3 | 0.031s | 0.114s | 2.898s |

-- Records ---

**random5000**
time ./sort1 random5000.txt => 0m0.064s
time ./sort2 random5000.txt => 0m0.005s
time ./sort3 random5000.txt => 0m0.031s

**random10000**
time ./sort1 random10000.txt => 0m0.259s
time ./sort2 random10000.txt => 0m0.007s
time ./sort3 random10000.txt => 0m0.192s

**random50000**
time ./sort1 random50000.txt => 0m7.227s
time ./sort2 random50000.txt => 0m0.020s
time ./sort3 random50000.txt => 0m2.881s

---

**reversed5000**
time ./sort1 reversed5000.txt => 0m0.068s
time ./sort2 reversed5000.txt => 0m0.005s
time ./sort3 reversed5000.txt => 0m0.030s

**reversed10000**
time ./sort1 reversed10000.txt => 0m0.211s
time ./sort2 reversed10000.txt => 0m0.007s
time ./sort3 reversed10000.txt => 0m0.114s

**reversed50000**
time ./sort1 reversed50000.txt => 0m5.503s
time ./sort2 reversed50000.txt => 0m0.021s
time ./sort3 reversed50000.txt => 0m2.847s

---

**sorted5000**
time ./sort1 sorted5000.txt => 0m0.009s
time ./sort2 sorted5000.txt => 0m0.006s
time ./sort3 sorted5000.txt => 0m0.031s

**sorted10000**
time ./sort1 sorted10000.txt => 0m0.013s
time ./sort2 sorted10000.txt => 0m0.006s
time ./sort3 sorted10000.txt => 0m0.114s

**sorted50000**
time ./sort1 sorted50000.txt => 0m0.013s
time ./sort2 sorted50000.txt => 0m0.016s
time ./sort3 sorted50000.txt => 0m2.898s
:::

---

### 作業： [Plurality](https://cs50.harvard.edu/x/2022/psets/3/plurality/)

:::spoiler (點擊展開) 符合 `style50` 風格的程式碼

#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)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0)
        {
            valid_name = true;
            candidates[i].votes++;
        }
    }

    return valid_name;
}

// Print the winner (or winners) of the election
void print_winner(void)
{
    int max_votes = 0;

    // search max votes in all candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > max_votes)
        {
            max_votes = candidates[i].votes;
        }
    }

    // print candidates that have max_votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == max_votes)
        {
            printf("%s\n", candidates[i].name);
        }
    }

    return ;
}

:::

--

:::spoiler (點擊展開) 個人覺得比較好讀的程式碼風格

#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)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(candidates[i].name, name) == 0) {
            valid_name = true;
            candidates[i].votes++;
        }
    }

    return valid_name;
}

// Print the winner (or winners) of the election
void print_winner(void)
{
    int max_votes = 0;

    // search max votes in all candidates
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes > max_votes)
            max_votes = candidates[i].votes;
    }

    // print candidates that have max_votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == max_votes)
            printf("%s\n", candidates[i].name);
    }

    return ;
}

:::

--

執行

驗證

---

### 作業： [Runoff](https://cs50.harvard.edu/x/2022/psets/3/runoff/)

:::spoiler (點擊展開) 符合 `style50` 風格的程式碼

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES)
    {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS)
    {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++)
    {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            // Record vote, unless it's invalid
            if (!vote(i, j, name))
            {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
        {
            break;
        }

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie)
        {
            for (int i = 0; i < candidate_count; i++)
            {
                if (!candidates[i].eliminated)
                {
                    printf("%s\n", candidates[i].name);
                }
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
        {
            candidates[i].votes = 0;
        }
    }
    return 0;
}

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0)
        {
            valid_name = true;
            // Record the voter and rank with candidate_index
            preferences[voter][rank] = i;
        }
    }

    return valid_name;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // counting by each votes
    for (int i = 0; i < voter_count; i++)
    {
        // counting by each rank
        for (int j = 0; j < candidate_count; j++)
        {
            int candidate_index = preferences[i][j];
            // if candidate is not eliminated, counting votes
            if (candidates[candidate_index].eliminated == false)
            {
                candidates[candidate_index].votes++;
                break;
            }
        }
    }

    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // have to be majority (more than 50%)
    int majority = (voter_count / 2) + 1;
    bool has_winner = false;

    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes >= majority)
        {
            has_winner = true;
            printf("%s\n", candidates[i].name);
        }
    }

    return has_winner;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min_votes = voter_count;

    // find minimum votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes < min_votes && candidates[i].eliminated == false)
        {
            min_votes = candidates[i].votes;
        }
    }

    return min_votes;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int max_votes = 0;
    int max_votes_candidates_count = 0;
    int uneliminated_candidates_count = 0;
    string max_votes_candidates[candidate_count];

    bool have_tie = false;

    // find maximum votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > max_votes && candidates[i].eliminated == false)
        {
            max_votes = candidates[i].votes;
        }
    }

    // count have max_votes candidates name
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false)
        {
            uneliminated_candidates_count ++;

            if (candidates[i].votes == max_votes)
            {
                max_votes_candidates[i] = candidates[i].name;
                max_votes_candidates_count++;
            }
        }
    }

    // condition have_tie
    if (max_votes_candidates_count > 1 && max_votes_candidates_count == uneliminated_candidates_count)
    {
        have_tie = true;
    }

    return have_tie;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }
    return;
}

:::

--

:::spoiler (點擊展開) 個人覺得比較好讀的程式碼風格

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct {
    string name;
    int votes;
    bool eliminated;
} candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2) {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES) {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }

    for (int i = 0; i < candidate_count; i++) {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS) {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++) {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++) {
            string name = get_string("Rank %i: ", j + 1);
            // Record vote, unless it's invalid
            if (!vote(i, j, name)) {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
            break;

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie) {
            for (int i = 0; i < candidate_count; i++) {
                if (!candidates[i].eliminated)
                    printf("%s\n", candidates[i].name);
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
            candidates[i].votes = 0;
    }
    return 0;
}

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(candidates[i].name, name) == 0) {
            valid_name = true;
            // Record the voter and rank with candidate_index
            preferences[voter][rank] = i;
        }
    }

    return valid_name;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // counting by each votes
    for (int i = 0; i < voter_count; i++) {
        // counting by each rank
        for (int j = 0; j < candidate_count; j++) {
            int candidate_index = preferences[i][j];
            // if candidate is not eliminated, counting votes
            if (candidates[candidate_index].eliminated == false) {
                candidates[candidate_index].votes++;
                break;
            }
        }
    }

    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // have to be majority (more than 50%)
    int majority = (voter_count / 2) + 1;
    bool has_winner = false;

    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes >= majority) {
            has_winner = true;
            printf("%s\n", candidates[i].name);
        }
    }

    return has_winner;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min_votes = voter_count;

    // find minimum votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes < min_votes && candidates[i].eliminated == false)
            min_votes = candidates[i].votes;
    }

    return min_votes;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int max_votes = 0;
    int max_votes_candidates_count = 0;
    int uneliminated_candidates_count = 0;
    string max_votes_candidates[candidate_count];

    bool have_tie = false;

    // find maximum votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes > max_votes && candidates[i].eliminated == false)
            max_votes = candidates[i].votes;
    }

    // count have max_votes candidates name
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].eliminated == false) {
            uneliminated_candidates_count ++;

            if (candidates[i].votes == max_votes) {
                max_votes_candidates[i] = candidates[i].name;
                max_votes_candidates_count++;
            }
        }
    }

    // condition have_tie
    if (max_votes_candidates_count > 1 && max_votes_candidates_count == uneliminated_candidates_count)
        have_tie = true;

    return have_tie;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == min)
            candidates[i].eliminated = true;
    }
    return;
}

:::

--

執行

驗證

---

### 作業： [Tideman](https://cs50.harvard.edu/x/2022/psets/3/tideman/)

:::spoiler (點擊展開) 符合 `style50` 風格的程式碼

#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];
// e.g. if have 3 candidates, all pairs will be `3 * (3-1) / 2` = 3
// it will map on record_preferences() and add_pairs()

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

void sort(int array[], int start, int end);
void merge(int array[], int start, int middle, int end);
bool has_cycle(int winner, int loser);

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++)
    {
        // candiates = [1: Alice, 2: Bob, 3: Charlie]

        // ranks[i] is voter's ith preference
        int ranks[candidate_count];
        // e.g. ranks[3]

        // 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;
            }
        }
        // e.g. a ballot content is 1st: Alice, 2nd: Charlie, 3rd: Bob
        // => ranks = [1, 3, 2]

        record_preferences(ranks);

        printf("\n");
    }
    // if we have 5 ballots
    // after all ballots run record updated,
    // each ballot content:

    //     Alice
    //     Charlie
    //     Bob

    //     Alice
    //     Charlie
    //     Bob

    //     Bob
    //     Charlie
    //     Alice

    //     Bob
    //     Charlie
    //     Alice

    //     Charlie
    //     Alice
    //     Bob

    // preferences will be:
    //     preferences[0](alice)    == [0, 3, 2]
    //     preferences[1](Bob)      == [2, 0, 2]
    //     preferences[2](Charlie)  == [3, 3, 0]


    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 c_index = 0; c_index < candidate_count; c_index++)
    {
        // if name match, insert candidates to ranks
        if (strcmp(name, candidates[c_index]) == 0)
        {
            ranks[rank] = c_index;
            return true;
        }
    }

    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    int a_candiate_index = 0;
    int b_candiate_index = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // if only 3 candiates, it loop will be:
            // i: 0, j: 1 (rank0 v.s rank1)
            // i: 0, j: 2 (rank0 v.s rank2)
            // i: 1, j: 2 (rank1 v.s rank2)

            // if
            //    candiates = [1: Alice, 2: Bob, 3: Charlie]
            //    ranks = [0, 2, 1]
            //
            // it means:
            //    Alice > Charlie
            //    Alice > Bob
            //    Charlie > Bob
            //
            // so preferences will be:
            //    preferences[0](alice)   == [0, 1, 1]
            //    preferences[1](Bob)     == [0, 0, 0]
            //    preferences[2](Charlie) == [0, 1, 0]


            // find candiate_index in compare a, b
            a_candiate_index = ranks[i];
            b_candiate_index = ranks[j];
            // printf("i: %i, j: %i\n", i, j);
            // printf("a_candiate: %i - %s\n b_candiate: %i - %s\n", a_candiate_index, candidates[a_candiate_index], b_candiate_index, candidates[b_candiate_index]);

            // record who win this compare
            preferences[a_candiate_index][b_candiate_index]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // like record_preferences(), we need couting each pair's winner and loser
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // if only 3 candiates, it loop will be:
            // i: 0, j: 1
            // i: 0, j: 2
            // i: 1, j: 2
            // => pair_count will be 3

            // i is a_candidate_index
            // j is b_candidate_index
            int comparison_1 = preferences[i][j];
            int comparison_2 = preferences[j][i];

            // if candiates = [1: Alice, 2: Bob, 3: Charlie]
            // if a preferences is:
            //     preferences[0](alice)    == [0, 3, 2]
            //     preferences[1](Bob)      == [2, 0, 2]
            //     preferences[2](Charlie)  == [3, 3, 0]

            // we will insert each pairs winner and loser
            // e.g. in first loop: i == 0(alice), b == 1(Bob)
            // comparison_1 = preferences[0][1] => is 3
            // comparison_2 = preferences[1][0] => is 2
            // so we can figure out winner is Alice, loser is Bob in this pair

            if (comparison_1 > comparison_2)
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (comparison_1 < comparison_2)
            {
                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)
{
    // if candiates = [1: Alice, 2: Bob, 3: Charlie]
    // if a preferences is:
    //     preferences[0](alice)    == [0, 3, 2]
    //     preferences[1](Bob)      == [2, 0, 2]
    //     preferences[2](Charlie)  == [3, 3, 0]

    // if pairs is:
    //     pairs[0](1st) => winner: 0(Alice),   loser: 1(Bob)
    //     pairs[1](2nd) => winner: 2(Charlie), loser: 0(Alice)
    //     pairs[2](3rd) => winner: 2(Charlie), loser: 1(Bob)

    // result will be [1, 1, 1]

    int strength_array[pair_count];
    int winner;
    int loser;

    for (int i = 0; i < pair_count; i++)
    {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        strength_array[i] = preferences[winner][loser] - preferences[loser][winner];
    }

    // desc sort
    sort(strength_array, 0, pair_count - 1);
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int winner;
    int loser;
    for (int i = 0; i < pair_count; i++)
    {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        if (!has_cycle(winner, loser))
        {
            locked[winner][loser] = true;
        }
    }

    return;
}

// Print the winner of the election
void print_winner(void)
{
    int i = 0;
    int j = 0;
    bool edge;
    while (i < candidate_count)
    {
        edge = locked[j][i];
        if (j == candidate_count && !edge)
        {
            printf("%s\n", candidates[i]);
            break;
        }
        else if (!edge)
        {
            j++;
        }
        else
        {
            i++;
            j = 0;
        }
    }
}

void sort(int array[], int start, int end)
{
    if (end > start)
    {
        int middle = (start + end) / 2;

        sort(array, start, middle);
        sort(array, middle + 1, end);

        merge(array, start, middle, end);
    }
}

void merge(int array[], int start, int middle, int end)
{
    int i = start;
    int j = middle + 1;
    int k = 0;

    typedef struct
    {
        int winner;
        int loser;
    } pair_temp;

    pair_temp pairs_temp[pair_count];

    while (i <= middle && j <= end)
    {
        if (array[i] >= array[j])
        {
            pairs_temp[k].winner = pairs[i].winner;
            pairs_temp[k].loser = pairs[i].loser;
            i++;
            k++;
        }
        else
        {
            pairs_temp[k].winner = pairs[j].winner;
            pairs_temp[k].loser = pairs[j].loser;
            j++;
            k++;
        }
    }

    while (i <= middle)
    {
        pairs_temp[k].winner = pairs[i].winner;
        pairs_temp[k].loser = pairs[i].loser;
        i++;
        k++;
    }

    while (j <= end)
    {
        pairs_temp[k].winner = pairs[j].winner;
        pairs_temp[k].loser = pairs[j].loser;
        j++;
        k++;
    }
    for (i = start; i <= end; i++)
    {
        pairs[i].winner = pairs_temp[i - start].winner;
        pairs[i].loser = pairs_temp[i - start].loser;
    }
}

bool has_cycle(int winner, int loser)
{
    if (locked[loser][winner] == true)
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[i][winner] == true)
        {
            return has_cycle(i, loser);
        }
    }
    return false;
}

:::

--

:::spoiler (點擊展開) 個人覺得比較好讀的程式碼風格

#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];
// e.g. if have 3 candidates, all pairs will be `3 * (3-1) / 2` = 3
// it will map on record_preferences() and add_pairs()

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

void sort(int array[], int start, int end);
void merge(int array[], int start, int middle, int end);
bool has_cycle(int winner, int loser);

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++) {
        /* sample: candiates = [1: Alice, 2: Bob, 3: Charlie] */

        // ranks[i] is voter's ith preference
        int ranks[candidate_count];
        /* e.g. ranks[3] */

        // 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;
            }
        }
        /* 
            e.g. a ballot content is 1st: Alice, 2nd: Charlie, 3rd: Bob
            => ranks = [1, 3, 2]
         */        
        record_preferences(ranks);

        printf("\n");
    }
    
    /* 
        if we have 5 ballots
        after all ballots run record updated,
        each ballot content:

            Alice
            Charlie
            Bob

            Alice
            Charlie
            Bob

            Bob
            Charlie
            Alice

            Bob
            Charlie
            Alice

            Charlie
            Alice
            Bob

        preferences will be:
            preferences[0](alice)    == [0, 3, 2]
            preferences[1](Bob)      == [2, 0, 2]
            preferences[2](Charlie)  == [3, 3, 0]    
     */

    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 c_index = 0; c_index < candidate_count; c_index++) {
        // if name match, insert candidates to ranks
        if (strcmp(name, candidates[c_index]) == 0) {
            ranks[rank] = c_index;
            return true;
        }
    }

    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    int a_candiate_index = 0;
    int b_candiate_index = 0;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = i + 1; j < candidate_count; j++) {
            /* 
                if only 3 candiates, it loop will be:
                i: 0, j: 1 (rank0 v.s rank1)
                i: 0, j: 2 (rank0 v.s rank2)
                i: 1, j: 2 (rank1 v.s rank2)

                if
                candiates = [1: Alice, 2: Bob, 3: Charlie]
                ranks = [0, 2, 1]
                
                it means:
                Alice > Charlie
                Alice > Bob
                Charlie > Bob
                
                so preferences will be:
                preferences[0](alice)   == [0, 1, 1]
                preferences[1](Bob)     == [0, 0, 0]
                preferences[2](Charlie) == [0, 1, 0]            
             */

            // find candiate_index in compare a, b
            a_candiate_index = ranks[i];
            b_candiate_index = ranks[j];

            // record who win this compare
            preferences[a_candiate_index][b_candiate_index]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // like record_preferences(), we need couting each pair's winner and loser
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            /* 
                if only 3 candiates, it loop will be:
                i: 0, j: 1
                i: 0, j: 2
                i: 1, j: 2
                => pair_count will be 3
             */

            // i is a_candidate_index
            // j is b_candidate_index
            int comparison_1 = preferences[i][j];
            int comparison_2 = preferences[j][i];

            /* 
                if candiates = [1: Alice, 2: Bob, 3: Charlie]
                if a preferences is:
                    preferences[0](alice)    == [0, 3, 2]
                    preferences[1](Bob)      == [2, 0, 2]
                    preferences[2](Charlie)  == [3, 3, 0]

                we will insert each pairs winner and loser
                e.g. in first loop: i == 0(alice), b == 1(Bob)
                comparison_1 = preferences[0][1] => is 3
                comparison_2 = preferences[1][0] => is 2
                so we can figure out winner is Alice, loser is Bob in this pair
             */

            if (comparison_1 > comparison_2) {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (comparison_1 < comparison_2) {
                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)
{
    /* 
        if candiates = [1: Alice, 2: Bob, 3: Charlie]
        if a preferences is:
            preferences[0](alice)    == [0, 3, 2]
            preferences[1](Bob)      == [2, 0, 2]
            preferences[2](Charlie)  == [3, 3, 0]

        if pairs is:
            pairs[0](1st) => winner: 0(Alice),   loser: 1(Bob)
            pairs[1](2nd) => winner: 2(Charlie), loser: 0(Alice)
            pairs[2](3rd) => winner: 2(Charlie), loser: 1(Bob)

        result will be [1, 1, 1]
     */

    int strength_array[pair_count];
    int winner;
    int loser;

    for (int i = 0; i < pair_count; i++) {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        strength_array[i] = preferences[winner][loser] - preferences[loser][winner];
    }

    // desc sort
    sort(strength_array, 0, pair_count - 1);
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int winner;
    int loser;
    for (int i = 0; i < pair_count; i++) {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        if (!has_cycle(winner, loser))
            locked[winner][loser] = true;
    }

    return;
}

// Print the winner of the election
void print_winner(void)
{
    int i = 0;
    int j = 0;
    bool edge;
    while (i < candidate_count) {
        edge = locked[j][i];
        if (j == candidate_count && !edge) {
            printf("%s\n", candidates[i]);
            break;
        }
        else if (!edge) {
            j++;
        }
        else {
            i++;
            j = 0;
        }
    }
}

void sort(int array[], int start, int end)
{
    if (end > start) {
        int middle = (start + end) / 2;

        sort(array, start, middle);
        sort(array, middle + 1, end);

        merge(array, start, middle, end);
    }
}

void merge(int array[], int start, int middle, int end)
{
    int i = start;
    int j = middle + 1;
    int k = 0;

    typedef struct {
        int winner;
        int loser;
    } pair_temp;

    pair_temp pairs_temp[pair_count];

    while (i <= middle && j <= end) {
        if (array[i] >= array[j]) {
            pairs_temp[k].winner = pairs[i].winner;
            pairs_temp[k].loser = pairs[i].loser;
            i++;
            k++;
        }
        else {
            pairs_temp[k].winner = pairs[j].winner;
            pairs_temp[k].loser = pairs[j].loser;
            j++;
            k++;
        }
    }

    while (i <= middle) {
        pairs_temp[k].winner = pairs[i].winner;
        pairs_temp[k].loser = pairs[i].loser;
        i++;
        k++;
    }

    while (j <= end) {
        pairs_temp[k].winner = pairs[j].winner;
        pairs_temp[k].loser = pairs[j].loser;
        j++;
        k++;
    }

    for (i = start; i <= end; i++) {
        pairs[i].winner = pairs_temp[i - start].winner;
        pairs[i].loser = pairs_temp[i - start].loser;
    }
}

bool has_cycle(int winner, int loser)
{
    if (locked[loser][winner] == true)
        return true;

    for (int i = 0; i < candidate_count; i++) {
        if (locked[i][winner] == true)
            return has_cycle(i, loser);
    }
    return false;
}

:::

--

執行

驗證