Day 10 - Number game

We need to code a “look-and-say” sequence. So, starting from 1, we “say” that we have “one one”, so we write 11. Then we have “two ones”, 21. Let’s take some arbitrary test number to get a sense of what’s going on, and start from 5231:

I think. So we’ve got a string of digits whose length is going to grow, I am assuming at some alarming rate. We need to find out how many digits we get after 40 rounds, starting from a sequence of (for my input at least) 10 digits.

The key part will be an expand function, which needs to take a pointer to a string (char*) as an input, and return the same. It will have to:

char* expand(char* s){
    char cur = s[0];    // current digit character
    int n_reps = 0;     // number of repetitions of current digit
    char* p = s;        // pointer to where we're at in the string, starting from the beginning
    int cap = strlen(s)+1;  // capacity that we need in memory to store a copy of the string, to be expanded.
    char* news = malloc(sizeof(char)*cap); // new string
    int offset = 0;     // where we're at in the new string
    while (*p != '\0'){ // iterate on the old string until we find the null character
        if (*p == cur) n_reps++; // if we're repeating the same character, increase counter
        else {          // we found a new character, we need to update the new string
            if (offset+2 >= cap){   // if necessary: double size of news
                cap *= 2;
                news = realloc(news, cap);
            }
            sprintf(news+offset, "%d%c", n_reps, cur);  // print number of repetitions and digit into new string
            offset += 2;    // update offset in new string
            n_reps = 1;     // reset number of repetitions
            cur = *p;       // set new current character digit
        }
        p++;            // move to next character in old string 
    }
    // don't forget the last one
    if (offset+2 >= cap){   
        cap += 2;
        news = realloc(news, cap);
    }
    sprintf(news+offset, "%d%c\n", n_reps, cur);
    // don't forget to add a null character
    news[offset+2] = '\0';
    // reallocate memory for new string to the necessary length (to remove unecessary space)
    news = realloc(news, strlen(news)+1);
    // free the old string
    free(s);
    // return the new string
    return news;
}

Then we just need to expand 40 times and compute the length at the end. We need to use a malloc to copy the input as well, instead of doing char content[] = INPUT, otherwise we can’t free it in expand. Otherwise, it’s all very straightforward.

void solve(){
    char* content = malloc(sizeof(char)*(strlen(INPUT)+1));
    sprintf(content, "%s", INPUT);

    printf("Input = %s\n", content);
    for (int i = 1; i <= 40; i++){
        content = expand(content);
        printf("%d: %d\n", i, strlen(content));
    }

    printf("Part 1: %d\n", strlen(content));
}

Part 2: same, but 50 times instead of 40. My implementation doesn’t see to get into any trouble with that. Now we have about 3.5 million digits, which is a very large number, but since one character is just one byte, in the end we just need a few megabytes of RAM to deal with it. Even at 2026 RAM prices that’s not too bad.