Logical flaw in Problem Set 3 - Tideman?

Question

Whilst writing my code for Tideman in Problem Set 3, I had many problems with the lock pair function, as I am very new to coding. Some research I did online also showed that this question is notoriously hard given that it appears in just week 3.

My code is as follows:

bool iscycle(int index, bool visited[])
{
    if (visited[index])
    {
        return true;
    }
    visited[index] = true;
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[index][i] && iscycle(i, visited))
        {
            return true;
        }
    }
    return false;
}

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

The only error is as follows:

:( lock_pairs skips final pair if it creates cycle
        lock_pairs did not correctly lock all non-cyclical pairs

I have been staring at my code for days and am simply unable to wrap my head around what is wrong. In fact, many of the codes I have seen for the lock_pairs function on this site usually has issues with the middle pair, so I am truly intrigued by what the logical flaw is in mine.

Answer 1

I have had this exact same problem, but managed to resolve it tonight. If this is the only error you are getting, your code is fundamentally correct (as not locking middle pairs would be the greatest challenge in my view).

What I found was that the scenarios of pairs and candidates that I had originally constructed were too simplistic. That is, my code was "good enough" to deal with most cases but not ALL cases. You therefore need to come up with a scenario that really puts the combinations to the test.

What I suggest you do is carve out a mini-programme alongside your tideman programme, that deals only with the locking of pairs. This will save you having to go through the tideman programme in inputting candidate names, victory margins etc. You can easily type in the pairs[x].winner and pairs[x].loser combinations in your mini-programme's main code.

In terms of a stress-test, I would suggest the following:

1. Use the maximum number of 9 candidates (i.e. A through I).
2. Physically draw the "victory" graph on a piece of paper - this way you will see the "final pair" that is probably causing your problem.
3. Start with A. In the first cycle, A must beat B, B must beat C, C must beat D, and D must beat E.
4. In the second cycle, A must beat F, F must beat G, G must beat H, and H must beat I.
5. So far there are obviously no cycles.
6. Now make I beat C - this links the two cycles, but there will still be no overall cycle. Test this for yourself.
7. For the final pair, make E beat F. This seems identical to the previous point, but you will see the overall cycle being completed.

In summary, there are 9 candidates and 10 pairs. Your code should accept all pairs except the final one. I would use "printf" functionality to see where you are positioned in your code, and why it is not accepting the final pair.

I hope this helps!