Array depth of a ragged list

Question

This is not a duplicate of this challenge.

Here by an array, I mean a nested list that is "not ragged", i.e., it is either a list of elements, or a list of arrays of the same shape. For example, this is an array of shape (2,3):

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

The depth (or rank) of an array is the length of its shape. The depth of the array above is 2.

But we can see every ragged-list as an array, where every element of the array is a either an atom (e.g., an integer) or a ragged-list. For example, the following ragged-list can be seen as an array of shape (2,3):

[[1, 2, [3]], [4, [5], [6, [7]]]]

The six elements of this array are 1, 2, [3], 4, [5], [6, [7]]. As an array, its depth is 2.

So we can define the array depth of a ragged list to be its maximum depth as an array.

Or more formally:

• If a ragged list has length \$a\$, we say it is an array of shape \$(a)\$.
• If every element of a ragged list is an array of shape \$(a_1,\dots,a_n)\$, and the length of the ragged list is \$a_0\$, then we say it is an array of shape \$(a_0,a_1,\dots,a_n)\$. (So it is also an array of shape \$(a_0,a_1,\dots,a_{n-1})\$.)
• The array depth of a ragged list is the maximum length of its shape when we see it as an array.

Task

Given a non-empty ragged list of positive integers, output its array depth. You may assume that the input does not contain any empty list.

This is code-golf, so the shortest code in bytes wins.

Testcases

[1] -> 1
[1, 2, 3] -> 1
[[1, 2, 3]] -> 2
[3, [3, [3], 3], 3] -> 1
[[[[1], 2], [3, [4]]]] -> 3
[[1, 2, 3], [4, 5, 6]] -> 2
[[1, 2, [3]], [4, [5], [6, [7]]]] -> 2
[[1, 2], [3, 4, 5], [6, 7, 8, 9]] -> 1
[[[1, 2]], [[3, 4], [5, 6]]] -> 1
[[1, [2]], [[[3]], [[[4]]]]] -> 2
[[[1], [2]], [[3, 4], [5, 6]]] -> 2
[[[[[[[3]]]]]]] -> 7

Answer 1

JavaScript (ES6), 54 bytes

f=a=>a.some(n=>+n.length!=a[0].length)?1:f(a.flat())+1

A quite simple approach: check if all elements are the same length, increment a counter if they are and repeat with the list flattened by one level, then return the counter.

-3 bytes thanks to tsh. -1 more thanks to l4m2.

f=a=>a.some(n=>+n.length!=a[0].length)?1:f(a.flat())+1

console.log(f([[[[1,2],[3,4]]]]))
console.log(f([[[[[[3, []]]]]]]))
console.log(f([[1, 2], [3, 4, 5], [6, 7, 8, 9]]))
console.log(f([[[1, 2]], [[3, 4], [5, 6]]]))

Answer 2

Python/NumPy, 23 bytes

Thx @pxeger for clarifying the legalese.

from numpy import*
ndim

Attempt This Online!

Not entirely legal Python/NumPy 22 bytes

from numpy import ndim

Attempt This Online!

Builtin (in case you haven't noticed).

Answer 3

Haskell + hgl, 22 bytes

l<itr(K**l$rH lp)<pM[]

Takes input as a free monad of lists (Free List a).

Explanation

Our strategy here is to calculate the "shape" of the array first and then derive its depth from that. We represent a shape as a list of sizes.

We are going to use a recursive strategy. Our base case is a terminal element which has shape [] and our inductive case is a list. If we have the shape of every element of a list then we know its shape is longest common prefix of all their shapes and add its own length to the front.

With that itr x<pM y will let us do this recursion. We already said y was [] so that's easy. Now we just need the other function.

lp gets the longest common prefix of two lists so rH lp gets the longest common prefix of a list of lists. We add K**l to put its own length on the front.

So our result is

itr(K**l$rH lp)<pM[]

which gets the shape of a array. But we need the depth so we add an extra l< to get the length of the shape.

Reflections

• On my dev branch I've already made a alias for (**)K. This would have come in use on this challenge here as well. It would have saved 2 bytes l<itr(l*:*rH lp)<pM[]
• This is not the first time I've used itr and pM together in this way. When we only care about the shape of a free it's very useful to first replace all the elements and then iterate. This should have it's own name. It would have saved 3 4 bytes: l<shp(K**l$rH lp)i (an extra byte is saved because [] can be replaced with i to save a byte whereas in the original i and [] are the same length)

Answer 4

R, 78 bytes

f=function(r)sum(1,if(all(Map(is.list,r))&!sd(lengths(c(r,r))))f(unlist(r,F)))

Try it online!

Answer 5

Python3, 107 bytes:

f=lambda x,c=0:int in[*map(type,x)]or any(len(i)!=(c:=c or len(x[0])) for i in x)or min(1+f(i,c)for i in x)

Try it online!

Answer 6

Charcoal, 43 bytes

Ｗ⁼⌊ＥθＬ⁺⟦⟧κ∨⌈ＥθＬ⁺⟦⟧κω«≔⟦⟧ζＦθＦκ⊞ζλ≔ζθ⊞υω»Ｉ⊕Ｌυ

Try it online! Link is to verbose version of code. Explanation:

Ｗ⁼⌊ＥθＬ⁺⟦⟧κ∨⌈ＥθＬ⁺⟦⟧κω«

Convert any numbers in the array to empty lists by vectorised adding them to the empty list (this leaves arrays unchanged). Compare their minimum and maximum length, unless the maximum length is 0 i.e. if the array only contains integers. Repeat while all arrays have the same length.

≔⟦⟧ζＦθＦκ⊞ζλ≔ζθ

Flatten the array.

⊞υω

Keep track of the number of loops.

»Ｉ⊕Ｌυ

Output the final depth.

33 bytes using the newer version of Charcoal on ATO:

Ｗ⁼⌊ＥθＬ⁺⟦⟧κ∨⌈ＥθＬ⁺⟦⟧κω«≔Σθθ⊞υω»Ｉ⊕Ｌυ

Attempt This Online! Link is to verbose version of code.

Answer 7

Jelly, 14 bytes

^{Seems long!}

¬RẎƬṖẈ€E€i0oLƲ

A monadic Link accepting a list that yields the "array-depth".

Try it online!

How?

Uses the same intuition as emanresu A's JavaScript answer

¬RẎƬṖẈ€E€i0oLƲ - Link: list, A
¬              - logical NOT - converts all integers to zeros
 R             - range (vectorises) - converts all zeros to empty lists
   Ƭ           - collect up inputs while distinct, applying:
  Ẏ            -   tighten
    Ṗ          - pop - remove the final one
     Ẉ€        - lenth of each for each
       E€      - all-equal for each
             Ʋ - last four links as a monad, f(that):
         i0    -   first 1-indexed index of a zero (or zero)
           oL  -   logical OR with the length

Answer 8

05AB1E, 18 bytes

SмΔ¼D€gË≠i¾q}€`}¾<

Inspired by @emanresuA's JavaScript answer.

Try it online or verify all test cases.

I initially had this 13-byter, but unfortunately it fails for test cases like [[[1,2]],[[3,4],[5,6]]].

Explanation:

Sм           # Convert all integers to an empty string:
S            #  Convert the (implicit) input-list to a flattened list of digits
 м           #  Remove all those digits from each inner-most integer/string of
             #  the (implicit) input-list
  Δ          # Loop until the list no longer changes:
   ¼         #  Increase the counter variable by 1 (starts at 0)
   D         #  Duplicate the current list
    €g       #  Get the length of each inner item
      Ë≠i    #  If they are NOT all the same length:
         ¾   #   Push the counter variable
          q  #   And stop the program
             #   (after which this is output implicitly as result)
        }    #  Close the if-statement
         €`  #  Flatten one level down
  }¾         # After the loop: push the counter variable
    <        # Decrease it by 1 (because the last two iterations were the same
             # for the loop to stop)
             # (after which this is output implicitly as result)

Answer 9

Ruby, 75...... 54 bytes

f=->a{a.map(&:size).uniq.one?&&a.flatten!(1)?1+f[a]:1}

Try it online!

Answer 10

Nekomata, 5 bytes

Uˡ{Ťj

Attempt This Online!

Uˡ{Ťj
U       Wrap the input in a singleton list
 ˡ{     Loop until failure, and return the number of iterations:
   Ť        Transpose; fails if it is not a rectangular 2D array
    j       Join