3
\$\begingroup\$

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()
\$\endgroup\$
  • 1
    \$\begingroup\$ How it should behave (what result) on this input string aAabcaa ? \$\endgroup\$ – RomanPerekhrest Jan 28 at 15:06
  • \$\begingroup\$ @RomanPerekhrest I will make a revision to cover that possibility \$\endgroup\$ – Dave Jan 28 at 19:23
2
\$\begingroup\$
  • 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)
    )
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Dave Jan 28 at 19:21
  • 1
    \$\begingroup\$ @Dave Yeah 165 times slower seems a bit off, since mine are both in the margin of error. How did you test it? \$\endgroup\$ – Peilonrayz Jan 28 at 19:24
  • \$\begingroup\$ I added my test script to my post. Tell me what I've done wrong :) \$\endgroup\$ – Dave Jan 28 at 20:13
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jan 28 at 20:17
  • 1
    \$\begingroup\$ @Dave Technically you got it right. It's just it didn't work in the way you expected with mutables. \$\endgroup\$ – Peilonrayz Jan 28 at 20:29

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.