why my code work in small instances only?

Question

I have developed a code for my problem and it seems like it is working but when I increase the problem size, it does not output anything. in my problem I have several courses with multiple meetings each week with a condition of each course must have at least one overall in all weeks(e.g. in a 4 weeks case, atleast one meeting in 4 weeks combined).

A sample of decired out put with 4 courses and 4 weeks looks like the following:

0, 0, 2, 0, 
1, 0, 0, 0, 
0, 1, 0, 1,
0, 2, 0, 3,

I have written the following recursive code and it is working for small number of courses and weeks but when I increase these number it does not output anything. even for small cases sometime it does not output anything and I have to run it againg to get a result. here is my code:

//headers
#include <iostream>
//global parameters
const int NumberOfCourses = 4;
const int AvailableWeeks = 4;
double Desired[NumberOfCourses][AvailableWeeks];
//parameters deciding how many courses should we remove from schedule
//option 0:0 f2f meeting
//option 1:1 f2f meeting
//option 2:2 f2f meeting
//option 3:3 f2f meeting
const double DN_possibilites[4] = { 0.7, 0.15, 0.1, 0.05 };
double Rand;
long int OptionSelected;
double SumOfProbabiltiesSofar = 0;
double total = 0;
int c, w;
using namespace std;

void DN_generator() {
    long int currSysTime = time(NULL);
    srand(currSysTime);
    for (int c = 0; c < NumberOfCourses; c++) {
        for (int w = 0; w < AvailableWeeks; w++) {
            long int currSysTime = time(NULL);
            Rand = ((float)rand() / RAND_MAX);
            //cout << Rand << endl;
            long int OptionSelected;
            double SumOfProbabiltiesSofar = 0;
            for (int i = 0; i < 4; i++) {
                SumOfProbabiltiesSofar += DN_possibilites[i];
                if (Rand < SumOfProbabiltiesSofar) {
                    OptionSelected = i;
                    break;
                }
            }
            if (OptionSelected == 0) {
                Desired[c][w] = 0;
            }
            else if (OptionSelected == 1) {
                Desired[c][w] = 1;
            }
            else if (OptionSelected == 2) {
                Desired[c][w] = 2;
            }
            else if (OptionSelected == 3) {
                Desired[c][w] = 3;
            }
        }
    }

    for (c = 0; c < NumberOfCourses; c++) {
        total = 0;
        for (w = 0; w < AvailableWeeks; w++) {
            total += Desired[c][w];
        }
        if (total == 0) {
            DN_generator(); 
        }
    }
}


int main(){
    DN_generator();
    for (c = 0; c < NumberOfCourses; c++) {
        for (w = 0; w < AvailableWeeks; w++) {
            cout << Desired[c][w] << ", ";
        }
        cout << endl;
    } 
    return 0;
}

any help is much appreciated.

If the code behaves differently on different runs it is almost guaranteed to be UB in it somewhere. I would suggest you run it with a debugger and try to see what goes wrong when it gets stuck. — super, Apr 23 '22 at 17:26
Run this in a debugger and I'll bet it breaks on an endless recursion into `DN_generator`. if *any* week is *ever* fully zero-populated recursion ensues. If that repeats, so does the recursion. Get `long int currSysTime = time(NULL); srand(currSysTime);` *out* of your function and put it at the head of `main`, btw. That's probably contributory. — WhozCraig, Apr 23 '22 at 17:34
I did moved the long int currSysTime = time(NULL); srand(currSysTime); to the head of main and I ran it with a debugger. it breaks at double SumOfProbabiltiesSofar = 0; — MK_OR, Apr 23 '22 at 17:47

score 0 · Answer 1 · answered Apr 23 '22 at 17:41

I see at least four fundamental flaws in the shown code:

With the random seed getting reset to the system clock on every recursive iteration, every call to the recursive function within the same second will produce the same results. If any one of them results in a total sum of 0, the recursive function repeats and produces the same results. The simple code can run fast enough on modern CPUs to blow through the stack, and crash, in much less than the second.
Increasing the array size increases the chances of the first problem happening. The combination of these two factors is what results in the crash, but that's not the end of the problems in the shown code.
If the total sum is 0, a recursive call is made. When the recursive call returns, it happily resumes totaling all the remaining rows, which makes no logical sense. This is a flaw in the recursion algorithm
Finally, the shown code has guaranteed undefined behavior:

   SumOfProbabiltiesSofar += DN_possibilites[i];

The assumption in this line of the code is that on the last iteration SumOfProbabiltiesSofar becomes 1.0 and the following if statement's condition is guaranteed to evaluate to true. This is not true because floating point math is broken.

With the sufficiently large number of iteration it becomes likely that the random value will be enough close to 1 so that exceeds the almost-1.0 value that ends up being here. The for loop exits without initializing OptionSelected, resulting in undefined behavior. This logic must be fixed too.

All of these problems will need to be fixed before the shown algorithm works correctly.

why my code work in small instances only?

1 Answers1