function that returns the next number of a repeating sequence

Question

First of all, this is a school assignment, so I can't use the <math.h> library as a handicap. So as the title suggests, I tried to write a function that gets a sequence of positive numbers for its input, then returns the number of which the sequence would continue. For example, if the sequence is 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 then it would return a 3 because that's what the next number would be. The sequence of numbers always ends with -1, however, -1 is not part of the sequence, it merely marks its end.

Here's the function:

#include <stdio.h>
int predict(int seq[]) {
    int i, j;
    for (i = 0; seq[i] != -1; i++)
        ;
    int seqLength = i;
    int rep[i+1];
    for (j = 0; j < i + 1; j++)
        rep[j] = -1;
    i = 0;
    j = 1;
    while (seq[i] != -1) {
        if (rep[0] == seq[i]) {
            for (j = 1; seq[i + j] != -1; j++) {
                if (rep[j] == seq[i + j]) {
                    j++;
                } else {
                    rep[i] = seq[i];
                    j = 1;
                    break;
                }
            }
            i++;
        } else {
            rep[i] = seq[i];
            i++;
        }
    }
    for (i = 0; rep[i] != -1; i++)
        ;
    int repLength = i;
    return seq[seqLength % repLength];
}

int main() {
    int seq[20] = {1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 1, 1, 2, 1, 2, -1}; /*or any other positive numbers as long as it ends with -1*/
    printf("%d\n",predict(seq));
    return 0;
}

The seq (short for sequence) is the sequence of numbers the function gets as the input. seqLength is the number of how many numbers the seq has. The rep (short for repeat) is the part of the sequence which repeats itself. repLength is the number of how many numbers the rep has.

The function works for all three test cases which I know, for example:

For 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 it returns 3.
For 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 it returns 1.
For 1 2 1 1 2 1 2 3 1 2 1 1 2 1 2 it returns 3.

However, when I upload it to the school system that tests and appraises my function, it tests for an additional two test cases, which are wrong. The problem is, that I don't know the input sequence for those additional two test cases and therefore I don't know what to change in order for my functions to work for all test cases. Can someone see an error in my work and have an idea of what to change in order for my function to work for any repeating number sequences, even for unknown ones?

Answer 1

There is a corner case for which your algorithm does not work: if the repeated sequence has length seqLength, you will not find -1 in the rep array because it was defined with a length of seqLength and the end of list marker was never copied there. Hence the last loop will run past the end of rep and cause undefined behavior.

I'm afraid there are other problems, let's try and simplify the code:

• It would be safer to compare the index values to seqLength instead of testing for -1, which by the way you did not document as the end of list marker.

• Furthermore, it seems superfluous to copy the sequence into a rep array as this array would always contain an initial portion of seq.

• The problems seems to boil down to finding the length of the repeated pattern.

Here is a simplified version, with seqLength passed as an argument:

int predict(int seq[], int seqLength) {
    /* find the mininum value of repLength such that the sequence is
       a repeated pattern of length repLength */
    int i, repLength;
    for (repLength = 1; repLength < seqLength; replength++) {
        for (i = 0; i < seqLength; i++) {
            if (seq[i] != seq[i % repLength])
                break;
        }
        if (i == seqLength) {
            /* we found the pattern length */
            break;
        }
    }
    return seq[seqLength % repLength];
}