Run-Length Encoding
Contest 4
Run-length encoding (RLE) is one of the simplest forms of data compression. It is used in image formats like BMP and TIFF to compress rows of pixels that repeat the same color. The idea is to replace consecutive runs of the same character with a count followed by the character.
For example, the string AAABBBCC encodes to 3A3B2C, and the string 3A3B2C decodes back to AAABBBCC.
You will implement either the encoder or decoder depending on the input.
ENCODE rules:
- Scan the input string left to right
- For each run of consecutive identical characters, output the count followed by the character
- Single characters still get a count: ABC encodes as 1A1B1C
DECODE rules:
- Read a number (may be more than one digit, e.g. ), then the character that follows
- Repeat that character the specified number of times
- Continue until the entire encoded string is consumed
After processing, output the result string AND a size summary showing the transformation.
Input:
- Line 1: ENCODE or DECODE
- Line 2: the string to process
Output:
- Line 1: the resulting string
- Line 2: "X -> Y" where X is the input length and Y is the output length
For example, the string AAABBBCC encodes to 3A3B2C, and the string 3A3B2C decodes back to AAABBBCC.
You will implement either the encoder or decoder depending on the input.
ENCODE rules:
- Scan the input string left to right
- For each run of consecutive identical characters, output the count followed by the character
- Single characters still get a count: ABC encodes as 1A1B1C
DECODE rules:
- Read a number (may be more than one digit, e.g. ), then the character that follows
- Repeat that character the specified number of times
- Continue until the entire encoded string is consumed
After processing, output the result string AND a size summary showing the transformation.
Input:
- Line 1: ENCODE or DECODE
- Line 2: the string to process
Output:
- Line 1: the resulting string
- Line 2: "X -> Y" where X is the input length and Y is the output length
Constraints
Input strings contain only uppercase letters (A-Z) for ENCODE. Encoded strings contain only digits and uppercase letters. All strings are to characters. Counts in encoded strings are between and .
Sample input
ENCODE AAABBCDDDDD
Sample output
3A2B1C5D 11 -> 8
Stdin