Counting depth or the deepest level a nested list goes to

Question

A have a real problem (and a headache) with an assignment...

I'm in an introductory programming class, and I have to write a function that, given a list, will return the "maximum" depth it goes to... For example: [1,2,3] will return 1, [1,[2,3]] will return 2...

I've written this piece of code (it's the best I could get T_T)

def flat(l):
    count=0
    for item in l:
        if isinstance(item,list):
            count+= flat(item)
    return count+1

However, It obviously doens't work like it should, because if there are lists that do not count for the maximum deepness, it still raises the counter...

For example: when I use the function with [1,2,[3,4],5,[6],7] it should return 2, but it returns 3...

Any ideas or help would be greatly appreciated ^^ thanks a lot!! I've been strugling with this for weeks now...

Answer 1

In Numpy, you can convert the data structure to a numpy array and use its library functions. arr.shape gives length per layer, so we can len() the shape and get the depth of the structure:

import numpy as np

def f( lists ):
  arr = np.array( lists )
  return len(arr.shape)

f( [[[1,2],[3,4]],[[3,4],[5,6]]] ) # results in 3
f( [[1,2],[3,4]] ) # results in 2
f( [1,2] )  # results in 1
f( [] )  # results in 1
# -- Be dragons: --
f( [[1],[3,4]] ) # results in 1

Numpy docs for shape: https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.shape.html

Answer 2

Let's stick with the original, fairly elegant solution and get it working using max. So many of the other solutions use lambda expressions or require external libraries. This one uses 'pure' python and keeps it simple.

def depth(lst):
    d = 0
    for item in lst:
        if isinstance(item, list):
            d = max(depth(item), d)
    return d + 1

Bonus: this solution counts empty lists and avoids the trap of traversing a string (provided you want to count empty lists).

Answer 3

@John's solution is excellent, but to address the empty list cases, like [], [[]], or further nested lists, you may need to do something like this

depth = lambda L: isinstance(L, list) and (max(map(depth, L)) + 1) if str(L) else 1

Answer 4

Abusive way: Say your list is called mylist

mybrackets = map(lambda x: 1 if x=='[' else -1, [x for x in str(mylist) if x=='[' or x==']'])  
maxdepth = max([sum(mybrackets[:i+1]) for i in range(len(mybrackets))])

This converts your list to a list of opening and closing brackets, then finds the largest number of opening brackets that occur before the corresponding closing bracket occurs.

Answer 5

you can also do it recursively using only python :

def depth(L,d):
    max = d
    for i in range(len(L)):
        if type(L[i])==list :
            a = depth(L[i],d+1)
            if a>max :
                 max = a
    return(max)

this function is recursive and what it does is that it just goes to the maximum depth of your list counting how deep the list is, and when it climbs back up, it keeps only the biggest deepness registered among all nested lists.

Answer 6

If you're looking for a quick fix

def getDepth(matrix):
    try:
        len(matrix)
        return getDepth(matrix[0]) + 1
    except:
        return 0

Answer 7

A way that does not need any additional modules and has the same speed, no matter what depth:

def depth(nested):
    instring = False
    count = 0
    depthlist = []
    for char in repr(nested):
        if char == '"' or char == "'":
            instring = not instring
        elif not instring and ( char == "[" or char == ")" ):
            count += 1
        elif not instring and ( char == "]" or char == ")" ):
            count -= 1
        depthlist.append(count)
    return(max(depthlist))

Basically, what this does is convert the list to a string using repr(). Then for every character in this string equal to "(" or "[" it increases the variable count. for the closing brackets it decreases count. It then returns the maximum that count has reached.

Answer 8

I extended the hammar's answer for every iterable (strings disabled by default):

def depth(arg, exclude=None):
    if exclude is None:
        exclude = (str, )

    if isinstance(arg, tuple(exclude)):
        return 0

    try:
        if next(iter(arg)) is arg:  # avoid infinite loops
            return 1
    except TypeError:
        return 0

    try:
        depths_in = map(lambda x: depth(x, exclude), arg.values())
    except AttributeError:
        try:
            depths_in = map(lambda x: depth(x, exclude), arg)
        except TypeError:
            return 0

    try:
        depth_in = max(depths_in)
    except ValueError:
        depth_in = 0

    return 1 + depth_in

Answer 9

A short addition to what has been said so it can handle empty lists too:

def list_depth(list_of_lists):
    if isinstance(list_of_lists, list):
        if(len(list_of_lists) == 0):
            depth = 1
        else:
            depth = 1 + max([list_depth(l) for l in list_of_lists])
    else:
        depth = 0
    return depth

Answer 10

Breadth-first, without recursion, and it also works with other sequence types:

from collections import Sequence
from itertools import chain, count

def depth(seq):
    for level in count():
        if not seq:
            return level
        seq = list(chain.from_iterable(s for s in seq if isinstance(s, Sequence)))

The same idea, but with much less memory consumption:

from collections import Sequence
from itertools import chain, count

def depth(seq):
    seq = iter(seq)
    try:
        for level in count():
            seq = chain([next(seq)], seq)
            seq = chain.from_iterable(s for s in seq if isinstance(s, Sequence))
    except StopIteration:
        return level

Answer 11

Did it in one line of python :)

enjoy

def f(g,count=0): return count if not isinstance(g,list) else max([f(x,count+1) for x in g])

Answer 12

Let's first rephrase your requirements slightly.

The depth of a list is one more than the maximum depth of its sub-lists.

Now, this can be translated directly to code:

def depth(l):
    if isinstance(l, list):
        return 1 + max(depth(item) for item in l)
    else:
        return 0

Answer 13

easy with recursion

def flat(l):
    depths = []
    for item in l:
        if isinstance(item, list):
            depths.append(flat(item))
    if len(depths) > 0:
        return 1 + max(depths)
    return 1

Answer 14

Here is one way to write the function

depth = lambda L: isinstance(L, list) and max(map(depth, L))+1

I think the idea you are missing is to use max()