crecursioncs50

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


Can someone help me understand whats wrong with my code Im working on this problem set https://cs50.harvard.edu/x/2023/psets/3/tideman/

bool CycleCheckRecursion(int L, int W)
// Checks if there is a cycle. Returns 1 if cycle is found.
{
    for (int q = 0;  q <= pair_count - 1; q++)
    {
        if (locked[q][W] == true)
        {
            if (locked[L][q] == true)
            {
                return 1;
            }
            else
            {
                CycleCheckRecursion(L, q);
            }
        }
    }
    return 0;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{        // TODO
    for (int y = 0; y <= pair_count - 1; y++)
    {
        if (!CycleCheckRecursion(pairs[y].loser, pairs[y].winner))
        {
            locked[pairs[y].winner][pairs[y].loser] = true;
        }
    }
}

This is what the terminal says after running check50

:) tideman.c exists
:) tideman compiles
:) vote returns true when given name of candidate
:) vote returns false when given name of invalid candidate
:) vote correctly sets rank for first preference
:) vote correctly sets rank for all preferences
:) record_preferences correctly sets preferences for first voter
:) record_preferences correctly sets preferences for all voters
:) add_pairs generates correct pair count when no ties
:) add_pairs generates correct pair count when ties exist
:) add_pairs fills pairs array with winning pairs
:) add_pairs does not fill pairs array with losing pairs
:) sort_pairs sorts pairs of candidates by margin of victory
:) 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

The middle pairs are being skipped as expected but for some reason the final pair is not being skipped. Can someone help me understand what part of my code is wrong or missing?


Solution

  • I figured it out with @Someprogrammerdude's and chatgpt's help.

    Calls and returns are still confusing to me so thats why I couldnt see the problem.

    bool CycleCheckRecursion(int L, int W)
    // Checks if there is a cycle. Returns 1 if cycle is found.
    {
        for (int q = 0;  q <= pair_count - 1; q++)
        {
            if (locked[q][W] == true)
            {
                if (locked[L][q] == true)
                    {
                        return 1;
                    }
                    else
                    {
                        if(CycleCheckRecursion(L, q))
                        return 1;
                    }
            }
        }
        return 0;
    }
    // Lock pairs into the candidate graph in order, without creating cycles
    void lock_pairs(void)
    {        // TODO
        for (int y = 0; y <= pair_count - 1; y++)
        {
            if (!CycleCheckRecursion(pairs[y].loser, pairs[y].winner))
            {
                locked[pairs[y].winner][pairs[y].loser] = true;
            }
        }
    }
    

    What I needed to do is to call

                {
                    CycleCheckRecursion(L, q);
                }
    

    again to see if it returned true or false. So I put it in an if statement and checked if it returned true. Then made it return true when it returned true. Heres the change below

                {
                    if(CycleCheckRecursion(L, q))
                    return 1;
                }
    

    Now I get this message from the terminal

    :) lock_pairs skips final pair if it creates cycle