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

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