CS50X tideman - Students correct sort_pairs sometimes fails

[max-min-median]

CS50x Tideman - Correct sort_pairs algorithm fails

Problem:

• Student attempts to calculate pair strengths by iterating through preferences in the same order that they would have generated the pairs in add_pairs.
• Pair strengths are thus not assigned correctly due to check50 setting up the pairs differently (i.e. not in typical index order).

// setup case 3 (line 53 of testing.c)
pairs[0].winner = 2;
pairs[0].loser = 1;
pairs[1].winner = 0;
pairs[1].loser = 1;
pairs[2].winner = 0;
pairs[2].loser = 2;

• Even if we changed it to set it up in typical index order, it might still not match the student's approach, e.g. if while processing candidates 0 and 4, student adds either 0, 4 or 4, 0, as opposed to only adding 4, 0 while processing 4, 0.

Personal opinions:

• It should not be considered wrong of the student to expect that any pairs array handed to them be generated in the same order as they themselves would have done in add_pairs. After all, the student is authoring all of these functions.
• This is further compounded by the student being unable to modify the pair struct to include the strength of victory.
• Thus, my humble opinion is that it would be fairer to the student if the checker were to use the student's own add_pairs function to generate the pairs (after checking the correctness of add_pairs, of course).

Suggested Solution:

• NB: I have also modified setup case 3 to have more candidates (5), and thus more pairs (10).

// setup case 3 (line 53 of testing.c)
case 3:
    candidate_count = 5;
    pair_count = 0;
    int temp_prefs[5][5] = {{  0, 12,  0, 11,  3 },
                            {  8,  0,  7,  5,  1 },
                            { 20, 13,  0, 14,  4 },
                            {  9, 15,  6,  0, 18 },
                            { 17, 19, 16,  2,  0 },
    };
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            preferences[i][j] = temp_prefs[i][j];
    break;

• Now call student's add_pairs() before sort_pairs().

// test case 8 (line 184 of testing.c)
case 8:
    add_pairs();
    sort_pairs();
    for (int i = 0; i < 10; i++)
        printf("%i %i ", pairs[i].winner, pairs[i].loser);
    break;

• Expected result:

# line 87 of __init__.py
def sort_pairs1():
    """sort_pairs sorts pairs of candidates by margin of victory"""
    check50.run("./tideman_test 3 8").stdout("2 0 4 1 3 4 4 0 4 2 3 1 2 3 2 1 0 1 0 3 ").exit(0)