14
\$\begingroup\$

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 , 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
\$\endgroup\$
5
  • 3
    \$\begingroup\$ It's not totally clear to me what how depth is being defined. I have an intuition based on the examples but a more formal explanation might be helpful. Alternatively, a breakdown of why the answer for [3, [3, [3], 3], 3] is 1, rather than 2 or 3, might also be good. \$\endgroup\$
    – Jonah
    Jan 17 at 2:21
  • 1
    \$\begingroup\$ @Jonah Added a more formal explanation. I'm not sure if it is clear now. \$\endgroup\$
    – alephalpha
    Jan 17 at 2:49
  • \$\begingroup\$ Added a testcase [[[1], [2]], [[3, 4], [5, 6]]] -> 2. \$\endgroup\$
    – alephalpha
    Jan 17 at 6:54
  • \$\begingroup\$ May input contains empty list somewhere nested? For example, [[], [], []]. If it can, what is expected output for this testcase? \$\endgroup\$
    – tsh
    Jan 17 at 9:32
  • \$\begingroup\$ @tsh No. It would not contain empty list on any level. \$\endgroup\$
    – alephalpha
    Jan 17 at 9:36

9 Answers 9

7
\$\begingroup\$

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]]]))

\$\endgroup\$
3
  • 3
    \$\begingroup\$ f=a=>a.some(n=>++n.length!=a[0].length)?1:f(a.flat())+1 \$\endgroup\$
    – tsh
    Jan 17 at 2:14
  • \$\begingroup\$ Why not +n.length? \$\endgroup\$
    – l4m2
    Jan 19 at 5:22
  • \$\begingroup\$ @l4m2 Nice, thanks! \$\endgroup\$
    – emanresu A
    Jan 19 at 5:40
4
\$\begingroup\$

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).

\$\endgroup\$
5
  • \$\begingroup\$ Can't you go from numpy import*? \$\endgroup\$
    – emanresu A
    Jan 17 at 7:49
  • \$\begingroup\$ @emanresuA I thought I should mention the function name somewhere. But I don't really know. \$\endgroup\$
    – loopy walt
    Jan 17 at 7:55
  • \$\begingroup\$ I don't see any real difference as they perform almost the exact same function, but your choice \$\endgroup\$
    – emanresu A
    Jan 17 at 7:56
  • 2
    \$\begingroup\$ @emanresuA I found this on meta: codegolf.meta.stackexchange.com/q/8287/9288 \$\endgroup\$
    – alephalpha
    Jan 17 at 8:25
  • 2
    \$\begingroup\$ I'm pretty sure this should be scored as from numpy import*;ndim \$\endgroup\$
    – pxeger
    Jan 17 at 12:04
4
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 43 bytes

W⁼⌊EθL⁺⟦⟧κ∨⌈EθL⁺⟦⟧κω«≔⟦⟧ζFθFκ⊞ζλ≔ζθ⊞υω»I⊕Lυ

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

W⁼⌊EθL⁺⟦⟧κ∨⌈EθL⁺⟦⟧κω«

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.

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

Flatten the array. (Unfortunately Sum doesn't work in the version of Charcoal on TIO, otherwise using it would save 10 bytes.)

⊞υω

Keep track of the number of loops.

»I⊕Lυ

Output the final depth.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ f=lambda x:min(map(str,x))<':'or len({*map(len,x)})>1or-~f(sum(x,[])) \$\endgroup\$
    – tsh
    Jan 17 at 9:27
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 75...... 54 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.