0

I have been working on the tideman problem from Problem Set 3. After multiple attempts, I have been able to pass all the required checks except one: "lock_pairs skips final pair if it creates cycle".

I realize that there are solutions available on the internet regarding this, but since I have tried to implement my custom form of a recursive solution, I would really appreciate some help on this.

Here's a snippet from the 'lock_pairs' and its helper, custom function that I have created:

// custom function for cycle checking
bool cycle_check(int from, int to)
{

    int neighbours[candidate_count];

    for (int i = 0; i < candidate_count; i++)
    {
        neighbours[i] = (int) locked[to][i]; // eg get all neighbours of A. (Wanting to check if we can establish pair from C to A)
    }

    if (neighbours[from] == 1) // if C exists in neighbours of A...
    {
        return true; //...then just return true. Since a path exists in reverse order already
    }

    int sum = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        sum += neighbours[i];
    }
    if (sum == 0) // if A has no neighbours...
    {
        return false; // ... then we can safely add this locked pair
    }

    else // else look for an indirect path from neighbours of A (for e.g)
    {
        for (int i = 0; i < candidate_count; i++)
        {
            if (neighbours[i] == 1) // if any other neighbour exists...
            {
                return false || cycle_check(from, to = i); //... then check for a possible path from that neighbour
            }
        }
    }
    
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
// to ascertain whether creating a locked_pair would creat a cycle or not...
// ... need to determine if a path already exists from (to to from)
// ... eg if want to see whether or not we can add a locked pair from C to A...
// ... need to see if a path from A to C already exists or not. If yes, then a cycle would be created. Hence we should not add.
void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        int from = pairs[i].winner;
        int to = pairs[i].loser;
        locked[from][to] = true;

        if (cycle_check(from, to)) // if path already exists...
        {
            locked[from][to] = false; //...set pair back to false
        }
    }

    return;
}

I have printed out the locked matrix at certain intervals including right at the end too. And despite it being seemingly correct, I am still unable to pass this check.

Any help on this would be highly appreciated, thanks.

You must log in to answer this question.

Browse other questions tagged .