Coding Solution

Chuck Norris – CodinGame solution in C

Easybinary encodingrun-length encodingstring buildingbit manipulationUpdated
Short answer

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

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

TimeO(7n)
SpaceO(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;
}

Common mistakes

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome