CODEWITHSUNDEEP
pythonpython-3.xlistrecursion
akela771
akela771

Reputation: 41

Recursively finding minimum value (no built-ins or loops)

Below is my code for finding the minimum integer in a nested list. It throws this error: 

TypeError: '<' not supported between instances of 'int' and 'list'

And I know why, but cannot figure out how to solve it. I am not able to use loops or built-in functions besides len, int, str, and append.

def min(nest):
    compareNum = nest[0]

    if len(nest) == 1:         
        return nest[0]      

    if compareNum < min(nest[1:]):         
       return compareNum     

    else:         
        return min(nest[1:])

Thanks in advance!

Upvotes: 1

Views: 325

Answers (3)

pjs
pjs

Reputation: 19855

If you're restricted to just len, int, str, and append, the following seems to work for me. It even handles empty lists.

def is_a_list(input):
    return str(input)[0] == '['

def nested_min(input):
    # if type(input) is list:
    if is_a_list(input):
        length = len(input)
        if length == 0:
            return None
        if length == 1:
            return nested_min(input[0])
        else:
            mid = length // 2
            first = nested_min(input[:mid])
            second = nested_min(input[mid:])
            if first is None:
                return second
            elif second is None:
                return first
            return first if first < second else second
    else:
        return input

If you're allowed to use type(), use the commented line instead of the uncommented version which uses is_a_list(), and remove that helper function.

I'm not a big fan of whittling recursive calls down one-by-one. Instead, this solution splits lists and sublists in half at each iteration, so it should be able to handle very large inputs. Consider the following test case:

from random import randint

rnd_list = [randint(10, 1000000) for _ in range(100000)]
# use builtin min to confirm answer
print("rnd_list minimum is " + str(min(rnd_list)))          
test_list = [42, 17, [99, 100], [rnd_list], [], 10000]
print("nested minimum is " + str(nested_min(test_list)))

This produces output such as:

rnd_list minimum is 22
nested minimum is 17

or

rnd_list minimum is 12
nested minimum is 12

but exceeds the maximum recursion depth when used with other proposed solutions.

Upvotes: 1

cdlane
cdlane

Reputation: 41872

not able to use loops or built-in functions besides len, int, str, and append

No loops, len(), int(), nor.append(). Just str():

def nested_minimum(array):
    if not array:
        return None

    first, *rest = array

    if '[' in str(first):
        first = nested_minimum(first)

    second = nested_minimum(rest)

    return [first, second][first is None or second is not None and second < first]

TEST

nested_list = [[-1523, 2], 3, -2, [2], [-23, 4], [-2234], 2, -1000]  # a la @AndrewGrass
print(nested_minimum(nested_list))

print(nested_minimum([[1, 2, 3], 5, 6, 7, [8, 6, 4]]))

print(nested_minimum([[], 1]))

TEST OUTPUT

> python3 test.py
-2234
1
1
>

Upvotes: 0

Andrew Grass
Andrew Grass

Reputation: 252

Alright, so you're probably going to have to use some try/except blocks for this one then if you can't use built-ins. It's throwing an error because you are trying to treat a nested list element as an integer, so let's make our try/except handle that Type Error:

def min(nest):
    # make sure your first element isn't a list
    try:
        compareNum = int(nest[0])
    except TypeError:
        compareNum = min(nest[0])

    if len(nest) == 1:
        return nest[0]

    try:
        if compareNum < min(nest[1:]):
            return compareNum
        else:
            return min(nest[1:])
    except TypeError: # element is a list!!
        min_item = min(nest[0]) # get the min value from that list

        if min_item < compareNum:
            compareNum = min_item # replace if new min is smaller

        return(min(nest[1:]))

nested_list = [[-1523,2],3,-2,[2], [-23,4],[-2234],2,-1000]

print(min(nested_list)) # return -2234

Tough one to solve with all of the restrictions! Hope that helps you out :)

Upvotes: 0

Related Questions