0

I am new to coding and I am trying to solve the locked pairs part of the Tideman problem.

Currently, I am receiving the following two errors:

:) lock_pairs locks all pairs when no cycles

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

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

Could you please explain where the issue is and how to go about independently debugging similar problems in the future? Also, if possible could you help me implement my approach rather than suggest an alternate path? I want to get good at translating my thoughts into code even if the approach is not the most efficient.

TLDR of my reasoning (also in comments): I iterate through each pair, for each pair I set the locked array at the pair winner and pair loser index to true. I noticed that a direct graph has a cycle when every column and row has at least one truth. So, after locking a pair I iterate through each row and then each column all the while tracking the amount of rows/columns that are empty. In the end, if the empty_count is 0, I revert the initial lock.

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // iterate through each pair, locking them in, checking if there is at least one empty column/row left, if not, revert lock
    for (int i = 0; i < pair_count; i++)
    {
        int empty_count = 0;
        // locks in ith pair with the intention to reverse the lock if later found to be invalid
        locked[pairs[i].winner][pairs[i].loser] = true;
        // check that each row and column of the locked array has at least 1 row/coloumn without a truth value, aka there is always a source in the graph
        // this ensures that there are no loops
        
        // iterate through each row of direct graph
        
        for (int k = 0; k < candidate_count; k++)
        {
            int truths = 0;
            for (int l = 0; l < candidate_count; l++)
            {
                if (locked[k][l] == true)
                {
                truths++;
                }  
            }
            // increments empty_count if row had no truths
            if (truths == 0)
            {
                empty_count++;
            }
        }    
            
            
        // iterate through each column of direct graph
        
        for (int k = 0; k < candidate_count; k++)
        {
            int truths = 0;
            for (int l = 0; l < candidate_count; l++)
            {
                if (locked[l][k] == true)
                {
                truths++;
                }  
            }
            // increments empty_count if column had no truths
            if (truths == 0)
            {
                empty_count++;
            }
        }
            
        
        // there is no source when each row and column has at least one truth
        // so if num of empty rows/columns == 0 then revert initial lock
        if (empty_count == 0)
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }        
    
    
    return;
}
0

The problem is you`re first locking all the pairs. Take a look at this example:

 0  0  1  1 
 1  0  0  1
 0 (1) 0  1
 0  0  0  0

In order to have no cycles the marked truth should not be considered but you already put that truth there when you locked all the pairs so now you can't see the free column because it`s not free anymore.

And at the end: if num of empty rows/columns == 0 then revert initial lock you mean if empty_count is different than 0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .