Conway Sequence – solution CodinGame en C
On part de la liste [R] et on applique L-1 fois l'étape « look-and-say » : on parcourt la liste courante, on regroupe les valeurs égales consécutives et on remplace chaque groupe par sa longueur suivie de la valeur. On travaille sur une liste d'entiers et non sur une chaîne de chiffres, car R peut avoir 2 ou 3 chiffres et doit être lu comme un seul élément. On affiche la liste finale séparée par des espaces simples ; chaque étape est linéaire en la taille de la ligne.
L'énoncé
La suite commence par un seul nombre R (de 1 à 100). Chaque ligne suivante décrit la précédente : on la lit de gauche à droite, et chaque plage de nombres identiques consécutifs devient deux nombres, le nombre d'occurrences puis la valeur elle-même. Ainsi 1 devient 1 1, puis 2 1, puis 1 2 1 1, et ainsi de suite.
Étant donnés R et un indice de ligne L (jusqu'à 25), il faut afficher la ligne L avec ses nombres séparés par des espaces. C'est la suite « look-and-say », avec la subtilité que les éléments sont des nombres entiers, pas des chiffres isolés.
La démarche, étape par étape
- Représenter une ligne par une liste d'entiersOn stocke [R] comme première ligne. Garder des entiers plutôt qu'une chaîne de chiffres garantit que 100 reste un seul élément et qu'un compte comme 12 n'est jamais découpé en 1 et 2.
- Encoder la ligne courante par plagesOn parcourt la liste en gardant la valeur courante et son nombre d'apparitions consécutives. Quand la valeur change, on ajoute le compte puis la valeur à la nouvelle liste et on remet le compteur à zéro.
- Vider la dernière plageAprès la boucle, le dernier groupe n'a pas encore été écrit. L'ajouter explicitement est la ligne que la plupart des gens oublient.
- Répéter L-1 fois et afficherLa ligne 1 est [R] lui-même, donc on applique l'étape L-1 fois. On joint avec des espaces simples sans espace final.
Complexité
O(total length)O(length of line L)Chaque étape est linéaire en la taille de la ligne courante. Les lignes look-and-say croissent d'environ 30 % par étape (constante de Conway ≈ 1,3036), donc la ligne 25 compte à peu près un millier d'éléments et l'exécution complète est instantanée.
Code de la solution
Conway Sequence – C
Garde chaque ligne sous forme de chaîne séparée par des espaces, la découpe avec strtok et atoi, puis réécrit la ligne suivante avec sprintf dans un tampon de 10 000 octets. Le tampon suffit pour L ≤ 25 (environ 1200 éléments d'au plus 4 caractères), mais une liste d'entiers serait plus simple.
#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;
}
Erreurs fréquentes
- Traiter la ligne comme une chaîne de chiffresAvec R = 100, la deuxième ligne doit être « 1 100 », pas « 1 1 2 0 ». Découper en caractères ne marche que pour les départs à un chiffre, ce que les tests suivants évitent justement.
- Oublier le dernier groupeL'émission se fait au changement de valeur, donc la dernière plage est encore en attente quand la boucle se termine. L'oublier raccourcit chaque ligne de deux nombres.
- Décalage d'une unité sur LL = 1 doit afficher R tel quel. Appliquer la transformation L fois au lieu de L-1 donne la ligne suivante.
- Espaces ou séparateurs en fin de ligneOn affiche les éléments joints par des espaces simples, sans rien après le dernier ; construire la chaîne avec '%d ' dans une boucle laisse un espace de trop.
Pour aller plus loin
Une propriété rarement mentionnée fournit un oracle de test gratuit : pour toute graine R de 2 à 100, R reste le tout dernier élément de chaque ligne et ne fusionne jamais avec rien, et tout ce qui le précède est identique quel que soit R. La ligne 6 est 1 1 1 3 1 2 2 1 1 suivie de R, pour R = 2 comme pour R = 100, et aucun nombre autre que R ne dépasse jamais 3. Seul R = 1 se comporte différemment, parce que la graine elle-même peut rejoindre les plages de 1 (on obtient le classique 1, 1 1, 2 1, 1 2 1 1, 1 1 1 2 2 1, 3 1 2 2 1 1). Donc si votre sortie pour R = 100 ne se termine pas par 100, ou si son préfixe diffère de votre sortie pour R = 2, vous avez un bug de parsing, presque toujours des nombres à plusieurs chiffres découpés en chiffres.
Questions fréquentes
La Conway Sequence est-elle la même chose que look-and-say ?
Oui, c'est le nom que John Conway a donné à la suite look-and-say. La version CodinGame autorise simplement une graine quelconque jusqu'à 100 et la traite comme un seul élément.
Quelle longueur atteint la ligne 25 ?
En partant de 1, la ligne 25 compte 1182 éléments. N'importe quelle liste dynamique ou un tampon de quelques kilo-octets suffit.
Peut-on résoudre le puzzle avec des expressions régulières ?
Dans les langages avec références arrière, un motif qui capture une valeur suivie de ses répétitions fonctionne, mais il doit capturer des nombres entiers séparés par des espaces, pas des caractères isolés, sinon les graines à plusieurs chiffres cassent tout.