Coding Solution

Chuck Norris – solution CodinGame en C

Facilebinary encodingrun-length encodingstring buildingbit manipulationMis à jour le
Réponse courte

On convertit chaque caractère en code ASCII sur 7 bits, on concatène tous les bits en une seule chaîne, puis on la découpe en séries de bits identiques. Chaque série donne deux blocs : « 0 » pour une série de 1 ou « 00 » pour une série de 0, suivi d'autant de zéros que la longueur de la série, le tout séparé par des espaces. Concaténer avant d'encoder est indispensable, car une série peut continuer d'un caractère au suivant.

L'énoncé

L'entrée est une seule ligne de caractères ASCII imprimables (moins de 100). Chaque caractère s'écrit en binaire sur exactement 7 bits, et la chaîne de bits obtenue est encodée uniquement avec des zéros et des espaces.

L'encodage porte sur les séries consécutives d'un même bit : le premier bloc indique le bit (« 0 » pour 1, « 00 » pour 0), le second est une suite de zéros dont la longueur est le nombre de bits de la série. Les blocs sont séparés par un espace. Par exemple, la lettre C (1000011) devient « 0 0 00 0000 0 00 ».

La démarche, étape par étape

  1. Coder chaque caractère sur 7 bitsOn prend le code ASCII de chaque caractère et on l'écrit en binaire, complété à gauche par des zéros jusqu'à 7 chiffres. Les conversions natives comme toBinaryString ou bin() suppriment les zéros de tête : le remplissage est obligatoire.
  2. Concaténer tous les bitsOn assemble les codes de 7 bits en une seule chaîne avant d'encoder quoi que ce soit. Encoder caractère par caractère donne un résultat faux dès qu'une série chevauche deux caractères.
  3. Parcourir les sériesOn parcourt la chaîne en retenant le bit précédent et la longueur de la série en cours. Quand le bit change, on ferme la série et on en ouvre une nouvelle.
  4. Écrire deux blocs par sériePour chaque série, on écrit « 0 » si elle est faite de 1 ou « 00 » si elle est faite de 0, un espace, puis autant de zéros que sa longueur. Un seul espace entre les séries, et ne pas oublier d'écrire la dernière série après la boucle.

Complexité

TempsO(7n)
MémoireO(7n)

Chacun des 7n bits est visité une fois, et la chaîne de bits comme la sortie grandissent linéairement avec le message. La version C de remplacement lit les bits directement par décalage et n'a besoin d'aucune chaîne intermédiaire.

Code de la solution

Chuck Norris – C

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

int main()
{
    char msg[256];
    if (!fgets(msg, sizeof msg, stdin))
        return 0;
    msg[strcspn(msg, "\r\n")] = '\0';

    int prev = -1; /* previous bit, -1 before the first one */
    for (int i = 0; msg[i]; i++) {
        for (int b = 6; b >= 0; b--) {
            int bit = (msg[i] >> b) & 1;
            if (bit != prev) {
                if (prev != -1)
                    printf(" ");
                printf(bit ? "0 " : "00 ");
                prev = bit;
            }
            printf("0");
        }
    }
    printf("\n");
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

Ce puzzle est un codage par plages (run-length encoding) déguisé : la chaîne de bits est compressée en couples (bit, longueur), et chaque couple est écrit en unaire. Vu ainsi, on peut faire plus simple que la plupart des solutions publiées : inutile de construire la chaîne binaire. On parcourt les caractères, on extrait les bits de 6 à 0 avec (c >> b) & 1, et on n'écrit un nouvel en-tête de bloc que lorsque le bit diffère du précédent ; sinon on ajoute juste un « 0 ». Les séries à cheval sur deux caractères sont gérées gratuitement, en mémoire constante. Un bon test qui piège les encodeurs caractère par caractère : « % » (0100101), dont la sortie attendue est « 00 0 0 0 00 00 0 0 00 0 0 0 ».

Questions fréquentes

Pourquoi 7 bits et pas 8 dans le puzzle Chuck Norris ?

L'énoncé utilise l'ASCII standard sur 7 bits : chaque caractère doit faire exactement 7 bits, complété par des zéros de tête si besoin.

Que signifie « 0 0 00 0000 0 00 » ?

C'est la lettre C (1000011) : un 1 (« 0 0 »), quatre 0 (« 00 0000 »), puis deux 1 (« 0 00 »).

Pourquoi mon code échoue-t-il sur les messages de plusieurs caractères ?

Vous encodez probablement chaque caractère séparément. Concaténez d'abord tous les codes de 7 bits, car une série de bits identiques peut se prolonger sur deux caractères.

Puzzles similaires

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