19
\$\begingroup\$

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 , so shortest code wins!

\$\endgroup\$

10 Answers 10

8
\$\begingroup\$

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!

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Maybe, f=(a,d)=>Math.max(...a.map(v=>v.at?f(v,-~d):d^v?0:a.length)) \$\endgroup\$
    – tsh
    Feb 26 at 11:27
  • 1
    \$\begingroup\$ Your answer can be compressed using JCram down to 14 bytes - as dⓅ⊓⍞CUay⍷γνU∧ϸ, beating all existing submissions in all languages so far. \$\endgroup\$ Feb 26 at 15:52
  • \$\begingroup\$ @KamilaSzewczyk Interesting. But the uncompressed JS code is using f(v,b+1) instead of f(v,-~b) for the recursion, which would fail. \$\endgroup\$
    – Arnauld
    Feb 26 at 16:03
  • 2
    \$\begingroup\$ 14 bytes (JCram): dⓅ⊓⍞Ⓣ⍅⁶tⒽ⍳⊗∃⍪Ⓐ; by using x instead of v as variable name \$\endgroup\$ Feb 26 at 16:19
  • 1
    \$\begingroup\$ @Mukundan314 The jcram could be 13 bytes after some try and errors: νⓅιk⑦③⍋⍁lζ⁷⊗Ⓙ \$\endgroup\$
    – tsh
    Feb 28 at 5:51
5
\$\begingroup\$

Python, 64 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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Can []== become 0!=? \$\endgroup\$
    – LyricLy
    Feb 26 at 3:59
5
\$\begingroup\$

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!

\$\endgroup\$
0
5
\$\begingroup\$

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

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

Charcoal, 26 bytes

⊞υAFυFΦι⁺⟦⟧κ⊞υ⊖κI⌈EΦυ№ι⁰Lι

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

⊞υAFυFΦι⁺⟦⟧κ

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

I⌈EΦυ№ι⁰Lι

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

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 25 24 bytes

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

As always, 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It feels to me that "Ð0åigˆ}<εDdië®.V"©.V¯à should work (instead of increasing the counter, decrease all of the elements in the list) but it just hangs when I try. \$\endgroup\$
    – Neil
    Feb 26 at 10:40
  • \$\begingroup\$ @Neil Thanks. That's because of the d being an >=0 check. If I change it to (is integer) check, it does work, so thanks. Kinda my fault for not properly explaining dië. There isn't really an isList builtin in 05AB1E, so I've used .ïië (if it's an integer: do nothing; else (aka it's a list): do ...) as a workaround for it. Thus changing the d to , so negative values are in the empty if-block instead of recursive else-block, does work. \$\endgroup\$ Feb 26 at 12:31
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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