I wrote this C code to solve Advent of Code 13 2020. I know, it's probably not viable trying to solve it via brute force, but the program gives the correct answer for the example input.
If I try to let gcc optimize the code, it gives the correct result with -O1, but creates an endless loop with -O2. After all the research my conclusion is that there is undefined behavior in my code, I guess it has to do with the probability that "found" may never be higher than 0 and so "time" would overflow.
Here is the question: Does anybody know how to patch that undefined behavior?
"-Wall -Wextra -pedantic" don't even issue a warning or something.
I just can't find a solution. If I, for example, change the head of the while loop to (!found && time < 10000000000), so that no overflow can occur, it just breaks the loop right away with a time value of 10000000003 when compiled with -O2, but still gives the right result with -O1.
Here is the code, the correct result would be "1068781":
#include <stdio.h>
int main()
{
unsigned int busses[] = {7, 0, 13, 2, 59, 1, 31, 0, 19};
unsigned int busses_used = 9;
unsigned int i = 0;
unsigned int found = 0;
unsigned long long time = 0;
unsigned int offset = 0;
unsigned int increment = 7;
while (!found) {
time += increment;
offset = 0;
for (i = 0; i < busses_used; i++) {
if ((time + offset) % busses[i] == 0) {
found = 1;
offset++;
} else {
found = 0;
break;
}
offset += busses[++i];
}
}
printf("Endtime: %lld\n", time);
return 0;
}
Edit: Thanks to KamilCuk for pointing out that the code is accessing the array out of bounds and teaching how to find out that it is doing so. The problem is solved by adding another 0 at the end of the "busses" array and therefore also setting "busses_used" to 10 instead of 9.
