# Run length encoding of an input string (Coderbyte 'Run Length' challenge)

I'd like feedback on my solution to the outlined (medium level) programming challenge. What might be a more efficient or Pythonic solution?

The challenge as outlined by Coderbyte:

Have the function RunLength(str) take the str parameter being passed and return a compressed version of the string using the Run-length encoding algorithm. This algorithm works by taking the occurrence of each repeating character and outputting that number along with a single character of the repeating sequence. For example: "wwwggopp" would return 3w2g1o2p. The string will not contain any numbers, punctuation, or symbols.

import doctest
import logging
import timeit

logging.basicConfig(
level=logging.DEBUG,
format="%(asctime)s - %(levelname)s - %(message)s")
# logging.disable(logging.CRITICAL)

def compress_string(s: str) -> str:
"""
Indicate the freq of each char in s, removing repeated, consecutive chars

E.g. "aaabbc" outputs '3a2b1c'

:param s: the string to compress
:type s: str
:return: s as a compressed string
:rtype: str

>>> compress_string(s="wwwggopp")
'3w2g1o2p'
>>> compress_string(s="aaa")
'3a'
>>> compress_string(s="")
''
>>> compress_string(s="b")
'1b'
>>> compress_string(s="abcd")
'1a1b1c1d'
"""
if s == "":
return ""

# indexes of change in characters
indexes = [i+1 for i in range(len(s) - 1) if s[i+1] != s[i]]

# add start and end index for slicing of s
indexes.insert(0, 0)
indexes.append(len(s))

# slice string
slices = [s[indexes[i]:indexes[i+1]] for i in range(len(indexes)-1)]

compressed_str = "".join(f"{len(s)}{s[0]}" for s in slices)

return compressed_str

if __name__ == "__main__":
print(timeit.timeit("compress_string(s='wwwggoppg')",
setup="from __main__ import compress_string",
number=100000))
doctest.testmod()

• How it should behave (what result) on this input string aAabcaa ? Jan 28, 2020 at 15:06
• @RomanPerekhrest I will make a revision to cover that possibility
– Dave
Jan 28, 2020 at 19:23

## 1 Answer

• You could just make a new list rather than use list.insert and list.append.

indexes.insert(0, 0)
indexes.append(len(s))

indexes = [0] + indexes + [len(s)]

• For your "slice string" part, I'd make a function called pairwise. As this is a rather well know recipe in Python.

def pairwise(iterable):
return (
(iterable[i], iterable[i+1])
for i in range(len(iterable) - 1)
)

• You could combine slices and compressed_str into one comprehension. If you do you don't need to use len as indexes[i+1] - indexes[i] is the length of the string.

return "".join(
f"{b - a}{s[a]}"
for a, b in pairwise(indexes)
)

def pairwise(iterable):
return (
(iterable[i], iterable[i+1])
for i in range(len(iterable) - 1)
)

def compress_string(s: str) -> str:
if s == "":
return ""

indexes = [
i+1
for i in range(len(s) - 1)
if s[i+1] != s[i]
]
indexes = [0] + indexes + [len(s)]
return "".join(
f"{b - a}{s[a]}"
for a, b in pairwise(indexes)
)


# Itertools

def compress_string(s: str) -> str:
if s == "":
return ""
return "".join(
f"{sum(1 for _ in g)}{k}"
for k, g in itertools.groupby(s)
)

• To my absolute horror, I timed indexes = '[0] + indexes + [len(s)]' vs my method, and the latter was 165 times slower! If someone could explain why? I originally had used @Peilonrayz's version, but changed it!
– Dave
Jan 28, 2020 at 19:21
• @Dave Yeah 165 times slower seems a bit off, since mine are both in the margin of error. How did you test it? Jan 28, 2020 at 19:24
• I added my test script to my post. Tell me what I've done wrong :)
– Dave
Jan 28, 2020 at 20:13
• @Dave l.insert and l.append run 100000 times, making l in the last test 200000 times larger than at the beginning. You're no longer comparing the same thing. Just remove setup. Jan 28, 2020 at 20:17
• @Dave Technically you got it right. It's just it didn't work in the way you expected with mutables. Jan 28, 2020 at 20:29