Find the maximum length in a ragged list

Question

Given a ragged list of positive integers find the size of the largest list contained somewhere in it.

For example:

[1,[1,[8,2,[1,2],5,4,9]],2,[],3]

Here the answer is 6 because one of the lists has 6 elements and all other lists have fewer.

[1,[1,[8,2,[1,2],5,4,9]],2,[],3]
       ^ ^ ^     ^ ^ ^

The length doesn't care in any way about the value of the elements, so a list can be longer than the list that contains it.

Task

Given a ragged list of positive integers output the size of the largest list contained somewhere in it. You may take input in any reasonable format.

This is code-golf so answers will be scored in bytes with the goal being to minimize the size of your source-code.

Testcases

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

Answer 1

Python 2, 40 bytes

f=lambda a:a>[]and max(len(a),*map(f,a))

Attempt This Online!

Uses Python 2's global ordering: lists are all considered greater than ints. We can also use > instead of >=, because []>[] is False which is the same as 0, which would be the result anyway from the max(len(a),*map(f,a)).

This also uses the var-args version of max which is shorter than constructing a list. Normally we wouldn't be able to do this, because the var-args form of max only works with 2 or more arguments, but if we know a>[] then a is non-empty, so *map(f,a) always adds at least one more argument to the call.

Whython, 34 bytes

f=lambda a:max(len(a),*map(f,a))?0

Attempt This Online!

When a member is an integer, the len call fails; we just catch this and replace the result with 0. When a is an empty list, this also fails because max gets only one argument, but catching and returning 0 conveniently fixes this too.

Answer 2

R, 58 bytes

f=function(x)max(l<-length(x),if(l&is.list(x))sapply(x,f))

Try it online!

Answer 3

Haskell + free, 40 37 bytes

3 bytes saved by Lynn

Haskell doesn't have a built in ragged list type so we need to build one out of free monads from the free package.

iter(maximum.((:)=<<length)).fmap(*0)

Try it online!

Explanation

First we replace every number with 0 because that is their length, or at least it's the length they should be to make the math work out.

Then from there we make a function maximum.((:)=<<length. This looks complicated, but really all it does is take the length of a list of integers, put it on the front of the list and take the maximum of that. So it gives the max of the list or the length of the list whichever is larger.

With this we use iter to "tear down" the list. iter will start first with the lists containing only integers and run this on them then replace them with their results, and then it will do that again, and again until we've reduced the entire structure down to a single element.

We can visualize the entire process as:

[1,[1,[8,2,[1,2],5,4,9]],2,[],3]
[0,[0,[0,0,[0,0],0,0,0]],0,[],0] -- Replace everything with 0
[0,[0,[0,0,2,0,0,0]],0,0,0]
[0,[0,6],0,0,0]
[0,6,0,0,0]
6

Answer 4

BQN, 15 13 bytes^SBCS

-2 bytes thanks to Razetime!

{(≠⌈´𝕊⍟=¨)×𝕩}

Run online!

{(≠⌈´𝕊⍟=¨)×𝕩}   # Anonymous function taking the list as right argument 𝕩
          ×𝕩    # Sign of each number, converts all numbers to 1
 =𝕩     ¨       # For each value in the list
     𝕊⍟=        #   do a recursive call if it is a list (rank 1)
                #   and return integers unchanged (rank 0)
     ≠⌈´        # Maximum reduction of the results starting with the length of 𝕩

or questionable 12 bytes:

{(≠⌈´𝕊⎊0¨)𝕩}

Run online!

This relies on exceeding the maximum call stack size, which means this only works if such a limit exists and is larger than the maximum depth of the ragged list.

Answer 5

05AB1E, 14 bytes

ΔDgˆʒ˜gĀ}€`}¯à

Try it online or verify all test cases.

Explanation:

Δ             # Loop until the result no longer changes:
 D            #  Duplicate the current list
  g           #  Pop and push its length
   ˆ          #  Pop and add this to the global array
    ʒ         #  Filter the items within the list:
     ˜        #   Flatten it
      g       #   Pop and push the length
       Ā      #   Check that this is not 0
    }         #  After the filter:
     €`       #  Flatten the list one level down
}             # After the loop:
 ¯            # Push the global array with lengths
  à           # Pop and push its maximum
              # (which is output implicitly as result)

Bug-abuses the fact that ˜ gives an error on integers, causing them to be removed after the filter. Most errors in 05AB1E are simply ignored, which would be incorrect in this case, since the gĀ would result in a truthy result.

---

Could have been 13 bytes in the legacy version of 05AB1E if all integers were guaranteed to contain less digits than the intended result:

˜g'ε×æ'g«€.VZ

Try it online or verify all test cases.

˜             # Flatten the (implicit) input-list
 g            # Pop and push its length
  'ε×        '# Push a string of that many "ε"
     æ        # Pop and push the powerset of this string
              # (the prefixes would be enough, but that builtin doesn't include
              # an empty string which the powerset builtin does)
      'g«    '# Append a trailing "g" to each
         €    # Map over each string
          .V  #  Execute it as 05AB1E code with the (implicit) input-list
              #  (where `ε` is a map, and `g` pushes the length)
            Z # Push the flattened maximum of this list
              # (which is output implicitly as result)

This unfortunately doesn't work if the integers are too big, because the εg would include the lengths of each inner integer in the resulting list of lists, which could potentially be larger than the intended result.
See that it fails if an input-number contains too many digits.

Minor note: Luckily the 'ε× isn't a dictionary word. If we would use € instead of ε it wouldn't work, because '€× is the dictionary word for "view".

Answer 6

Japt, 14 13 11 bytes

˶ԩßDÃrwUl

Try it (includes all test cases)

˶ԩßDÃrwUl     :Implicit input of array U
Ë               :Map each D
 ¶              :  Test for strict equality with
  Ô             :    Max with nothing if an integer (which, for some reason, returns an object)
  Ô             :    Itself reversed if an array (which works because reversing mutates the array)
   ©            :  Logical AND with
    ßD          :   Recursive call with argument D
      Ã         :End map
       r        :Reduce by
        w       :  Maximum
         Ul     :  With initial value of length of U

Answer 7

Python 3, 41 bytes

f=lambda x:x*-1or max([len(x),*map(f,x)])

Try it online!

-10 bytes thanks to loopy walt with a better way of typechecking

Answer 8

Factor, 41 bytes

[ [ array? ] deep-filter longest length ]

Try it online!

Get a list of every list (no matter the depth), then find the length of the longest one. deep-filter is like filter except instead of traversing elements in a linear fashion, it traverses nested sequences using a depth-first search algorithm. (deep-reduce is also an approach that works, but it offers atoms and so it's verbose to check for and ignore them.)

                        ! { 1 { 1 { 8 2 { 1 2 } 5 4 9 } } 2 { } 3 }
[ array? ] deep-filter  ! {
                        !     { 1 { 1 { 8 2 { 1 2 } 5 4 9 } } 2 { } 3 }
                        !     { 1 { 8 2 { 1 2 } 5 4 9 } }
                        !     { 8 2 { 1 2 } 5 4 9 }
                        !     { 1 2 }
                        !     { }
                        ! }
longest                 ! { 8 2 { 1 2 } 5 4 9 }
length                  ! 6

Answer 9

R, 66 64 bytes

f=function(x)"if"(is.list(x)&(l=length(x)),max(l,sapply(x,f)),0)

Try it online!

Currently being out-golfed by Dominic van Essen.

Answer 10

JavaScript, 40 bytes

f=a=>a/a||Math.max(a.length,...a.map(f))

Try it online!

JavaScript, 43 bytes

f=a=>Math.max(~~a.length,...a.map?.(f)??[])

f=a=>Math.max(~~a.length,...a.map?.(f)??[])

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

Answer 11

Vyxal, 9 bytes

-λ[vxnLJG

Try it Online!

-         # Subtract from self to generate a list with the same shape but only zeroes
 λ        # A recursive lambda, which automatically gets called with ^
  [       # If it's truthy (a list)
   vx     # Do a recursive call on each item
     nLJ  # Append the length of the list
        G # Get the maximum

Answer 12

APL (Dyalog Unicode), 28 25 bytes

Full program.

l←⍬
{1<|≡l,∘≢←⍵:∇¨⍵}⎕
⌈/l

Try it online!

l←⍬ initiate l to an empty list

⎕ get evaluated console input
{…} apply the following anonymous lambda to that; the argument is ⍵:  ⍵ the length of the argument
 l,∘≢←⍵ append l with the argument length, giving the argument as pass-through value
 ≡ the depth (nesting level — negative if ragged) of the argument
 | absolute value of that
 1<…: if that is greater than 1:
  ∇¨ recurse on each element of the argument

⌈/l [implicitly print] the largest value of l (lit. max-reduce)

Answer 13

BQN, 13 bytes

{⌈´≠⊸∾𝕊¨⍟=×𝕩}

Anonymous function that takes a list and returns an integer. Run it online!

Found independently of ovs's solution, but takes advantage of a 1-byte savings proposed in a comment on that solution by Razetime.

Explanation

{⌈´≠⊸∾𝕊¨⍟=×𝕩}
            𝕩   Start with the argument, which is either a list or an integer
           ×    Get its sign (applies itemwise over lists): converts all integers to 1
         ⍟=    Apply this function 0 times to an integer or 1 time to a list:
       𝕊¨         Map a recursive call over each element
   ≠⊸∾         Prepend the length of the list (or 1 if it's an integer)
 ⌈´            Take the maximum

Answer 14

Charcoal, 23 bytes

⊞υＡＦυＦιＦ⁼κ⁺κ⟦⟧⊞υκＩ⌈ＥυＬι

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

⊞υＡ

Collect the input list into the list of lists.

Ｆυ

Loop over each list.

Ｆι

Loop over each element.

Ｆ⁼κ⁺κ⟦⟧

If adding the empty list to the element results in a copy of the element, ...

⊞υκ

...then push the element to the list of lists. (Adding the empty list to a scalar results in an empty list, not the scalar.)

Ｉ⌈ＥυＬι

Output the maximum of all the lengths of the lists.

Answer 15

Wolfram Language (Mathematica), 23 bytes

Max[Length@#,#0/@(0#)]&

Try it online!

Answer 16

Brachylog, 10 bytes

{ċl|ċ∋↰}ᶠ⌉

Try it online!

Explanation

{      }ᶠ     Find all possible outputs of the following predicate:
 ċ                The input is a list
  l               Output its length
   |            OR
    ċ             The input is a list
     ∋            Take an element of that list (creates choice points for each element)
      ↰            Recursively call this predicate
         ⌉    Final output is the maximum value of the resulting list of possible outputs

Answer 17

Jelly,  7  6 bytes

¬ß€»LṀ

Try it online!

A monadic Link accepting a list containing any strictly positive integers or nested, similar, lists that yields the maximal length list.

How?

¬ß€»LṀ - Link, call this "f": list, A
¬      - logical NOT (vectorises) - convert all positive integers to zeros so that
                                    we wont implicitly treat them as ranges
  €    - for each element, E, in A (...if the current A isn't now a zero):
 ß     -   call this Link (i.e. f(A=E))
    L  - length of A - Note that zero has length one.
   »   - maximum (vectorises)
     Ṁ - maximum (of the resulting list)

Answer 18

Perl 5, 34 bytes

sub f{max@_+0,map ref?f(@$_):0,@_}

Try it online!

Answer 19

Ruby, 44 39 bytes

f=->d{d*0==0?0:[d.size,*d.map(&f)].max}

Try it online!

Answer 20

C (gcc) with -m32 and -lm, 94 88 87 bytes

• -6 thanks to ceilingcat

32-bit mode used to make bit-twiddling of pointers easier.

As C doesn't have any list primitive, I implemented a tagged value list (lists stored as an item have the least significant bit set.) The function simply gets the total length of the current list and checks to see if any sublist has a longer length.

f(l,m,i)int*l,*m;{for(m=l,i=0;l;l=l[1])i++;for(;m;m=m[1])*m&1?i=fmax(f(*m^1),i):0;l=i;}

Try it online!

Ungolfed:

f(l,m,i)int*l,*m;{
  for(m=l,i=0;l;l=l[1]) i++; // Get length of current list
  for(;m;m=m[1])
    *m&1? // Is this a sublist?
      i=fmax(f(*m^1),i): // Is the sublist longer?
    0;
  l=i;
}

Answer 21

tinylisp, 65 56 bytes

(load library
(d M(q((x)(i(v x)1(max(c(length x)(map M x

Try it online!

-9 bytes thanks to DLosc's suggestion for type abuse.

Answer 22

Julia 1.0, 39 34 bytes

~a::Int=1
~a=max(length(a),.~a...)

Try it online!

Pretty easy to get a general idea of how this works. The .~(a) is way of recursively mapping our function (which we've called ~) on the elements of a.

(-5 bytes thanks to @MarcMush - making use of dispatch instead of the isa check.)