Conway Sequence – CodinGame solution in C
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
- 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.
- 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.
- Flush the final runAfter the loop the last group has not been written yet. Appending it explicitly is the line most people forget.
- 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
O(total length)O(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
- Treating the line as a string of digitsWith R = 100 the second line must be '1 100', not '1 1 2 0'. Splitting into characters only works for single-digit starts, which is exactly what the later tests avoid.
- Forgetting the last groupThe emit happens when the value changes, so the final run is still pending when the loop ends. Missing it shortens every line by two numbers.
- Off-by-one on LL = 1 must print R unchanged. Applying the transformation L times instead of L-1 gives the next line.
- Trailing spaces or separatorsPrint the elements joined by single spaces with nothing after the last one; building the string with '%d ' in a loop leaves an extra space.
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.