CODEWITHSUNDEEP
pythonlistrecursionnested
loiuytre35
loiuytre35

Reputation: 82

Python Get Second Smallest Value in Nested Lists Recurssion

The second_smallest(input_list) function has to return the second smallest value from a list of nested lists. The function MUST NOT pass through the list more then once (can't flatten and then proceed), must use default built-in python functions (no import), must use recursion and NO LOOPS. The list passed into the function can be the form of:

>>> [1,2,3]
>>> [[1,2],3]
>>> [[1],2,3]
>>> [[],1,2,3]
>>> [[1],[2],[3]]
>>> [1,2,3,2,[4,5],[]]

So the input_list can be of all these forms and the return of all of these should be 2

>>> [1,1,2,3]

would return 1

>>> second_smallest([[1],[2]])

is valid, but

>>> second_smallest([1])

is not

What I currently have is this:

def second_smallest(numbers):
    '''(list of int) -> int
    This function takes in 1 parameter, input_list, and returns the second
    smallest number in the list.
    '''
    # if the length of numbers is equal to 2, then set result equal to the
    # second element if the first is less than or equal to second, otherwise
    # set result equal to the first element
    if(len(numbers) == 2):
        if(numbers[0] <= numbers[1]):
            result = numbers[1]
        else:
            result = numbers[0]
    # if the length of numbers is greater than 2, then set result equal to
    # second_smallest_help of the first to second last element in numbers if
    # first is less than or equal to last and last is greater than or equal     to
    # second, otherwise, set result equal to second_smallest of the last to the
    # second last
    else:
        if(numbers[0] <= numbers[-1] >= numbers[1]):
            result = second_smallest(numbers[:-1])
        else:
            result = second_smallest([numbers[-1]] + numbers[:-1])
    return result

but this code only works for lists that are not nested. So how can I adjust my implementation (or change completely) in order to solve this problem?

A way I though of is checking how deep in recursion the current block is in, is there a way to do that?

Upvotes: 1

Views: 1040

Answers (2)

Paul Panzer
Paul Panzer

Reputation: 53029

Ok if loops are forbidden we can bisect:

def second(l):
    n = len(l)
    if n >= 2:
        f1, s1 = second(l[:n//2])
        f2, s2 = second(l[n//2:])
        if f1 is None:
            return f2, s2
        elif f2 is None:
            return f1, s1
        elif f1 < f2:
            return f1, (f2 if s1 is None or s1 > f2 else s1)
        else:
            return f2, (f1 if s2 is None or s2 > f1 else s2)
    if n == 0:
        return None, None
    elif isinstance(l[0], list):
        return second(l[0])
    else:
        return l[0], None

def master(l):
    return second(l)[1]

Upvotes: 2

Bemmu
Bemmu

Reputation: 18217

When you go through entries in the list, check if they are lists or not. If they are lists, then recursively traverse the list. Something like:

def second_smallest(input):
    two_smallest_entries = [None, None]

    def encountered(entry):
        if two_smallest_entries[0] is None or two_smallest_entries[0] >= entry:
            two_smallest_entries[1] = two_smallest_entries[0]
            two_smallest_entries[0] = entry
        elif two_smallest_entries[1] is None or two_smallest_entries[1] >= entry:
            two_smallest_entries[1] = entry

    def traverse(input):
        for entry in input:
            if type(entry) == list:
                traverse(entry)
            else:
                encountered(entry)

    traverse(input)
    return two_smallest_entries[1]

def test(correct, input):
    print second_smallest(input) == correct

test(2, [1,2,3])
test(2, [[1,2],3])
test(2, [[1],2,3])
test(2, [[],1,2,3])
test(2, [[1],[2],[3]])
test(2, [1,2,3,2,[4,5],[]])
test(1, [1,1,2,3])
test(4, [6, 4, [4, 4, 3]])

Upvotes: 2

Related Questions