Coding Solution

Conway Sequence – CodinGame solution in C

Mediumlook-and-sayrun-length encodinglistsUpdated
Short answer

Start from the list [R] and apply the look-and-say step L-1 times: walk the current list, group equal consecutive values and replace each group by its length followed by the value. Work on a list of integers rather than on a string of digits, because R can be 2 or 3 digits long and must be read as one element. Print the final list separated by single spaces.

The problem

The sequence starts with a single number R (1 to 100). Each following line describes the previous one: you read it left to right, and every run of identical consecutive numbers becomes two numbers, how many times it appears and the value itself. So 1 becomes 1 1, then 2 1, then 1 2 1 1, and so on.

Given R and a line index L (up to 25), print line L with its numbers separated by spaces. This is the look-and-say sequence, but with the twist that elements are whole numbers, not individual digits.

Approach, step by step

  1. Represent a line as a list of integersStore [R] as the first line. Keeping integers instead of a digit string means 100 stays one element and counts such as 12 never get split into 1 and 2.
  2. Run-length encode the current lineWalk the list keeping the current value and how many times it has appeared in a row. When the value changes, append count then value to the new list and restart the counter.
  3. Flush the final runAfter the loop the last group has not been written yet. Appending it explicitly is the line most people forget.
  4. Repeat L-1 times and printLine 1 is [R] itself, so you apply the step L-1 times. Join with single spaces and avoid a trailing space.

Complexity

TimeO(total length)
SpaceO(length of line L)

Each step is linear in the size of the current line. Look-and-say lines grow by about 30% per step (Conway's constant ≈ 1.3036), so line 25 has roughly a thousand elements and the whole run is instant.

Solution code

Conway Sequence – C

Keeps each line as a space-separated string, tokenises it with strtok and atoi, and rewrites the next line with sprintf into a 10000-byte buffer. The buffer is large enough for L ≤ 25 (about 1200 elements of at most 4 characters), but a list of ints would be simpler.

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

int main(int argc, char **argv)
{
    int R, L;
    scanf("%d\n%d\n", &R, &L);

    char line[10000];
    char newline[10000];
    sprintf(newline, "%d", R);
    
    for (int i = 1; i < L; i++) {
        /* copies the last known term of the sequence in 'line'
           the next term will be stored into 'newline'*/
        strncpy(line, newline, 10000);
        char *token;
        char *iter = newline;
        
        int val = -1;
        int count = 0;
        /* Parses the last known term
          updating the number of consecutive identical digits
          and printing when the digit changes*/
        token = strtok(line," ");
        while (token != NULL) {
            int current = atoi(token);
            if (current == val)
                count++;
            else {
                if (count != 0)
                    iter += sprintf(iter, "%d %d ", count, val);
                val = current;
                count = 1;
            }
            token = strtok(NULL," ");
        }
        sprintf(iter, "%d %d\n", count, val);
    }

    printf(newline);
    return EXIT_SUCCESS;
}
            

Common mistakes

Going further

A property few write-ups mention gives you a free test oracle: for every seed R from 2 to 100, R stays as the very last element of every line and never merges with anything, and everything in front of it is identical whatever R is. Line 6 is 1 1 1 3 1 2 2 1 1 followed by R, for R = 2 just as for R = 100, and no number other than R ever exceeds 3. Only R = 1 behaves differently, because the seed itself can join the runs of 1s (it gives the classic 1, 1 1, 2 1, 1 2 1 1, 1 1 1 2 2 1, 3 1 2 2 1 1). So if your output for R = 100 does not end in 100, or its prefix differs from your R = 2 output, you have a parsing bug, almost always multi-digit numbers being split into digits.

FAQ

Is the Conway Sequence the same as look-and-say?

Yes, it is John Conway's name for the look-and-say sequence. The CodinGame version just lets the seed be any number up to 100 and treats it as a single element.

How long does line 25 get?

Starting from 1, line 25 has 1182 elements. Any dynamic list or a buffer of a few kilobytes is enough.

Can I solve it with regular expressions?

In languages with backreferences, a pattern matching a value followed by its repeats works, but you must match whole space-separated numbers, not single characters, or multi-digit seeds break.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome