Code does not work for all test cases of flattening a nested list

Question

Write a function to flatten a list. The list contains other lists, strings, or ints. A list such as the example given below is to be flattened:

[[1,'a',['cat'],2],[[[3]],'dog'],4,5]

to produce a flattened list:

[1,'a','cat',2,3,'dog',4,5] (order matters)

I wrote my code as follows and got the required flattened list above. However, I did not score full marks for the question as apparently my code did not work for other test cases. The question did not show me any test cases.Thus I only know that my code works properly for the example given above Could you think of any cases that can show that my code is not correct?

My thinking process: Look through every index element in input list 'aList' by using a for loop. If that element happens to be a str/int, then that element is already flattened and I'll add that into my output flattened list 'new' using append. However, if that index element is still a list, it has not yet be flattened, so I'll do a recursive call 'new.append(aList[n])' so that I now look within list of list ie. aList[0][0] etc. until I find an element that is not a list.


new = []
def flatten(aList):


    for n in range(len(aList)):
        if type(aList[n]) == type([]):
                
                flatten(aList[n])
        else:
            new.append(aList[n])
    
    return new

Here, I found a code online that gets me the full marks for the question.


def flatten(aList):
    new = []
    for i in aList:
        if type(i) == type([]):
            new.extend(flatten(i))
            
        else:
            new.append(i)
            
    return new

It is very similar to my code, with the only difference in the way it calls the recursive function to flatten any nested lists. I directly call my function 'flatten(aList[n])' while the sample answer used 'new.extend(flatten(i)). However, I could not see why my code does not work for all cases. Also, how is using extend going to solve the problem?

By declaring `new = []` outside of the function, it will fail to flatten a second array. So I guess by having 2 test your function fails? Try moving it into the function — Dames, Jul 05 '20 at 12:58
Run your code twice on the same list and print the output: `[1, 'a', 'cat', 2, 3, 'dog', 4, 5, 1, 'a', 'cat', 2, 3, 'dog', 4, 5]`. simply moving it into the function wont work either. — Patrick Artner, Jul 05 '20 at 12:58
`extend` is exactly build to insert all elements of an iterable into the list it is executed with - so its better to use then appending single elements from a computational standpoint — Patrick Artner, Jul 05 '20 at 12:59
See [how-to-make-a-flat-list-out-of-list-of-lists](https://stackoverflow.com/questions/952914/how-to-make-a-flat-list-out-of-list-of-lists) or [flatten-an-irregular-list-of-lists](https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists) for more solutions on how to do this — Patrick Artner, Jul 05 '20 at 13:02
If it's a multi test-case problem, you need to reset new after each call to 'flatten' method. — Sabareesh, Jul 05 '20 at 13:09

score 0 · Answer 1 · answered Jul 05 '20 at 13:10

0

If it's a multi test-case problem, you need to reset new after each call to 'flatten' method.

answered Jul 05 '20 at 13:10

Sabareesh

711
1
7
14

Amal K · Answer 2 · 2020-07-05T13:28:07.463

Your algorithm is correct. Your test cases are probably failing because of the new variable declared outside of the flatten function. This causes the result of the function to be extended to the new list that already contains results from previous function calls. Pass the list as parameter for a recursive solution:


def flatten(aList, new=None):
   if new == None: new = []
    for n in range(len(aList)):
        if type(aList[n]) == type([]):
                
                flatten(aList[n], new)
        else:
            new.append(aList[n])
    
    return new

What's important here that notice how I have used the default value of the argument new as None and then assigned it inside the function if it is None, rather than just: def flatten(aList, new=[]):. Never do this–use a mutable datatype like list as a default argument as it will only be evaluated once and this instance will be reused everytime the function is called rather than creating a fresh empty list. Check this out for more details.

If you want better performance, try using two functions to optimize the if away:

flatten = lambda aList: flatten_aux(aList, [])

def flatten_aux(aList, new):
    for n in range(len(aList)):
        if type(aList[n]) == type([]):
                
                flatten(aList[n], new)
        else:
            new.append(aList[n])
    
    return new

Jake Levi · Answer 3 · 2020-07-06T00:18:54.430

This is not an answer to the question, but rather an alternative way to solve the problem using generators (I would post this as a comment, but comments don't format multi-line code, to the best of my knowledge):

def flat_gen(nd_list):
    if type(nd_list) is list:
        for i in nd_list:
            yield from flat_gen(i)
    else:
        yield nd_list

def flatten(nd_list):
    return list(flat_gen(nd_list))

nd_list = [[1,'a',['cat'],2],[[[3]],'dog'],4,5]
flat_list = flatten(nd_list)
print(flat_list)
answer = [1,'a','cat',2,3,'dog',4,5]
print(flat_list == answer)

Output:

[1, 'a', 'cat', 2, 3, 'dog', 4, 5]
True

Code does not work for all test cases of flattening a nested list

3 Answers3