4
\$\begingroup\$

The code works not only as a normal run length encoder and decoder, but it also works for values like 3ABC (Prints ABCABCABC), but the same doesn't happen for encoding

class DecodeError(BaseException):
    __module__ = Exception.__module__

class EncodeError(BaseException):
    __module__ = Exception.__module__

def run_length_encode(string: str) -> str:
    if any(not i.isalpha() for i in string):
        raise EncodeError('String must contain only alphabets')

    final_string = ''

    number = 1
    character = string[0]

    for i in string[1:]:
        if i != character:
            final_string += str(number) + character
            number = 0

        number += 1
        character = i

    final_string += str(number) + character

    return final_string

def run_length_decode(encoded_string: str) -> str:
    if not encoded_string:
        return ''

    if encoded_string[-1].isnumeric():
        raise DecodeError('Ending character must not be an integer')

    if not encoded_string[0].isnumeric():
        raise DecodeError('Starting character must be an integer')

    number = character = ''
    final_string = ''

    for c in encoded_string:
        if c.isnumeric():
            if character:
                final_string += int(number) * character
                number = character = ''

            number += c

            if number == '0':
                raise DecodeError('Number cannot start with 0')

        else:
            if not c.isalpha():
                raise DecodeError('String must contain only alphabets')

            character += c

    final_string += int(number) * character

    return final_string

if __name__ == '__main__':
    t = int(input('Enter if you want to encode(1) or decode(2): '))

    string = input('Enter string: ')

    if t == 1: print(run_length_encode(string))
    elif t == 2: print(run_length_decode(string))
    else: raise ValueError('Value must be 1 or 2')

Is it possible make this code shorter, neater, and faster?

A few testcases:

For encode:

Enter if you want to encode(1) or decode(2): 1
Enter string: AABBCCDD
2A2B2C2D
Enter if you want to encode(1) or decode(2): 1
Enter string: AB1
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 67, in <module>
    if t == 1: print(run_length_encode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 9, in run_length_encode
    raise EncodeError('String must contain only alphabets')
EncodeError: String must contain only alphabets
Enter if you want to encode(1) or decode(2): 1
Enter string: AAABBcCCddee
3A2B1c2C2d2e
Enter if you want to encode(1) or decode(2): 1
Enter string: AAABBCC.
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 67, in <module>
    if t == 1: print(run_length_encode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 9, in run_length_encode
    raise EncodeError('String must contain only alphabets')
EncodeError: String must contain only alphabets

For decode:

Enter if you want to encode(1) or decode(2): 2
Enter string: 2A3C4D
AACCCDDDD
Enter if you want to encode(1) or decode(2): 2
Enter string: 1ABC
ABC
Enter if you want to encode(1) or decode(2): 2
Enter string: 2A3B1ABC
AABBBABC
Enter if you want to encode(1) or decode(2): 2
Enter string: 0X
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 68, in <module>
    elif t == 2: print(run_length_decode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 50, in run_length_decode
    raise DecodeError('Number cannot start with 0')
DecodeError: Number cannot start with 0
Enter if you want to encode(1) or decode(2): 2
Enter string: 0123A
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 68, in <module>
    elif t == 2: print(run_length_decode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 50, in run_length_decode
    raise DecodeError('Number cannot start with 0')
DecodeError: Number cannot start with 0
Enter if you want to encode(1) or decode(2): 2
Enter string: 2A3#
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 68, in <module>
    elif t == 2: print(run_length_decode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 54, in run_length_decode
    raise DecodeError('String must contain only alphabets')
DecodeError: String must contain only alphabets
Enter if you want to encode(1) or decode(2): 2
Enter string: A2A
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 68, in <module>
    elif t == 2: print(run_length_decode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 36, in run_length_decode
    raise DecodeError('Starting character must be an integer')
DecodeError: Starting character must be an integer
Enter if you want to encode(1) or decode(2): 2
Enter string: 1A2
Traceback (most recent call last):
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 68, in <module>
    elif t == 2: print(run_length_decode(string))
  File "C:/Users/Administrator/.PyCharmCE2018.3/config/scratches/scratch_62.py", line 33, in run_length_decode
    raise DecodeError('Ending character must not be an integer')
DecodeError: Ending character must not be an integer

If you want more testcases, say so in the comments and I'll add them!

\$\endgroup\$
  • \$\begingroup\$ Consider the following actual test: run_length_decode("10abc2err3.0bbc") gives abcabcabcabcabcabcabcabcabcabcerrerr.... Is that expected? 1) sequence of chars 2) float numbers 3) 0 digit before a letter ? \$\endgroup\$ – RomanPerekhrest Nov 20 '19 at 9:27
  • \$\begingroup\$ abcabcabc... was expected, but the others were not. Thanks for pointing that out!. I'll edit my code soon \$\endgroup\$ – Srivaths Nov 20 '19 at 11:02
  • \$\begingroup\$ It would be helpful to describe the intended behavior, with examples of inputs and expected outputs. \$\endgroup\$ – Groger Nov 20 '19 at 12:40
  • \$\begingroup\$ @RomanPerekhrest Yes \$\endgroup\$ – Srivaths Nov 20 '19 at 13:32
5
\$\begingroup\$

Improvements and corrections:

run_length_encode function.
The responsibility is "encoding" the input string basing on counting consecutive characters (including repetitive characters) and returning the resulting string in format <count><char(s)>....
Instead of relying on a verbose and noisy for loop, re.sub function with regex backreferences and extended (but simple) substitution allow to succeed the job in just one line. (Add import re at top level)

The new version of run_length_encode function:

def run_length_encode(string: str) -> str:
    if not string.isalpha():
        raise EncodeError('Input string must contain only alphabetic chars')

    encoded = re.sub(r'(.)(\1+)?', 
                     lambda m: f"{len(m.group(2) or '') + 1}{m.group(1)}", string)
    return encoded

run_length_decode function.

  • encoded_string is shortened to encoded_str and stripped at the very start:

    encoded_str = encoded_str.strip()
    
  • if encoded_string[-1].isnumeric(). The DecodeError for this check is rephrased to get a more consistent description:

    if encoded_str[-1].isnumeric():
        raise DecodeError('Ending character must be an alphabetic char')
    
  • if not encoded_string[0].isnumeric(). The validation for starting char is extended to also cover prohibited 0 digit at the start of the input string:

    if not encoded_str[0].isnumeric() or encoded_str[0] == '0':
        raise DecodeError('Starting character must be an integer (except 0)')
    
  • the crucial for loop gets even worse with inner validations:

    if number == '0':
        raise DecodeError('Number cannot start with 0')
    

    and

    if not c.isalpha():
        raise DecodeError('String must contain only alphabets')
    

    The error message 'Number cannot start with 0' sounds too generic and is better expressed as 'Input string cannot contain letter(s) with zero counts'.
    Those 2 validations can be effectively moved out from the loop and run just once (powered by re.search check) before the main processing.

If sacrificing concrete descriptive error messages - all validations can be handled with a single regex pattern and collapsed, but that, of course, would require a more generic error message.

But finally, the entire loop is replaced with similar short regex magic based on pattern r'(\d+)(\D+)' and string multiplication:

    def run_length_decode(encoded_str: str) -> str:
        encoded_str = encoded_str.strip()
        if not encoded_str:
            return ''

        if encoded_str[-1].isnumeric():
            raise DecodeError('Ending character must be an alphabetic char')

        if not encoded_str[0].isnumeric() or encoded_str[0] == '0':
            raise DecodeError('Starting character must be an integer (except 0)')

        if re.search(r'[^\da-zA-Z]', encoded_str):
            raise DecodeError('Input string must contain only alphanumeric chars')

        if re.search(r'\D0', encoded_str):
            raise DecodeError('Input string cannot contain letter(s) with zero counts')

        decoded = re.sub(r'(\d+)(\D+)', 
                         lambda m: f"{m.group(2) * int(m.group(1))}", encoded_str)
        return decoded

Quick test of new versions:

print(run_length_encode('AABBCCDDDD'))   # "2A2B2C4D"
print(run_length_encode('aaaa3'))   # EncodeError "Input string must contain only alphabetic chars"
print(run_length_encode('AAABBcCCddee'))   # "3A2B1c2C2d2e"

print(run_length_decode("2A3#"))   # DecodeError "Input string must contain only alphanumeric chars"
print(run_length_decode("1a2N030c"))   # DecodeError "Input string cannot contain letter(s) with zero counts"
print(run_length_decode("1a2"))   # DecodeError "Ending character must be an alphabetic char"
print(run_length_decode("a23b"))   # DecodeError "Starting character must be an integer (except 0)"
print(run_length_decode("10abC2err10b3B"))  # "abCabCabCabCabCabCabCabCabCabCerrerrbbbbbbbbbbBBB"
print(run_length_decode("4abc1Arr3bbB"))   # "abcabcabcabcArrbbBbbBbbB"
\$\endgroup\$
1
\$\begingroup\$

In order to give an alternative to the excellent RegEx answer by @RomanPerekhrest, here is one using itertools.groupby. This way you can eliminate your manual for loops and counting for the run_length_encode function.

from itertools import groupby

def run_length_encode(s):
    """Returns a RLE string like this:
       'ABBCC' -> '1A2B3C'
    """
    if not s.isalpha():
        raise EncodeError('Input string must contain only alphabetic chars')

    return "".join(f"{len(list(g))}{c}" for c, g in groupby(s))

For the decoding I would also use a RegEx, but maybe using re.findall:

def run_length_decode(s):
    """Take a RLE from `run_length_encode` and decompress it:
       '1A2B3C' -> 'ABBCC'
    """
    return "".join(c * int(n) for n, c in re.findall(r'(\d)([a-zA-Z])', s))

Of course you would have to add all the sanity checks back again to this. Doing that will make it less neat and short. The current code will raise some exceptions (e.g. for the empty string), but skip malformed parts of the string (check out run_length_decode("a2b") -> "bb").

In addition, you should probably also document your functions, ideally using a docstring.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.