10
\$\begingroup\$

I'd like feedback on my solution to the outlined programming challenge (medium level). I've tried it fast in any way I know how to, but, what might be a more efficient and/or pythonic solution?

[Caesar Cipher] Using the Python language, have the function CaesarCipher(str,num) take the str parameter and perform a Caesar Cipher shift on it using the num parameter as the shifting number. A Caesar Cipher works by shifting each letter in the string N places down in the alphabet (in this case N will be num). Punctuation, spaces, and capitalization should remain intact. For example if the string is "Caesar Cipher" and num is 2 the output should be "Ecguct Ekrjgt".

import doctest
import logging
import timeit

from string import ascii_lowercase, ascii_uppercase

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

ALPHABET_LENGTH = 26
# Wrap alphabet letters
LOWERCASE = ascii_lowercase + ascii_lowercase
UPPERCASE = ascii_uppercase + ascii_uppercase

def encode_string(s: str, n: int) -> str:
    """Perform a Caesar Cipher shift on s leaving punctuation, spaces intact

    :param s: the str on which to perform a Cipher shift
    :type s: str
    :param n: the number of places in the alphabet to shift the letter. 
              Positive for a forward shift, negative for a backwards shift
    :type n: int
    >>> encode_string(s="Caesar Cipher", n=2)
    'Ecguct Ekrjgt'
    >>> encode_string(s="Caesar Cipher", n=54)
    'Ecguct Ekrjgt'
    >>> encode_string(s="Aa Bb", n=0)
    'Aa Bb'
    >>> encode_string(s="Cc Dd", n=-28)
    'Aa Bb'
    """
    if n ==0:
        return s

    # Incase of very large n, find lowest equivalent offset
    n = n % ALPHABET_LENGTH

    # value of n used to index constants, equivalent to -n steps in backwards direction 
    if n < 0:
        n = ALPHABET_LENGTH - n

    new_str = ""

    for c in s:
        if c in LOWERCASE:
            i = LOWERCASE.index(c)
            encoded_char = LOWERCASE[i + n]
            new_str = new_str + encoded_char
        elif c in UPPERCASE:
            i = UPPERCASE.index(c)
            encoded_char = UPPERCASE[i + n]
            new_str = new_str + encoded_char
        else:
            new_str = new_str + c

    return new_str


if __name__ == "__main__":
    doctest.testmod()
    print(timeit.timeit(
        "encode_string(s='Caesar Cipher', n=2)",
        setup="from __main__ import encode_string, ALPHABET_LENGTH, LOWERCASE, UPPERCASE",
        number=100000)
    )
\$\endgroup\$
10
\$\begingroup\$

Magic number

ALPHABET_LENGTH = 26

You don't need to hard-code ALPHABET_LENGTH = 26 in your program. Let Python do the work for you, with ALPHABET_LENGTH = len(ascii_lowercase)


Avoid String concatenation; use built-in functions

String concatenation is very slow.

new_str = new_str + encoded_char

AlexV's append / join isn't much better.

Python comes with a str.translate, function which will do a letter-for-letter substitution in a string, which is exactly what you want to do. As a built-in, it is blazingly fast compared to processing each letter individually:

>>> help(str.translate)
Help on method_descriptor:

translate(self, table, /)
    Replace each character in the string using the given translation table.

      table
        Translation table, which must be a mapping of Unicode ordinals to
        Unicode ordinals, strings, or None.

    The table must implement lookup/indexing via __getitem__, for instance a
    dictionary or list.  If this operation raises LookupError, the character is
    left untouched.  Characters mapped to None are deleted.

It has a str.maketrans function for creation of the translation table:

>>> help(str.maketrans)
Help on built-in function maketrans:

maketrans(x, y=None, z=None, /)
    Return a translation table usable for str.translate().

    If there is only one argument, it must be a dictionary mapping Unicode
    ordinals (integers) or characters to Unicode ordinals, strings or None.
    Character keys will be then converted to ordinals.
    If there are two arguments, they must be strings of equal length, and
    in the resulting dictionary, each character in x will be mapped to the
    character at the same position in y. If there is a third argument, it
    must be a string, whose characters will be mapped to None in the result.

Using these functions, you can easily construct a Caesar cipher encoder-decoder:

from string import ascii_lowercase, ascii_uppercase

def caesar_cipher(shift: int):
    shift %= len(ascii_lowercase)
    return str.maketrans(ascii_lowercase + ascii_uppercase,
                         ascii_lowercase[shift:] + ascii_lowercase[:shift] +
                         ascii_uppercase[shift:] + ascii_uppercase[:shift])

def encode_string(s: str, n: int) -> str:
    """Your docstring here"""

    cipher = caesar_cipher(n)
    return s.translate(cipher)

The real speed will come from not creating a new translation table on each call.

if __name__ == "__main__":
    import doctest, timeit

    doctest.testmod()

    print(timeit.timeit(
        "'Caesar Cipher'.translate(cipher)",
        setup="from __main__ import caesar_cipher; cipher = caesar_cipher(2)",
        number=100000)
    )

Net: 10 times faster

\$\endgroup\$
11
\$\begingroup\$

Generally speaking your code looks quite good from my point of view. It's nicely structured, readable and documented. Well done!

Using LOWERCASE = ascii_lowercase + ascii_lowercase in conjunction with n = n % ALPHABET_LENGTH also seems to be a very clever way to implement the shift.

You don't need

if n < 0:
    n = ALPHABET_LENGTH - n

because modulo will handle negative numbers in the same way naturally.

Using LOWERCASE.index(...) to find the position of the letter in the alphabet could be optimized by using some kind of look-up table like so:

LOWERCASE_LUT = {letter: i for i, letter in enumerate(ascii_lowercase)}
UPPERCASE_LUT = {letter: i for i, letter in enumerate(ascii_uppercase)}

Also appending to a string with + in Python is wasteful, because strings are immutable, so each time this is done, a new string will be created. What you'll often find instead is to collect the string parts in a list which is then joined at the end.

All of this leads to the following code:

def encode_string_cr(s: str, n: int) -> str:
    """Perform a Caesar Cipher shift on s leaving punctuation, spaces intact

    :param s: the str on which to perform a Cipher shift
    :type s: str
    :param n: the number of places in the alphabet to shift the letter. 
              Positive for a forward shift, negative for a backwards shift
    :type n: int
    >>> encode_string(s="Caesar Cipher", n=2)
    'Ecguct Ekrjgt'
    >>> encode_string(s="Caesar Cipher", n=54)
    'Ecguct Ekrjgt'
    >>> encode_string(s="Aa Bb", n=0)
    'Aa Bb'
    >>> encode_string(s="Cc Dd", n=-28)
    'Aa Bb'
    """
    if n == 0:
        return s

    n %= ALPHABET_LENGTH

    chars = []    
    for c in s:
        if c in ascii_lowercase:
            i = LOWERCASE_LUT[c]
            encoded_char = LOWERCASE[i + n]
        elif c in ascii_uppercase:
            i = UPPERCASE_LUT[c]
            encoded_char = UPPERCASE[i + n]
        else:
            encoded_char = c
        chars.append(encoded_char)

    return "".join(chars)

This is roughly 1,5x faster than the original code, at the cost of a little bit more memory for those look-up tables.

\$\endgroup\$

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.