Articles – Page 46 – The Renegade Coder

As much fun as creating our own upper() function was, I figured it would be fun to try something a bit more challenging. Specifically, we're going to try replicating the minimum function today. Problem Description Today, I figured we could try to replicate another common Python function: min(). If you're not familiar with this function, here's what the docs say: Return the smallest item in an iterable or the smallest of two or more arguments. If one positional argument is provided, it should be an iterable. The smallest item in the iterable is returned. If two or more positional arguments are provided, the smallest of the positional arguments is returned. There are two optional keyword-only arguments. The key argument specifies a one-argument ordering function like that used for list.sort(). The default argument specifies an object to return if the provided iterable is empty. If the iterable is empty and default is not provided, a ValueError is raised. If multiple items are minimal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc)[0] and heapq.nsmallest(1, iterable, key=keyfunc). Source: Python Documentation While last time we tried reducing the complexity of the problem a bit, I think this time around we should try to replicate the full extent of the behavior. In other words, not only should we be able to handle iterables, but we should also be able to handle variable length arguments. Likewise, we should try to support the two keyword arguments. Thought Process Like last time, the first thing I usually do is think about inputs and outputs. In this case, we can accept a few different types of inputs. Meanwhile, output is relatively stable: Input: Required: an iterable OR a variable length argument Optional: a one-argument ordering function, a default value Output: the smallest value among the values provided In languages like Java, we might want to approach this problem from a method overloading standpoint. In other words, we could make two methods: one for iterables and one for variable length arguments. Unfortunately in Python, we don't have that luxury. That said, we do have the luxury of type flexibility. And as it turns out, variable length arguments are actually iterables. As a result, we don't have to make any special considerations. Instead, here's what I'm thinking for our Python function header (feel free to put this in a file called roll_your_own.py): def minimum(*args, **kwargs): pass From there, here's what I imagine are the steps to solving this problem: Check if input is an iterable: True: Check if iterable is empty True: Check if default keyword argument exists: True: Return default key False: Raise ValueError Check if key keyword argument exists: True: use key keyword argument to return smallest value False: use natural ordering to return smallest value The main steps are divided into two parts: First (i.e. step 1), we want to determine if we're working with an iterable, so we can check if it's empty. If it isn't, we can go ahead and treat the iterable like variable length arguments. Otherwise, we need to determine if a default value is available to return. If so, we return it. Otherwise, we throw an error. Second (i.e. step 2), we perform our minimum operation. There are basically two ways this goes down. Either we have an ordering function, or we don't. The rest of the time will be spent finding the smallest value. Fortunately, a minimum algorithm is fairly straightforward: Assume the first value in the iterable is the minimum value Check each subsequent value against the current minimum and replace as necessary Return the smallest value after iterating over the entire iterable At the very least, this will serve as our framework. Once we get some testing going, we can modify this algorithm as needed. Testing Given the complexity of this function, there are a lot of things we should probably test. That said, to keep things simple, we'll stick to our "first, middle, last, zero, one, many routine." Here's what that looks like for the minimum function: First: smallest value in iterable is the first value Middle: smallest value in iterable is a middle value Last: smallest value in iterable is the last value Zero: iterable is empty One: iterable has one element in it Many: iterable has many smallest elements in it For each of these test cases, we probably want to duplicate them for multiple types of input. For example, remember that the minimum function supports both iterables and variable length arguments. In addition, we have a couple keywords we can support. Unfortunately, this results in a fairly large set of tests for a single function. To keep things simple, we'll use the same framework above, but we may test multiple input types per test function. Here's what that looks like: import unittest import importlib roll_your_own = importlib.import_module("roll_your_own") class TestMinumum(unittest.TestCase): def test_minimum_first(self): test_set = [1, 2, 3, 4] test_key = lambda x: -x expected = 1 expected_rev = 4 self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key") def test_minimum_middle(self): test_set = [3, 2, 1, 4] test_key = lambda x: -x expected = 1 expected_rev = 4 self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key") def test_minimum_last(self): test_set = [4, 2, 3, 1] test_key = lambda x: -x expected = 1 expected_rev = 4 self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key") def test_minimum_zero(self): test_set = [] default = 1 self.assertRaises(ValueError, roll_your_own.minimum, test_set) self.assertEqual(roll_your_own.minimum(test_set, default=default), default, f"Failed to find smallest value {default} in {test_set} based on default") def test_minimum_one(self): test_set = [1] test_key = lambda x: -x expected = 1 expected_rev = 1 self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key") def test_minimum_many(self): test_set = [1, 2, 1, 4] test_key = lambda x: -x expected = 1 expected_rev = 4 self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}") self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key") if __name__ == '__main__': unittest.main() Generally, I think these tests cover most of our bases. Feel free to modify the set above for your own needs. Otherwise, let's get to coding! Solution Once again, here's the function header we're working with: def minimum(*args, **kwargs): pass Assuming the tests are in good shape, we should see something like the following during execution: FFFFFF ====================================================================== FAIL: test_minimum_first (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 13, in test_minimum_first self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 3, 4] ====================================================================== FAIL: test_minimum_last (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 31, in test_minimum_last self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [4, 2, 3, 1] ====================================================================== FAIL: test_minimum_many (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 54, in test_minimum_many self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 1, 4] ====================================================================== FAIL: test_minimum_middle (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 22, in test_minimum_middle self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [3, 2, 1, 4] ====================================================================== FAIL: test_minimum_one (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 46, in test_minimum_one self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1] ====================================================================== FAIL: test_minimum_zero (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 38, in test_minimum_zero self.assertRaises(ValueError, roll_your_own.minimum, test_set) AssertionError: ValueError not raised by minimum ---------------------------------------------------------------------- Ran 6 tests in 0.073s FAILED (failures=6) Now, let's go ahead and try to implement our algorithm. Check If Input Is An Iterable The very first thing we need to do is find a way to implicitly support function overloading. To do that, we need to check how many inputs the user has provided. This will tell us if we're working with an iterable or not: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable pass If the user provides exactly one argument, we know we're working with an iterable. According to our algorithm, we'll then want to check if it's empty. Check If Iterable Is Empty Now, this is a part where I sort of get stuck because checking if an iterable is empty is usually pretty straightforward. In fact, Python docs usually recommend using type flexibility as follows: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable if not args[0]: # must be empty However, there's a bit of a catch here. See, just because we know there's only one argument, doesn't mean we're actually dealing with an iterable. As a result, I think a possible workaround is to use the len() function again: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable if len(args[0]) == 0: # must be empty The idea here being that len() will crash if the value provided is not an iterable: >>> len(0) Traceback (most recent call last): File " ", line 1, in len(0) TypeError: object of type 'int' has no len() >>> Now, this error message is slightly different from the one provided by the built-in min() function: >>> min(0) Traceback (most recent call last): File " ", line 1, in min(0) TypeError: 'int' object is not iterable So, what we can do is catch the TypeError, and change it's error message: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable try: if len(args[0]) == 0: # must be empty pass except TypeError: raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None Regardless, I think either solution is fine as folks entering anything but iterables would be breaking the contract. Anyway, let's move on! Check If Default Keyword Argument Exists Given what we have so far, checking if the default keyword exists is pretty straightforward: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable try: if len(args[0]) == 0: # must be empty if "default" in kwargs: pass except TypeError: raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None Since we're here, we might as well return the default value: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable try: if len(args[0]) == 0: # must be empty if "default" in kwargs: return kwargs.get("default") except TypeError: raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None And, it should be pretty straightforward to raise the ValueError as well: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable try: if len(args[0]) == 0: # must be empty if "default" in kwargs: return kwargs.get("default") else: raise ValueError("min() arg is an empty sequence") except TypeError: raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None If all is well, we should start passing at least one of the tests: FFFFF. ====================================================================== FAIL: test_minimum_first (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 13, in test_minimum_first self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 3, 4] ====================================================================== FAIL: test_minimum_last (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 31, in test_minimum_last self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [4, 2, 3, 1] ====================================================================== FAIL: test_minimum_many (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 54, in test_minimum_many self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 1, 4] ====================================================================== FAIL: test_minimum_middle (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 22, in test_minimum_middle self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [3, 2, 1, 4] ====================================================================== FAIL: test_minimum_one (__main__.TestMinumum) ---------------------------------------------------------------------- Traceback (most recent call last): File "C:\Users\jerem\Downloads\test.py", line 46, in test_minimum_one self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}") AssertionError: None != 1 : Failed to find smallest value 1 in [1] ---------------------------------------------------------------------- Ran 6 tests in 0.013s FAILED (failures=5) Looks like test_minimum_zero is passing! Let's keep going. Check If Key Keyword Argument Exists With all the iterable checking out of the way, we can start talking about how we'll go about finding the minimum value. To do that, however, we'll need to know if we have a key function or not. Fortunately, we've already performed this check once, so we could do it again. However, I have a better idea. Ultimately, the purpose of the key function is to apply it to each value in the iterable to get a new value that we'll use for comparisons. This is kind of annoying because we have a scenario where we apply a function and a scenario where we don't. Of course, if we had a function that did nothing, we could reduce the logic to always apply a function. One way to can do this is by making use of the same get() function for dictionaries as before. The difference this time is that we can use the default argument to pass a nothing function. Take a look: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable try: if len(args[0]) == 0: # must be empty if "default" in kwargs: return kwargs.get("default") else: raise ValueError("min() arg is an empty sequence") except TypeError: raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None key = kwargs.get("key", lambda x: x) If the user does not provide a key function, then we use a function that returns whatever value it's fed. All that's left now is to compute the minimum value in our iterable. Compute the Minimum Value Computing the minimum is a pretty straightforward task, but we need to perform a little cleanup first. In particular, we need to make sure that args are an iterable regardless of the type of input. To do that, we can reassign args as soon as we know we're working with an iterable: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable args = args[0] try: if len(args) == 0: # must be empty if "default" in kwargs: return kwargs.get("default") else: raise ValueError("min() arg is an empty sequence") except TypeError: raise TypeError(f"'{type(args).__name__}' object is not iterable") from None key = kwargs.get("key", lambda x: x) Now, it's a matter of iterating over this iterable, applying a function, and returning the result when we're done: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable args = args[0] try: if len(args) == 0: # must be empty if "default" in kwargs: return kwargs.get("default") else: raise ValueError("min() arg is an empty sequence") except TypeError: raise TypeError(f"'{type(args).__name__}' object is not iterable") from None key = kwargs.get("key", lambda x: x) iterator = iter(args) smallest = next(iterator) while True: try: test = next(iterator) if key(test) < key(smallest): smallest = test except StopIteration: break return smallest And when we run this, we get exactly what we're expecting: ...... ---------------------------------------------------------------------- Ran 6 tests in 0.014s OK How cool is that? That said, there's some work I'd like to do to clean this up. Revising Solution One of the reasons I write these articles is to show that I don't know everything and that development is a process. By the time I got to the minimum computation part of the solution, I realized we had a problem: how do we get the the first value of any iterable? Not all iterables are indexable, so what do you do? That's when I discovered the iter() function which we ended up using in our solution. It's essentially how for loops work under the hood, but I found it useful for pulling out the initial value first. Of course, the cool thing about iter() is that we can use it in place of len() to determine if we have an iterable. As a result, we can remove the nasty try/except from the iterable portion of the code: def minimum(*args, **kwargs): if len(args) == 1: # must be an iterable args = args[0] iterator = iter(args) # will crash if not iterable if not args: if "default" in kwargs: return kwargs.get("default") else: raise ValueError("min() arg is an empty sequence") key = kwargs.get("key", lambda x: x) iterator = iter(args) smallest = next(iterator) while True: try: test = next(iterator) if key(test) < key(smallest): smallest = test except StopIteration: break return smallest But even then, the code isn't very pretty. At this point, I'm not sure how we could improve this beyond cleaning things up a bit with separate functions. That said, I did try looking into the source code to see how Python implemented min(). Turns out that it's written in C! And, it's not pretty: static PyObject * builtin_min(PyObject *self, PyObject *args, PyObject *kwds) { return min_max(args, kwds, Py_LT); } Naturally, this points to a generic min_max() function which is over 100 lines long. I'll spare you the specifics, but you can take a peek using this GitHub permalink. Let's just say there's quite a bit of nesting. Anyway, that's about all the time I'm willing to pour into this for today. If you're not interested in writing your own function but still want to help the site out, consider checking out our list of ways to grow the site. Right now, you can head over there to gain access to our Discord. Likewise, here are a few related posts: How to Capitalize a String in Python: Upper(), Capitalize(), And More What’s the Difference Between Arrays and Lists in Python? Python 3.9 Features That Will Make Your Life Easier In addition, here are a few resources from the folks at Amazon (#ad): Otherwise, thanks again for sticking around. I appreciate the support!