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

Question

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:

[Run Length] (https://www.coderbyte.com/solution/Run%20Length?tblang=german)

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()

• RomanPerekhrest: How it should behave (what result) on this input string aAabcaa ?
• Dave: @RomanPerekhrest I will make a revision to cover that possibility

Answer 1

• 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

• The pairwise function could be better described using the pairwise recipe.
• If you utilize itertools.groupby the challenge is super easy, as it makes slices for you.

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)
 )

• Dave: 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!
• Peilonrayz: @Dave Yeah 165 times slower seems a bit off, since mine are both in the margin of error. How did you test it?
• Dave: I added my test script to my post. Tell me what I've done wrong :)
• Peilonrayz: @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.
• Peilonrayz: @Dave Technically you got it right. It's just it didn't work in the way you expected with mutables.