-1

This is my first time posting a coding question on any website, so apologies if i dont do a great job. Constructive feedback is very welcome. I am working on the tideman problem in cs50, if that is meaningful to anyone.

I cant figure out a way to break out of the inner nested loop but continue the outer loop. As in, if is_cycle is true, the lines:

locked[pairs[i].winner][pairs[i].loser] = true;
num_locked++;

need to be skipped for that current iteration of the outer loop.

Thank you so much.

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int num_locked = 0;
    //loop through pairs
        //has loser won before?
            //if no, lock the pair
            //if yes, call is_cycle on pair. if its not a cycle lock the pair
    for (int i = 0; i < pair_count; i++)
    {
        //has the loser won before?
        for (int j = 0; j < i; j++)
        {
            if (pairs[i].loser == pairs[j].winner)
            {
                //if the loser has won before and it creates a cycle, break the inner loop, continue outer
                if (is_cycle(pairs[i], pairs[j], num_locked))
                {
                    break;
                }
            }
        }
        //this is incorrect this will lock the pair each time
        locked[pairs[i].winner][pairs[i].loser] = true;
        num_locked++;
    }

    return;
}

I have tried searching through stack overflow. Some mentioned a goto function but most people said that is bad programming. someone else mentioned creating a separate function and using return statements but i need that outer loop to continue, not stop. And one other answer suggested using flags, which after more searching i still dont get how that could help.

user20633421
  • 3
  • 1
  • One solution is to create a boolean which says whether or not it should go through the inner loop. If the condition fails, then the switch can go to false, and the lines can be skipped. It's certainly not as sophisticated, but it works. – Hhadley Nov 29 '22 at 13:06
  • https://stackoverflow.com/questions/9695902/how-to-break-out-of-nested-loops might help you – FreudianSlip Nov 29 '22 at 13:07
  • Create a function that returns some indicator for the inner loop, and use that return value to decide to continue the outer loop or not. – kotatsuyaki Nov 29 '22 at 13:08
  • 1
    See the discussion at this earlier question: [How to avoid use of goto and break nested loops efficiently](https://stackoverflow.com/questions/50530113/). – Steve Summit Nov 29 '22 at 13:09
  • 3
    I recommend against "solving" this sort of problem using extra, Boolean flags. Those flags can be at least as confusing as using the dreaded `goto`. – Steve Summit Nov 29 '22 at 13:10
  • 2
    Whenever you have a nested loop like your `for (int j = 0; j < i; j++)`, with a comment before it saying "`has the loser won before?`", it is almost always a good idea to break that loop out into a separate function with a name like `user_has_won_before()`. – Steve Summit Nov 29 '22 at 13:18
  • Ignore those "most people" and use `goto`. The `goto` is just a tool for getting things done, though a bit sharper than the other ones. – tstanisl Nov 29 '22 at 17:23
  • 'someone else mentioned creating a separate function and using return statements but i need that outer loop to continue, not stop' eh?? A return in an 'inner-loops' function would not stop the 'outer-loop' caller from continuing.... – Martin James Nov 29 '22 at 17:37

3 Answers3

3

Although goto should generally be avoided if there is a better alternative, for breaking out of a nested loop or continuing an outer loop, I do recommend using goto, as there is no clearly better alternative.

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int num_locked = 0;
    //loop through pairs
        //has loser won before?
            //if no, lock the pair
            //if yes, call is_cycle on pair. if its not a cycle lock the pair
    for (int i = 0; i < pair_count; i++)
    {
        //has the loser won before?
        for (int j = 0; j < i; j++)
        {
            if (pairs[i].loser == pairs[j].winner)
            {
                //if the loser has won before and it creates a cycle, break the inner loop, continue outer
                if (is_cycle(pairs[i], pairs[j], num_locked))
                {
                    goto continue_outer_loop;
                }
            }
        }
        //this is incorrect this will lock the pair each time
        locked[pairs[i].winner][pairs[i].loser] = true;
        num_locked++;

    continue_outer_loop:
        continue;
    }

    return;
}
Andreas Wenzel
  • 22,760
  • 4
  • 24
  • 39
  • I would have said like you some years ago, goto can be useful for that specific case, but here i see a way to avoid it : now i tend to make functions with no more than 1 loop level. Simply giving a name to most inner loop, making a function from it, and again until function is flat. But i wouldn't throw you to hell for using goto here. – AR7CORE Nov 29 '22 at 13:59
1

A flag is just a variable that lets you keep track of how things went, and adapt:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
  int num_locked = 0;
  //loop through pairs
  //has loser won before?
  //if no, lock the pair
  //if yes, call is_cycle on pair. if its not a cycle lock the pair
  for (int i = 0; i < pair_count; i++)
  {
    //has the loser won before?
    bool found = false;
    for (int j = 0; j < i; j++)
    {
        if (pairs[i].loser == pairs[j].winner)
        {
            //if the loser has won before and it creates a cycle, break the inner loop, continue outer
            if (is_cycle(pairs[i], pairs[j], num_locked))
            {
                found = true;
                break;
            }
        }
    }
    if (!found)
    {
      locked[pairs[i].winner][pairs[i].loser] = true;
      num_locked++;
    }
  }
}

Also note that there is no need to return at the end of a void function, it's okay to just fall off the end. :)

unwind
  • 391,730
  • 64
  • 469
  • 606
  • It would also be possible to omit the `break` when the boolean variable `found` is added to the loop condition: `for (int j = 0; !found && j < i; j++)` – Bodo Nov 29 '22 at 13:19
  • @Bodo Yes but that makes each iteration more expensive, since it's then checking the boolean every time. Since we need the statement to set the flag, we can just as well `break` out at that point and remove the check from the loop. – unwind Nov 30 '22 at 08:33
  • Optimization should be left to the compiler. The code created by `gcc -O` does not show an explicit check of the `found` flag in the version without break. I cannot see if one version is more expensive because the code differs too much. So using `break` or adding the flag to the loop condition is a matter of taste. – Bodo Nov 30 '22 at 13:10
1

One way is to add a test after the inner loop to check whether it was broken out of early. E.g.:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int num_locked = 0;
    //loop through pairs
        //has loser won before?
            //if no, lock the pair
            //if yes, call is_cycle on pair. if its not a cycle lock the pair
    for (int i = 0; i < pair_count; i++)
    {
        int j;
        //has the loser won before?
        for (j = 0; j < i; j++)
        {
            if (pairs[i].loser == pairs[j].winner)
            {
                //if the loser has won before and it creates a cycle, break the inner loop, continue outer
                if (is_cycle(pairs[i], pairs[j], num_locked))
                {
                    break;
                }
            }
        }
        if (j < i)
        {
            continue;
        }
        locked[pairs[i].winner][pairs[i].loser] = true;
        num_locked++;
    }

    return;
}

The scope of the j variable needed to be changed so that it could be accessed outside the inner loop.

Ian Abbott
  • 15,083
  • 19
  • 33