Chuck Norris – CodinGame solution in C
Convert every character to its 7-bit ASCII code, concatenate all the bits into one string, then split that string into runs of identical bits. Each run becomes two blocks: "0" for a run of 1s or "00" for a run of 0s, followed by as many zeros as the run length, all separated by spaces. Concatenating before encoding is essential because a run can continue from one character into the next.
The problem
The input is a single line of printable ASCII characters (fewer than 100). Each character is written in binary on exactly 7 bits, and the resulting bit string is encoded using only zeros and spaces.
The encoding works on consecutive runs of the same bit: the first block says which bit ("0" means 1, "00" means 0), the second block is a sequence of zeros whose length is the number of bits in the run. Blocks are separated by single spaces. For example, the letter C (1000011) becomes "0 0 00 0000 0 00".
Approach, step by step
- Encode each character on 7 bitsTake the ASCII code of each character and write it in binary, left-padded with zeros to exactly 7 digits. Built-in conversions such as toBinaryString or bin() drop leading zeros, so padding is mandatory.
- Concatenate all bitsJoin the 7-bit codes into one long string before encoding anything. Encoding each character separately produces wrong output whenever a run spans two characters.
- Walk through the runsScan the bit string while remembering the previous bit and the current run length. When the bit changes, close the current run and open a new one.
- Emit two blocks per runFor each run print "0" if it is made of 1s or "00" if it is made of 0s, a space, then as many zeros as its length. Separate runs with a single space and do not forget to output the final run after the loop.
Complexity
O(7n)O(7n)Each of the 7n bits is visited once, and the bit string plus the output grow linearly with the message. The C replacement below reads bits directly with shifts and needs no bit string at all.
Solution code
Bug fixed in this version: The C version stores the message in char msg[100] and then loops until it meets '\n'. A legal message can have 99 characters, so with the newline and terminator it needs 101 bytes: fgets stops before the newline and the loop runs past the end of the string into uninitialised memory. The same happens if the last input line has no trailing newline. It also passes &msg (a pointer to an array) to fgets. The replacement strips the line ending with strcspn and extracts bits with shifts, without any intermediate buffer.
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
Uses Integer.toBinaryString() and pads the missing leading zeros manually, with a StringBuilder to avoid quadratic string concatenation.
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
The format spec '{0:07b}' does the padding in one go, and string multiplication ('0' * count) prints the zeros of each run.
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="")
Common mistakes
- Encoding characters one by oneWith "CC" the bits are 1000011 1000011: the trailing 11 of the first C and the leading 1 of the second form a single run of three 1s. Encoding per character prints "0 00 0 0" instead of "0 000" there and fails the test.
- Missing leading zerosMost characters have codes below 64, so their binary form has only 6 digits or fewer. Without padding to 7 bits, every run is off and the output is wrong from the first block.
- Using 8 bits per characterThe puzzle uses 7-bit ASCII. Padding to 8 bits adds an extra leading 0 to every character and changes all the runs.
- Forgetting the last run or adding a trailing spaceThe loop only closes a run when the bit changes, so the final run must be flushed after the loop. Also make sure blocks are separated by exactly one space with nothing extra at the end.
Going further
This puzzle is run-length encoding in disguise: the bit string is compressed into (bit, length) pairs and each pair is written in unary. Seeing it that way suggests a simpler implementation than most published solutions: you do not need to build the binary string at all. Loop over the characters, extract bits from 6 down to 0 with (c >> b) & 1, and emit a new block header only when the bit differs from the previous one; otherwise just print one more "0". This handles cross-character runs for free and uses constant memory. A good test that breaks per-character encoders is "%" (0100101), whose expected output is "00 0 0 0 00 00 0 0 00 0 0 0".
FAQ
Why 7 bits and not 8 in the Chuck Norris puzzle?
The statement uses standard 7-bit ASCII, so every character must be written on exactly 7 bits, padded with leading zeros if needed.
What does "0 0 00 0000 0 00" mean?
It is the letter C (1000011): one 1 ("0 0"), four 0s ("00 0000"), then two 1s ("0 00").
Why does my output fail on messages with several characters?
You are probably encoding each character separately. Concatenate all 7-bit codes first, because a run of identical bits can continue across two characters.