2
\$\begingroup\$

As part of my college class, I have to write a program that returns the "smallest" letter in the string. Input is assumed to be a non empty string. "Smallest" is defined as:

The smallest decimal value of the character, pertaining to this chart.

The range of acceptable values is 0 <= x <= 127

I would like to get feedback on the algorithm of the code. Other suggestions are accepted and welcome, but the main algorithm is the main focus.

def smallest_letter(string: str) -> str:
    """
    Returns the smallest letter in the string

    Input is restricted to ASCII characters in range 0 <= character <= 127

    :param string: A string containing only ASCII letters

    :return: A string length one of the smallest letter
    """

    # Ensure all characters are within the acceptable range #
    for character in string:
        assert ord(character) <= 127

    smallest_letter = 1000
    for letter in string:
        if ord(letter) < smallest_letter:
            smallest_letter = ord(letter)
    return chr(smallest_letter)

if __name__ == "__main__":

    # Test Cases #

    assert smallest_letter("abydsufaksjdf") == "a"
    assert smallest_letter("bfsufsjfbeywafbiu") == "a"
    assert smallest_letter("ABYUVGDuibfsafuofiw") == "A"
\$\endgroup\$
  • 2
    \$\begingroup\$ Is there a reason you don't simply use min("abydsufaksjdf")? \$\endgroup\$ – L. F. Nov 3 '19 at 7:28
  • \$\begingroup\$ There is a bug: what happens if you pass an empty string ("") to smallest_letter? \$\endgroup\$ – Jan Kuiken Nov 3 '19 at 9:09
  • \$\begingroup\$ @L.F. I was completely unaware that the min method could do those computations. I'll tag this as reinventing-the-wheel. \$\endgroup\$ – Linny Nov 3 '19 at 9:36
  • \$\begingroup\$ @JanKuiken This is assuming the input is a non empty string. I will update the question accordingly. \$\endgroup\$ – Linny Nov 3 '19 at 9:36
  • \$\begingroup\$ I updated my answer, if you want to take a look :) \$\endgroup\$ – AMC Nov 26 '19 at 0:00
3
\$\begingroup\$

I'll second what Gloweye said in this answer, namely that assert should not be used for control flow.


This solution combines many of the other answers:

def smallest_character(str_in: str) -> str:
    min_ord = 128
    for curr_char_ord in (ord(c) for c in str_in):
        if curr_char_ord > 127:
            raise ValueError(f'Character {chr(curr_char_ord)} in smallest_letter() arg has ord value {curr_char_ord} '
                             f'which is above the allowed maximum of 127')
        else:
            min_ord = min(min_ord, curr_char_ord)
    return chr(min_ord)

This solution uses min() and max():

def smallest_character(str_in: str) -> str:
    min_val = min(str_in)
    max_val = max(str_in)
    if ord(max_val) > 127:
        raise ValueError(
            f'Character {max_val} in smallest_letter() arg has ord value {ord(max_val)} which is above the allowed '
            f'maximum of 127')
    else:
        return min_val
\$\endgroup\$
3
\$\begingroup\$

Regarding min(string): Python exceeding your expectations. It happens a lot.

assert

All assert statements can be disabled with a switch to the interpreter, and sometimes are. Therefore, they're not suitable for flow control. I think you should replace:

for character in string:
    assert ord(character) <= 127

With:

for character in string:
    if ord(character) > 127:
        raise ValueError(f"Character {character} is out of range.")

or to optimize with a generator instead of the loop (requires Python 3.8+ if you want to report the character that violates the condition):

if any(ord(character := char) > 127 for char in string):
    raise ValueError(f"Character {character} out of range")

(Thanks to @Graipher for proper handling of the := token in 3.8+, which I hadn't worked with myself yet.)

That's all I can see being wrong here, though.

\$\endgroup\$
  • \$\begingroup\$ Me neither, took me a while to find an online interpreter, but TIO has it: tio.run/#python38pr \$\endgroup\$ – Graipher Nov 4 '19 at 16:03
  • 1
    \$\begingroup\$ Whoopsie. fixed. \$\endgroup\$ – Gloweye Nov 4 '19 at 17:58
2
\$\begingroup\$

Of course min("3sdsdf44ldfkTsdfnsnприветsdfa5É") (contains unicode chars) approach won't be suitable in case if validating/requiring only ASCII chars.

Issues of initial approach :

  • validating empty string. To ensure non-empty input string we'll add a simple assertion at start:
    assert string != "", "Empty string"
  • doubled traversals. On valid input strings like "3sdsdf44ldfkTe45456fghfgh678567sdfnsnsdfa23" where the char with minimal code would be at the end part of the string the former approach will make a double traversal though 2 for loops.
    To avoid that inefficiency we can combine validation and comparison/accumulation logic to be on a single iteration. (you may run time performance measurements to see the difference)

  • ord(letter). Duplicated calls can be eliminated through applying Extract variable technique: char_code = ord(char)


The final optimized version:

def smallest_letter(string: str) -> str:
    """
    Returns the smallest letter in the string
    Input is restricted to ASCII characters in range 0 <= character <= 127

    :param string: A string containing only ASCII letters
    :return: A string length one of the smallest letter
    """

    assert string != "", "Empty string"

    max_code, min_code = 128, 128

    for char in string:
        char_code = ord(char)
        assert char_code < max_code, f"{char} is not ASCII character"  # ensure the char is in acceptable code range
        if char_code < min_code:
            min_code = char_code

    return chr(min_code)
\$\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.