Chuck Norris – solution CodinGame en C
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
- 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.
- 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.
- 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.
- É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é
O(7n)O(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;
}
Chuck Norris – Java
Utilise Integer.toBinaryString() et complète à la main les zéros de tête manquants, avec un StringBuilder pour éviter des concaténations coûteuses.
import java.util.*;
import java.math.*;
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
String msg = in.nextLine();
StringBuilder binMsg = new StringBuilder("");
/* Converts the message into its binary code, char by char
(without forgetting 0s in the beginning like toBinaryString does)*/
for (char c : msg.toCharArray()) {
String binChar = Integer.toBinaryString(c);
for (int j = binChar.length(); j < 7 ;j++)
binMsg.append("0");
binMsg.append(binChar);
}
/* prev contains the last character of binMsg read : '0' or '1'
count cointains the number of consecutive identical characters */
char prev = '2';
int count = 0;
/* reads binMsg character by character, updating prev, count
and printing the solution bit by bit*/
for (char c : binMsg.toString().toCharArray()) {
if (c != prev) {
for (int j = 0 ; j < count ; j++)
System.out.print("0");
if (count != 0)
System.out.print(" ");
System.out.print((c == '0') ? "00 " : "0 ");
count = 1;
} else {
count++;
}
prev = c;
}
for (int j = 0 ; j < count ; j++)
System.out.print("0");
}
}
Chuck Norris – Python 3
Le format '{0:07b}' fait le remplissage en une fois, et la multiplication de chaînes ('0' * count) écrit les zéros de chaque série.
msg = input()
# First build ONE bit string for the whole message: runs of identical bits
# can cross character boundaries (e.g. "CC" -> 1000011 1000011, the 11 and 1 merge).
binMsg = []
for c in msg:
# converts c to a 7digit 0 left padded binary code
binMsg.append('{0:07b}'.format(ord(c)))
# reunites the list of string into one string and browses it, updating :
# - prev which contains the last character of binMsg read : '0' or '1'
# - count which countains the number of consecutive identical characters
# and printing the result gradually
prev, count = None, 0
for c in ''.join(binMsg):
if c != prev:
# A new run starts: flush the zeros of the previous run (if any),
# then open a new block, "0 " for a run of 1s or "00 " for a run of 0s.
print(('0' * count) + \
(' ' if count else '') + \
("00 " if c == '0' else "0 "), end='')
count = 1
else:
count+=1
prev = c
# Flush the zeros of the very last run, which the loop never closes.
print("0" * count, end="")
Erreurs fréquentes
- Encoder caractère par caractèreAvec « CC », les bits sont 1000011 1000011 : le 11 final du premier C et le 1 initial du second forment une seule série de trois 1. Encoder par caractère produit « 0 00 0 0 » au lieu de « 0 000 » à cet endroit et le test échoue.
- Oublier les zéros de têteLa plupart des caractères ont un code inférieur à 64, donc 6 chiffres binaires ou moins. Sans compléter à 7 bits, toutes les séries sont fausses dès le premier bloc.
- Utiliser 8 bits par caractèreLe puzzle utilise l'ASCII sur 7 bits. Compléter à 8 bits ajoute un 0 en tête de chaque caractère et modifie toutes les séries.
- Oublier la dernière série ou laisser un espace finalLa boucle ne ferme une série que lorsque le bit change : la dernière doit être écrite après la boucle. Vérifiez aussi qu'il y a exactement un espace entre les blocs et rien de plus à la fin.
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.