1
\$\begingroup\$

I'm solving exercise 2 from lecture 3 of Berkeley's CS 61A (2012):

Write a function min_element that returns the minimum element in a tuple.

def min_element(tup):
    """ Returns the minimum element in tup.
    >>> a = (1, 2, 3, 2, 1)
    >>> min_element(a)
    1
    """

I know that Python has a built-in min function, but at this point in the course, the only operations on tuples that we have studied are indexing [1] [-1], slicing [1:], and concatenation +, so my solution needs to restrict itself accordingly.

My solution:

def min_element(tup):
    """ Returns the minimum element in tup.
    >>> a = (1, 2, 3, 2, 1)
    >>> min_element(a)
    1
    """
    def find_min(tup, min):
        if not tup:
           return min
        else:
           min = tup[0] if tup[0] < min else min
           return min_element(tup[1:], min)
    if tup:
        return find_min(tup[1:], tup[0])

Can this solution be improved?

\$\endgroup\$
  • 1
    \$\begingroup\$ Is min(tup) allowed? \$\endgroup\$ – 200_success Apr 14 '15 at 5:26
  • \$\begingroup\$ you mean python provided min function? No. \$\endgroup\$ – overexchange Apr 14 '15 at 5:44
  • \$\begingroup\$ One supplementary, this doc says: "A sequence has an element corresponding to any non-negative integer index less than its length, starting at 0 for the first element.". But python allows tup[:-1]? \$\endgroup\$ – overexchange Apr 14 '15 at 6:42
  • 1
    \$\begingroup\$ Negative indexes just count backwards from the end, and can therefore be disregarded. tup[:-1] is shorthand for tup[:len(tup)-1]. \$\endgroup\$ – 200_success Apr 14 '15 at 6:45
  • \$\begingroup\$ @overexchange: I've rewritten the question so that it clearly explains why you have these constraints on your solution, where they come from, and that you know about the built-in min function. We can't read your mind, so you need to tell us these things in the question! \$\endgroup\$ – Gareth Rees Apr 14 '15 at 8:52
1
\$\begingroup\$

You can simplify the recursive version of your code by dropping elements until you are left with just one, and then comparing pairs sequential pairs:

def min_element_recur(tup):
    if len(tup) == 1:
        return tup[0]
    elif len(tup) >= 2:
        a = tup[0]
        b = min_element_recur(tup[1:])
        return a if a<b else b

If you have learned reduce and lambda expressions, you can implement the operation by reducing on the minimum of two elements (if you are using python 3, you need from functools import reduce). This is basically the same as Danny's approach.

def min_element_reduce(tup):
   return reduce(lambda x, y: x if x<y else y, (1,2,3,4,-1,5))

Finally, this is a bit too simple so it may not be allowed, but you can take the first elements of the sorted version of the tuple:

def min_element_sorted(tup):
   return sorted(tup)[0]

Danny's solution is probably the most straightforward, though.

\$\endgroup\$
  • \$\begingroup\$ It is straightforward, but I prefer this solution ): Can we categorise such recursive style? \$\endgroup\$ – overexchange Apr 16 '15 at 1:03
  • \$\begingroup\$ I don't know what you mean by "categorize". \$\endgroup\$ – TheBlackCat Apr 16 '15 at 7:00
3
\$\begingroup\$

Berkeley CS61A alum here. Your solution looks fine. Having sat through many a lecture where the prof would go through problems like this, I can pretty much guarantee this is the solution that would have been given:

def min_element(tup):
    min = tup[0]
    for element in tup[1:]:
        if element < min:
            min = element
    return min

So this solution might be considered by someone really pedantic to be a bit "better" than yours since it is less verbose and because, in general, recursion tends to be slower than iteration. Your solution works just fine though :)

\$\endgroup\$
2
\$\begingroup\$

If I pass the empty tuple to your function, what happens? The condition if tup: fails, so control reaches the end of the function. As it happens, reaching the end of a function is equivalent to return None, but it's a bad idea to rely on this (because it's not clear to the reader what happens in this case; also, it's deprecated in the Python style guide (PEP8)).

The result is the same as if the function succeeds and found that None is the minimum element of the tuple, as if you'd called min_element((None,)), so it could potentially lead to errors elsewhere in a program.

It would be better to raise an exception in this case. The built-in min raises ValueError:

>>> min(())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: min() arg is an empty sequence
\$\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.