Coding a Look-and-Say sequence should be fun, just like any C programming project where you’re not under pressure from a deadline. From last week’s Lesson, I was able to create a nested loop that takes a number and outputs its Look-and-Say values. It’s time to update this code to output a sequence.

I tried to keep the entire sequence in the main() function, though after a while it became obvious that a function is required. This function, which I name looksay(), requires an integer value as its argument and returns an integer value, the next number in the sequence.

This code went through several iterations before I recognized that the sequence quickly overflows the integer data type container. The range of an integer on most modern computers is between -2,147,483,684 and 2,147,483,647 signed, or zero to 4,294,967,295 unsigned. While I wanted to see 20 values of the sequence output, I was barely able to get six!

To ensure that the looksay() function could handle larger values, I used an unsigned long long value, which has a range from 0 to 18,446,744,073,709,551,615. Here is the code:

2024_09_21-Lesson.c

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

unsigned long long looksay(unsigned long long v)
{
    const int size = 128;
    char number[size],temp[size],*n,c;
    static char value[128];
    int count;
    unsigned long long r;

    /* convert and process the string */
    snprintf(number,size,"%lld",v);
    value[0] = '\0';        /* cap the buffer for strcat() */
    n = number;                /* initialize the pointer */
    while(*n)                /* loop through the string */
    {
        count = 0;            /* digit count */
        c = *n;                /* save the current digit */
        while( *n==c )        /* loop while the digits match */
        {
            count++;
            n++;
        }
        /* convert the result into a string */
        snprintf(temp,size,"%d%c",count,c);
        /* build the new value string */
        strcat(value,temp);
    }

    /* convert the string back into a long */
    r = strtoll(value,NULL,10);

    /* check for overflow */
    if( r==LONG_MAX )
    {
        puts("OVERFLOW");
        exit(1);
    }

    return(r);
}

int main()
{
    unsigned long long start;
    int x;

    printf("Starting value: ");
    scanf("%llu",&start);

    /* loop through 10 iterations */
    printf("%llu\n",start);
    for( x=0; x<10; x++ )
    {
        start = looksay(start);
        printf("%llu\n",start);
    }

    return 0;
}

The main() function uses unsigned long long variable start, obtained from the user. The scanf() function requires the %llu placeholder to represent an unsigned long long value. A for loop repeats ten times, obtaining the Look-and-Say values in the sequence and outputting each one.

The looksay() function is base on code presented in last week’s Lesson, though with the unsigned long long used instead of int. The snprintf() function is updated with the %llu placeholder.

The biggest change is building a string, value, which contains the Look-and-Say number. Two statements are used:

snprintf(temp,size,"%d%c",count,c);
strcat(value,temp);

The first statement converts a Look-and-Say value for a series of digits into a string, stored in variable temp. This string is then appended (concatenated) to the string value.

Once the nested loops build the next value in the sequence (as a string), the strtoll() function converts the string into a long long value stored in variable r.

The code worked at first, but the final values output were always 9223372036854775807, which seemed odd to me. I debugged the code by outputting the string value created, which didn’t match the result returned from the strtoll() function.

After a few frustrating moments, it occurred to me that the strtoll() function was overflowing. This is the reason why I added the test for overflow at the end of the function:

if( r==LONG_MAX )
{
    puts("OVERFLOW");
    exit(1);
}

The OVERFLOW constant is defined in the limits.h header file. This test is trigged in the looksay() function, which removes the bogus value from the output, but proves that the function has its limits. Here is a sample run:

Starting value: 1
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
OVERFLOW

The looksay() function actually finds the next value in the sequence, 13211311123113112211. If you add a puts() function to output string value before the strtoll() function, you see this value properly generated. But it’s value is beyond the range of an unsigned long long integer — if you can fathom that.

The code almost generates the results I wanted from the Look-and-Say sequence, shy one. A possible solution is to use the GMP Library, which I wrote about in a previous Lesson. I may attempt to do so in the future, but I’m happy with the code now, and relieved that the issue with my attempt at a Look-and-Say sequence is overflow and not any booboo that I may have made.