Coding Solution

Conway Sequence – solution CodinGame en C

Moyenlook-and-sayrun-length encodinglistsMis à jour le
Réponse courte

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

  1. 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.
  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.
  3. 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.
  4. 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é

TempsO(total length)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome