# Simple run-length encoding decoder

For practice, I decided to write a run-length decoder. For example:

basic_run_length_decode("1A2B3C")
=> 'ABBCCC'

basic_run_length_decode("5A10Z10J")
=> 'AAAAAZZZZZZZZZZJJJJJJJJJJ'


It ended up getting long, but that's mostly because I wanted try incorporating the partition-by function from Clojure. It seemed like it would work nicely here, and it did. It required me to write that function though since Python doesn't seem to have anything equivalent. I also "stole" grouper from the "recipe" section of the itertools docs. Clojure has both of these functions as part of its standard library, so that's what I thought of while writing this.

Basically, it works by cutting the string into groups of digits and non-digits, pairing them into [digits, word] pairs, then parsing the digits and doing some string multiplication.

What I'd like commented on mainly:

• partition_by. I tried to see if there was a sane way of using something like takewhile + drop_while, but both of those functions consume an extra element after the predicate flips, which caused problems. I opted to just do manual iteration, but it's quite verbose.

• Anything else that I may be doing the hard way.

Note, it actually allows for multiple characters per number.

basic_run_length_decode("10AB10CD")
=> 'ABABABABABABABABABABCDCDCDCDCDCDCDCDCDCD'


I thought about raising an error, but decided to just allow it. This is apparently a type of possible encoding, and it cost me nothing to allow it.

from itertools import zip_longest
from typing import Callable, Any, Iterable, TypeVar, Generator, List

T = TypeVar("T")
# Emulating https://clojuredocs.org/clojure.core/partition-by
def _partition_by(f: Callable[[T], Any], iterable: Iterable[T]) -> Generator[List[T], None, None]:
"""Splits off a new chunk everytime f returns a new value.
list(partition_by(lambda n: n < 5, [1, 2, 3, 6, 3, 2, 1])) => [[1, 2, 3], [6], [3, 2, 1]]
"""
last_value = object()  # Dummy object that will never be equal to anything else
chunk = []

for x in iterable:
returned = f(x)

if returned == last_value:
chunk.append(x)

else:
if chunk:
yield chunk

chunk = [x]

last_value = returned

if chunk:
yield chunk

# Recipe from https://docs.python.org/3.8/library/itertools.html#itertools.takewhile
def _grouper(iterable, n, fillvalue=None):
"""Collect data into fixed-length chunks or blocks"""
args = [iter(iterable)] * n
return zip_longest(*args, fillvalue=fillvalue)

def _invalid_encoded_error(message: str) -> ValueError:
return ValueError(f"Invalid encoded string. {message}")

def basic_run_length_decode(encoded_string: str) -> str:
"""Decodes a string in the form of <number><chars><number><chars>. . .
basic_run_length_decode("1A2B3C") => 'ABBCCC'"""
if encoded_string and not encoded_string[0].isdigit():
raise _invalid_encoded_error("First character must be a number.")

chunks = _partition_by(lambda c: c.isdigit(), encoded_string)

acc = []
for raw_n, raw_word in _grouper(chunks, 2):
if not raw_word:
raise _invalid_encoded_error("Trailing numbers without character at end of encoded string.")

n = int("".join(raw_n))  # Should never throw as long as the very first char is a digit?
word = "".join(raw_word)

acc.append(n * word)

return "".join(acc)


The code looks good to me, it is well documented and I do not have much to say.

Suggestion for _partition_by

In:

    if returned == last_value:
chunk.append(x)
else:
if chunk:
yield chunk
chunk = [x]


I'd tried to write chunk = [x] as chunk = [] ; chunk.append(x). This allows some rewriting as you can extract the common line out of the if / else.

    if returned == last_value:
pass
else:
if chunk:
yield chunk
chunk = []
chunk.append(x)


Then revert condition

    if returned != last_value:
if chunk:
yield chunk
chunk = []
chunk.append(x)


Then group condition as there is nothing to do when chunk is already empty.

    if chunk and returned != last_value:
yield chunk
chunk = []
chunk.append(x)


There is nothing wrong with the way things were done, this is a pure personal preference.

The docstrings are slightly inconsistent as we have two different forms for the verb: with and without the final 's'. If that can be of any help, there are Docstring conventions for Python in PEP 257.

It suggests:

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

Short and flexible substitution for initial _partition_by function by using itertools.groupby magic (to generate/split a consecutive groups by predicate):

from typing import Callable, Any, Iterable, TypeVar, Generator, List
from itertools import groupby

T = TypeVar("T")

def _partition_by(f: Callable[[T], Any], iterable: Iterable[T]) -> Generator[List[T], None, None]:
"""Splits to consecutive chunks by predicate.
list(partition_by(lambda n: n < 5, [1, 2, 3, 6, 3, 2, 1])) => [[1, 2, 3], [6], [3, 2, 1]]
"""
for k, group in groupby(iterable, key=f):
yield list(group)


Use case:

lst = [1, 2, 3, 6, 3, 2, 1]
print(list(_partition_by(lambda n: n < 5, lst)))


The output:

[[1, 2, 3], [6], [3, 2, 1]]

• Thanks. I thought I tried groupby and it didn't do what I wanted. I think I misinterpreted it as returning a map instead of a list of pairs. Ya, looking at it now, it's basically partition_by. Nov 13 '19 at 16:52

## Type Hint

The return type -> Generator[List[T], None, None] is correct, but it is a little verbose. The documentation suggests a simpler way of documenting generators that just yield values, using Iterator[]

def _partition_by(...) -> Iterator[List[T]]:


The method _grouper() doesn't have a return type hint.

## The Hard Way

• Anything else that I may be doing the hard way.

Well, you are doing the whole thing The Hard Way™.

You are looking for occurrences of <number><chars> in a string. This sounds like a job for the regular expression module. The <number> pattern is simply (\d+), and the <chars> pattern would be characters which are not numbers, which can be expressed concisely as (\D+) ... using a capital letter indicates it is matching not-digit characters.

Since you wish to find successive occurrences of these, you would want to use re.findall, or perhaps re.finditer:

for m in re.finditer(r"(\d+)(\D+)", encoded_str)


Now, m.group(1) is the string containing <number> characters and m.group(2) is the string containing the <chars> character. At this point, we can turn the digits into an integer, multiply the character string by that value, and join successive values together into one large string:

def basic_run_length_decode(encoded_string: str) -> str:
"""
Decodes a string in the form of <number><chars><number><chars>. . .

>>> basic_run_length_decode("1A2B3C")
'ABBCCC'
>>> basic_run_length_decode("10AB10CD")
'ABABABABABABABABABABCDCDCDCDCDCDCDCDCDCD'
"""

return "".join(m.group(2) * int(m.group(1))
for m in re.finditer(r"(\d+)(\D+)", encoded_string))


Yup. Your function can be simplified to one line of code, with no helper functions. Re-adding error checking left as exercise. ;-)

## Doctest

I've changed the format of your """docstring""" slightly.

    basic_run_length_decode("1A2B3C") => 'ABBCCC'


which implies to the reader that when you execute basic_run_length_decode("1A2B3C"), it will return the value 'ABBCCC', I've replaced this with:

    >>> basic_run_length_decode("1A2B3C")
'ABBCCC'


which implies if you are at Python's REPL, and you type basic_run_length_decode("1A2B3C"), it will return the value 'ABBCCC', the representation of (ie, with quotes) which will be printed by the REPL.

Basically, exactly the same thing.

Except ...

The doctest module knows how to read docstrings for functions, and extract things that look like Python REPL commands (ie, appear after a >>> prompt), and will execute those commands and compare the actual result with the indicated result, and raise an error if they don't match. Built-in unit testing!

Let's test our code!

aneufeld$python3 -m doctest run_length_decode.py aneufeld$


Well, that was anticlimactic; nothing got printed. That's a good thing. It means the tests passed. We can add a -v to make the output more verbose:

aneufeld$python3 -m doctest -v run_length_decode.py Trying: basic_run_length_decode("1A2B3C") Expecting: 'ABBCCC' ok Trying: basic_run_length_decode("10AB10CD") Expecting: 'ABABABABABABABABABABCDCDCDCDCDCDCDCDCDCD' ok 1 items had no tests: run_length_decode 1 items passed all tests: 2 tests in run_length_decode.basic_run_length_decode 2 tests in 2 items. 2 passed and 0 failed. Test passed. aneufeld$

• Thanks. Honestly, I never learned regex 😬. I've tried several times, and I always just ended up frustrated. I can see how terse they can allow code to be though. Nov 13 '19 at 16:44
• Funny. I often find myself wanting to say the same thing about lambda functions, closures, and functional programming. I can see how they can allow non-string processing code to be be terse. 😝 Nov 13 '19 at 16:49