dontmindmehere307's stats

#include <stdio.h>
#include <stdlib.h>

char gijswijt_next(const char *sequence, unsigned len) {
    // [ ] this is dynamic programming
    // [ ] this is tabulation
    // [ ] this is memoization
    // [x] this is quadratic but pretty much instant up to like 10000
    char max_repeat_count = 1;
    for (unsigned subseq_len = 1; subseq_len <= len / 2; subseq_len++) {
        char repeat_count = 1;
        unsigned current_count = 0;
        for (unsigned i = len - 1; i >= subseq_len; i--) {
            if (sequence[i] != sequence[i - subseq_len]) {
                break;
            }
            current_count++;
            if (current_count == subseq_len) {
                repeat_count++;
                current_count = 0;
            }
        }
        if (max_repeat_count < repeat_count) {
            max_repeat_count = repeat_count;
        }
    }
    return max_repeat_count;
}

int main(int argc, char *argv[]) {
    unsigned max_iter = 220;
    if (argc >= 2) {
        if (sscanf(argv[1], "%u", &max_iter) != 1) {
            fprintf(stderr, "USAGE: %s [max iterations (default %u)]\n",
                    argv[0], max_iter);
        }
    }
    char *sequence = malloc((max_iter + 1) * sizeof(*sequence));
    unsigned sequence_len = 1;
    sequence[0] = '1';
    // no wait ouch oof this is cubic help
    while (max_iter --> 1) {
        char next = gijswijt_next(sequence, sequence_len);
        sequence[sequence_len++] = next + '0';
    }
    sequence[sequence_len] = '\0';
    puts(sequence);
    /*   ^^^^^^^^ the fucking thing you know what it is
    ^^^^ print the is to output write */
    free(sequence);
}