Search the deepest depths of an array

Question

Given a ragged array, find the length of the largest subarray that contains the depth of that subarray. The base array layer has a depth of 0.

Here is an example:

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

Here, the subarray [2, 5] contains its own depth 2 and has a length of 2 as well.

But in the outermost subarray is a 0, its depth. The outermost subarray has a length of 4, which is greater than 2, so the output is 4.

Test Cases

[1, 2, [3, 4, [2, 5]], 0] => 4
[1, [2, 3], [[1]], [2, [2, 3]]] => 2
[1, 1, 1] => undefined (must not be a number >= 1)

Scoring

This is code-golf, so shortest code wins!

Answer 1

JCram, 13 bytes (SBCS)

-1 thanks to @mukundan314
-1 thanks to @tsh

A JCrammed version, as suggested by Kamila Szewczyk.

νⓅιk⑦③⍋⍁lζ⁷⊗Ⓙ

JavaScript (ES13), 60 bytes

-4 thanks to @mukundan314
-2 thanks to @tsh

Returns 0 for undefined.

f=(a,d)=>Math.max(...a.map(v=>v.at?f(v,-~d):d^v?0:a.length))

Attempt This Online!

Answer 2

Python, ⁶⁴ 63 bytes

-1 byte thanks to @LyricLy

f=lambda x,d=0:max(0!=i*0and f(i,d+1)or(d==i)*len(x)for i in x)

Attempt This Online!

Pyth, 23 bytes

MeSm?q0*0d*lHqdGghGdHg0

Attempt This Online!

Answer 3

R, 97 93 bytes

Edit: -3 bytes thanks to @Giuseppe.

f=\(L,d=0,l=0,`[`=sapply,`?`=max)`if`(is.list(L),?L[f,d+1,length(L)*any(L[identical,d])?l],l)

Attempt This Online!

Answer 4

Jelly, 13 bytes

0LȦ?»ŒḊƇ’߀ṀƲ

Try It Online!

I'm sure this could be done much better, but I am rusty. Returns 0 for undefined.

Explanation

0LȦ?»ŒḊƇ’߀ṀƲ  Main Link
  Ȧ?           If any and all (that is, no 0)
0                Return 0
 L               Else return the length
    »          Take the maximum of the above and ...
           Ṁ   The maximum of
         ߀    This link recursively applied to each of
        ’      The (vectorized) decrement of
     ŒḊƇ       This list filtered for non-zero depth

Numbers have a depth of zero, so ŒḊƇ returns all elements of the list that are themselves lists.

In place of 0LȦ?, the following also work:

• 0e×L (0e is 1 if the list contains 0 and 0 otherwise)
• Ȧ¬×L (Ȧ is 1 if the list is all true, so Ȧ¬ inverts that)

Answer 5

Haskell + hgl 45 bytes

t y x=xd 0$[l x|p y?>x]<>(t(y+1)*~|p 0)<x

t 0

Attempt This Online!

Takes input as a List (Free List Int).

Explanation

We use a pretty straightforward recursive approach to the problem. t takes a depth y and a list x, it then gets the maximum (xd 0) of:

• [l x|p y?>x] the length of x, if y is in the list. (We wrap y with p to specify that we are searching for terminal nodes in the tree, y?>Fe x would search recursively down every level)
• (t(y+1)*~|p 0)<x the map across x of t(y+1) (t with the depth one higher) for list elements and p 0 (always return 0) for terminal nodes.

Then our final answer is naturally t 0 to start the depth at 0.

Point-free, 55 bytes

xd 0<jn<ixm(l<<<fl<e)<uef(mm$dFe$p(-1))(fb$m$dPr$p i)<p

Attempt This Online!

Ech! This is long. I will see about fully explaining and breaking down a reflection tomorrow.

Explanation

A rough explanation is as follows:

• uef(mm$dFe$p(-1))(fb$m$dPr$p i)<p breaks the sublists into layers.
• ixm(l<<<fl<e) filter out the layers not containing their depth and get the lengths of the remainder.
• xd 0<jn get the largest value.

Reflection

Let's start by pointing out the obvious, Haskell is a strongly typed programming language, and ragged lists are not very nice for strongly typed languages. That's why we have to use the weird type List (Free List Int) here. List (Free List Int) is a pretty specific type and there are not a lot of tools to deal with it, which is why half of the point-free answer is manipulating this type into another form.

That being said I'm still disappointed in this answer. The fact that the best approach (that I can find) isn't point-free, points to the fact that this is a recursion scheme that isn't well supported in the library. There are issues here, along with a couple small things to be improved.

• The flattening operation I do as uef(mm$p(-1)*~|id)(fb$m$id*~|p i)<p should have a built in. This would save an absurd number of bytes here, and would make operations based on the depth into a ragged list much more doable.
• There should probably just be an operation which tags elements by their depth, like eu but with a behavior specific to free monoids, instead of the insanity that eu does on free monoids. This would be an alternative solution to the same problems solved by the above suggestion.
• xd 0 should have a shortcut, probably xd0.
• (-1) and other small negative numbers should have shortcuts.
• jn<<ixm, an index concatmap, should have a shortcut.

Answer 6

Charcoal, 26 bytes

⊞υＡＦυＦΦι⁺⟦⟧κ⊞υ⊖κＩ⌈ＥΦυ№ι⁰Ｌι

Try it online! Link is to verbose version of code. Outputs None if no subarray contains its depth. Explanation:

⊞υＡＦυＦΦι⁺⟦⟧κ

Starting with the input array, perform a breadth-first search for subarrays.

⊞υ⊖κ

As each subarray is found, decrement the values in that subarray, so that the subarray will contain zero if it's at the correct depth. (Note that although the version of Charcoal on TIO fails to correctly decrement an empty list, the code already ignores empty lists as they can't contain their depth anyway.)

Ｉ⌈ＥΦυ№ι⁰Ｌι

Output the length of the longest subarray that contained its depth.

Answer 7

05AB1E, 25 24 bytes

"Ð0åigˆ}<εD.ïië®.V"©.V¯à

As always, ragged-list or recursive challenges aren't really 05AB1E's forte.
-1 byte thanks to @Neil.

Outputs an empty string if there is no result.

Try it online or verify all test cases.

Explanation:

"..."       # Recursive string explained below
     ©      # Store it in variable `®` (without popping)
      .V    # Evaluate and execute it as 05AB1E code
        ¯   # Push the global array
         à  # Pop and push its maximum
            # (which is output implicitly as result)

Ð           # Triplicate the current list
            # (which will be the implicit input-list in the first iteration)
 0å         # Pop one copy, and check if it contains a 0
   i  }     # If this is truthy:
    g       #  Pop another copy, and push its length
     ˆ      #  Pop and add this length to the global array
 <          # Then decrease all inner-most values in the ragged list by 1
  ε         # Map over the current list:
   D.ïië    #  If the current value is NOT an integer (aka it's a list):
        ®.V #   Do a recursive call on this list

Answer 8

APL (Dyalog APL), 25 bytes

{⍬≢⍴⍵:(⌈/∇¨,≢ׯ1∊⊢)⍵-1⋄0}

Returns 0 if there is no match.

Attempt This Online!

{⍬≢⍴⍵:(⌈/∇¨,≢ׯ1∊⊢)⍵-1⋄0}­⁡​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠⁠‏​⁡⁠⁡‌⁢​‎⁠⁠‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠⁠‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁢⁣‏⁠‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁢⁤‏‏​⁡⁠⁡‌­
 ⍬≢⍴⍵                      # ‎⁡if argument is not a scalar
                   ⍵-1     # ‎⁢  decrement all elements by 1 (including nested elements)
       ⌈/                  # ‎⁣  maximum of
         ∇¨                # ‎⁤    recursive call on each element
           ,               # ‎⁢⁡    concatenated to
            ≢ׯ1∊⊢         # ‎⁢⁢    length * (-1 exists in argument)
                      ⋄    # ‎⁢⁣else
                       0   # ‎⁢⁤  return 0
💎

Created with the help of Luminespire.

Answer 9

APL(NARS), 42 chars

{d←≡⍵⋄⌈/∊{0=k←↑⍴⍵:0⋄(k×⍵∊⍨d-≡⍵),∇¨⍵[⍳k]}⍵}

test:

  f←{d←≡⍵⋄⌈/∊{0=k←↑⍴⍵:0⋄(k×⍵∊⍨d-≡⍵),∇¨⍵[⍳k]}⍵}
  f  1 2 (3 4 (2 5)) 0
4
  f 1 (2 3) (⊂,1) (2 (2 3))
2
  f 1 1 1 1
0

Answer 10

Wolfram Language (Mathematica), 88 bytes

Max@Reap[Do[Do[If[MemberQ[e,l],Sow@Length@e],{e,Level[#,{l}]}],{l,0,Depth@#-1}]][[2,1]]&

Try it online!