20
\$\begingroup\$

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 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
\$\endgroup\$
1
  • 3
    \$\begingroup\$ I think you should specify that it's the longest list contained in the list including itself. It only shows up in the test cases \$\endgroup\$ Jan 7 at 15:56

20 Answers 20

10
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

R, 58 bytes

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

Try it online!

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

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Maybe fmap(0*) saves a few bytes. \$\endgroup\$
    – Lynn
    Jan 6 at 20:06
5
\$\begingroup\$

BQN, 15 13 bytesSBCS

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Choose is shorter: {=◶0‿(≠⌈´𝕊¨)𝕩}, and {(≠⌈´𝕊¨)⍟=×𝕩} seems to work but i'm not too sure. \$\endgroup\$
    – Razetime
    Jan 6 at 16:07
  • \$\begingroup\$ @Razetime thanks a lot, both work. I've rewritten your second suggestion slightly to reduce the number of recursive calls. \$\endgroup\$
    – ovs
    Jan 7 at 9:05
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I don't know Japt, but is it possible to wrap itself into a list before doing the map, and simply using max after the map, instead of the reduce-by with initial length? \$\endgroup\$ Jan 6 at 17:59
  • \$\begingroup\$ Not in a way that would make this any shorter or without introducing an infinite loop, @KevinCruijssen. At least not that I can think of. \$\endgroup\$
    – Shaggy
    Jan 6 at 19:01
4
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ -10, I believe tio.run/##FcdBCoAgEEDRq7SckWmRFlTQSWQWRkmBmkiL6fSG8OHx8/… \$\endgroup\$
    – loopy walt
    Jan 6 at 18:08
  • \$\begingroup\$ @loopywalt that doesn't work with 0s in the input \$\endgroup\$
    – hyper-neutrino
    Jan 6 at 18:34
  • \$\begingroup\$ OP explicitly says positive integers (first line of post). \$\endgroup\$
    – loopy walt
    Jan 6 at 18:39
  • \$\begingroup\$ @loopywalt oh, positive. my bad \$\endgroup\$
    – hyper-neutrino
    Jan 6 at 18:53
  • \$\begingroup\$ You can omit the [] because max can take multiple arguments \$\endgroup\$
    – pxeger
    Jan 7 at 7:55
4
\$\begingroup\$

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

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I saw that you'd answered, so didn't peek before I'd had a go too, and ended-up naming every single variable with the exact same name... \$\endgroup\$ Jan 6 at 16:23
3
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Wow, TIL about the ?.() operator \$\endgroup\$
    – pxeger
    Jan 6 at 16:53
  • 1
    \$\begingroup\$ @pxeger The () isn't really part of the operation. .? is the 'optional chaining' operator. It's mostly used with variables - e.g. a?.b?.c will result in c if both a and b are defined, and will result in undefined if either a or b is undefined/null. But it can also be used with indexing (a?.[i]) and functions (f?.(args)), of this this answer uses the second with map?.(f). :) \$\endgroup\$ Jan 6 at 17:19
  • 1
    \$\begingroup\$ @KevinCruijssen That's not right; a.?b.?c will result in a.b.c if a and a.b are defined, unrelated to the variables b and c (that would be ??). ?.() is special-case syntax AFAICT \$\endgroup\$
    – pxeger
    Jan 6 at 17:30
  • 1
    \$\begingroup\$ @pxeger a.?b.?c isn't valid JavaScript. I think you meant a?.b?.c? Partially my fault for that .? instead of ?. typo in the first line of my comment.. To correct & clarify part of my previous comment: ?. is the 'optional chaining' operator. It's mostly used with variables - e.g. a?.b?.c will result in a.b.c if both a and a.b are defined, and will result in undefined if either a or a.b is undefined/null. \$\endgroup\$ Jan 6 at 17:54
  • \$\begingroup\$ @pxeger Anyway, it's still all the ?. operator, as can be seen in the link I send in my first comment. Whether you use it as obj?.val, arr?.[index] or func?.(args) doesn't matter too much. \$\endgroup\$ Jan 6 at 17:56
2
\$\begingroup\$

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)

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

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

Charcoal, 23 bytes

⊞υAFυFιF⁼κ⁺κ⟦⟧⊞υκI⌈EυLι

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

⊞υA

Collect the input list into the list of lists.

Fυ

Loop over each list.

Fι

Loop over each element.

F⁼κ⁺κ⟦⟧

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

I⌈EυLι

Output the maximum of all the lengths of the lists.

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

Wolfram Language (Mathematica), 23 bytes

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

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ does it need to be (0#) instead of #? \$\endgroup\$
    – att
    Jan 6 at 18:18
  • \$\begingroup\$ Ah, I see, it does \$\endgroup\$
    – att
    Jan 6 at 20:03
  • 1
    \$\begingroup\$ -# doesn't work with e.g. {2} \$\endgroup\$
    – att
    Jan 7 at 2:54
2
\$\begingroup\$

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

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

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
\$\endgroup\$
7
  • \$\begingroup\$ -1 \$\endgroup\$
    – lyxal
    Jan 6 at 23:43
  • \$\begingroup\$ @lyxal Doesn't work? \$\endgroup\$
    – emanresu A
    Jan 6 at 23:47
  • \$\begingroup\$ It was working when I commented it \$\endgroup\$
    – lyxal
    Jan 6 at 23:56
  • \$\begingroup\$ @lyxal ??? Last push to production was two days ago... \$\endgroup\$
    – emanresu A
    Jan 7 at 0:21
  • \$\begingroup\$ Maybe it's a server issue. Have you tried running it offline? \$\endgroup\$
    – lyxal
    Jan 7 at 0:22
1
\$\begingroup\$

Perl 5, 34 bytes

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

Try it online!

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

Ruby, 44 39 bytes

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

Try it online!

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

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

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.