Find the dimensions of a ragged list

Question

For any ragged list its dimensions will be a list of non-negative integers defined as follows:

• Elements that are not a list will have dimensions \$\textbf{[}\,\,\textbf{]}\$.
• An empty list has dimensions \$[0]\$.
• An \$n\$ dimensional list \$L\$ of length \$x\$ has dimensions \$x : k\$ where \$k\$ is the element wise maximum of the dimensions of the elements of \$L\$ (treating missing elements as zero).

(Here, : is "cons", the list constructor, e.g. in Lisp or Haskell)

The intuitive idea is that this is the dimensions of the smallest box which can fit the list. But this is still a little bit daunting, so let's work through some examples.

To start with, for one dimensional lists, its dimensions are always just its length.

[ 1
, 2
, 3
]

There are 3 elements here so its dimensions are \$3:k\$. To determine \$k\$ we look at the dimensions of each element. They are all integers so they have dimensions \$\textbf{[}\,\,\textbf{]}\$, and the pairwise maximum is also \$\textbf{[}\,\,\textbf{]}\$. So the dimensions are \$3:\textbf{[}\,\,\textbf{]}\$ or just \$[3]\$.

Let's do an example that is actually ragged:

[ [ 1
  , 2
  , 9
  , 9
  ]
, 4
]

There are two elements, the first is one dimensional so it has dimensions \$[4]\$, the second is an integer so it has dimensions \$\textbf{[}\,\,\textbf{]}\$. Now we take the pairwise maximum. Since \$[4]\$ has more elements we treat the missing elements as zeros. The maximum is just \$[4]\$ then. The total list has length \$2\$ so the answer is \$2:[4]\$ or \$[2,4]\$.

Let's do another example:

[ [ 1
  , 2
  , 9
  , 9
  ]
, [ []
  , 2
  ]
]

The first element is the same, but the second one is different, so let's calculate its dimensions. It has two elements with dimensions \$[0]\$ and \$\textbf{[}\,\,\textbf{]}\$. The pairwise maximum is \$[0]\$ so this element has dimensions \$[2,0]\$. With this in mind now we take the pairwise maximum of \$[4]\$ and \$[2,0]\$ which gives \$[4,0]\$. Finally we add one the \$2\$ for the length of the top level and get the dimensions of \$[2,4,0]\$

Task

Given an arbitrary ragged list of positive integer give a list of non-negative integers representing its dimensions. You may assume that the input is a list.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[]
=> [0]
[ 1, 2, 3]
=> [3]
[[1, 2, 9, 9], 4]
=> [2,4]
[[1, 2, 9, 9], [[], 2]]
=> [2,4,0]
[[[]],[]]
=> [2,1,0]
[[1,2,3],[[1,2,3],[[1,2,3],[[1,2,3],[1,2,3]]]]]
=> [2,3,3,3,3]

Answer 1

Python 2, 52 bytes

d=lambda l:d<l and[len(l)]+map(max,[],*map(d,l))or[]

Attempt This Online!

Old Python 2, 53 bytes (@att)

d=lambda l:[1]*(d<l)and[len(l)]+map(max,[],*map(d,l))

Attempt This Online!

Old Python 2, 65 bytes

d=lambda l:[1]*(d<l)and[len(l)]+map(lambda*a:max(a),[],*map(d,l))

Attempt This Online!

That's a cleanup of @Steffan's Python 2 answer. He made it a challenge, so I took the liberty of posting it as a separate answer.

Answer 2

Whython, 95 bytes

from itertools import*
d=lambda l:[len(l),*(map(max,zip_longest(*map(d,l),fillvalue=0))?[])]?[]

Attempt This Online!

Answer 3

JavaScript, 65 bytes

f=(a,e=+(o=[]),L=0)=>!a.map?.(v=>f(v,e+1)*++L)|L<o[e]||(o[e]=L,o)

f=(a,e=+(o=[]),L=0)=>!a.map?.(v=>f(v,e+1)*++L)|L<o[e]||(o[e]=L,o)

t = `
[] => [0]
[ 1, 2, 3] => [3]
[[1, 2, 9, 9], 4] => [2,4]
[[1, 2, 9, 9], [[], 2]] => [2,4,0]
[[[]],[]] => [2,1,0]
[[1,2,3],[[1,2,3],[[1,2,3],[[1,2,3],[1,2,3]]]]] => [2,3,3,3,3]
`.trim().split('\n').map(l => l.split('=>').map(v => JSON.parse(v)));
t.forEach(([i, e]) => {
  console.log(f(i) + '' == e, JSON.stringify(f(i)));
});

f=(
  a,      // Input array
  e=+(    // Current level
  o=[]),  // Output array, initialized by []
  L=0     // length of input
)=>
  !a.map?.(v=>    // If Current level is an array not integer And
    f(v,e+1)*     //     Recursively call `f` for inner levels
    ++L)|         //     Count length of input array
  L<o[e]||        // If Current length is longer than we ever seen
  (o[e]=L,o)      // Update it, and remember to return the output array

Answer 4

Wolfram Language (Mathematica), 36 bytes

Max/@#~Position~_?AtomQ~Flatten~{2}&

Try it online!

-5 bytes thanks to @att.

---

Wolfram Language (Mathematica), 41 bytes

Max/@Thread@PadRight@Position[#,_?AtomQ]&

Try it online!

How?

In Mathematica, everything is an expression. An expression is a tree, where atoms are the leaves: symbols, numbers, strings, etc.

How many atoms are there in the expression {1, 2, 3}?

The answer is 4. In fact, {1, 2, 3} is just a syntactic sugar for List[1, 2, 3], which has 4 atoms: 1, 2, 3 and List. List is the head of the expression, whose position is 0.

Now takes the input {1, {}, 2} as an example. When desugared, it becomes List[1, List[], 2], which has 4 atoms: List, 1, List, 2.

Position[#,_?AtomQ] finds the positions of all atoms in the input. In this case, it is {{0}, {1}, {2, 0}, {3}}.

PadRight pads the list with 0s to make it a full (i.e., not ragged) array. So it becomes {{0, 0}, {1, 0}, {2, 0}, {3, 0}}.

Thread transposes the array. So it becomes {{0, 1, 2, 3}, {0, 0, 0, 0}}.

Finally, Max/@ finds the maximum value in each row. So the result is {3, 0}.

Answer 5

R, 126 119 bytes

d=function(l,`+`=sapply,r=length)c(r(l),if(any(m<-l+is.list))do.call(pmax,c(lapply(k<-l[m]+d,`[`,1:max(k+r)),na.rm=T)))

Try it online!

This was supposed to be just a simple recursive function using the elementwise-maximum (emax) to get the largest element at each position of a list of unequal-length vectors:

dimensions=
d=function(l,m=sapply(l,is.list))c(length(l),if(any(m))emax(lapply(l[m],d)))

Unfortunately, the emax function does not exist. This is because R loves element-recycling, and the similar-seeming parallel-maximum function - pmax - helpfully recycles the elements of unequal-length vectors (so pmax(10:11,1:3) gives 10 11 10 instead of 10 11 3): exactly what we don't want here!).
So this approach needs to implement emax by 'padding' all shorter vectors with NAs, before calling pmax and specifying na.rm=T to ignore them:

emax=
function(l)do.call(pmax,c(lapply(l,`[`,1:max(lengths(l))),na.rm=T))

Rolling these two functions together, we can golf out a few excess characters (and render the code near-unreadable as a by-product), but bearing in mind how awkward this overall approach is, I won't be surprised if there's a shorter one that doesn't require creating nonexistant functions to make it work...

Answer 6

Python 3, 73 bytes

f=lambda*a:a and[max(map(len,a)),*f(*[b for b in sum(a,[])if'A'<str(b)])]

Try it online!

And this is 70 bytes in Python 3 (Cython).

Answer 7

Python 2, 77 bytes

d=lambda l:l*0==[]and[len(l)]+('['in`l`[1:]and map(max,[],*map(d,l))or[])or[]

Attempt This Online!

Takes advantage of a bunch of Python 2 stuff:

• multiple lists passed to map pads with None
• max works with values other than integers (which includes None)
• can do `l` with Python 2's backticks instead of str(l)

Python, 128 bytes

from itertools import*
d=lambda l:[len(l),*(map(max,zip_longest(*map(d,l),fillvalue=0))if'['in str(l)[1:]else[])]if[]==l*0else[]

Attempt This Online!

Answer 8

Haskell + free, 73 bytes

(a:b)!(c:d)=max a c:b!d
[]!x=x
y!_=y
iter((:).length<*>foldr(!)[]).([]<$)

Try it online!

Here we represent ragged lists as free monads of lists.

We define (!) which takes the pairwise maximum of two lists. This is almost just zipWith max, but that takes the length of the shorter list, and we need the length of the longer one defaulting to zero when empty.

That makes up the majority of the code. The rest of the code is the point free function that implements the answer.

First we have ([]<$) this replaces every terminal element with [] which is it's dimensions. This is the base case for our recursion. Then we have the recursive step which is (:).length<*>foldr(!)[]. Which is just point-free for \x -> length x:foldr(!)[]x or the length of the list x and the pairwise maximum of all its elements.

We combine the inductive step and the base case with iter from the free library to make it work. iter is just induction on free monads.

Answer 9

Haskell + hgl, 21 bytes

shp[]$l*:*rF(zd' ma)i

Explanation

• zd' ma takes the pairwise maximum of two lists. zdm ma would also work.
• rF(zd' ma)i folds the above across a list of lists. lf(zd' ma)i also works.
• (l*:*) takes the a function and a list and prepends the length of the list onto the result of the function.
• l*:*rF(zd' ma)i forms the inductive step of our algorithm. It takes a list of dimensions, calculates the pairwise maximum and then adds the length onto the front of that result.
• shp[] takes an inductive step and replaces everything with [] as a base case.

So altogether this implements a basic recursive algorithm.

Reflection

There's a lot here that might be useful to combine.

• frF i<zd' could be useful, if I had a function zzD=frF i<zd the answer would be shp[]$l*:*zzD ma saving 5 bytes here. It might in general be useful to have versions of the zip functions that operate over a foldable rather than just combining two elements.
• shp i might be useful as a standalone it seems like the most common arguments for shp would be [] and 0, which are both i.
• (l*:*) is something I think I've done in the past might be useful to give it a name.

Answer 10

Python3, 202 bytes:

lambda x:(K:=lambda d,j={}:[max(j[i])for i in j]if[]==d else K(d[1:],{**j,d[0][0]:j.get(d[0][0],[])+[d[0][1]]}))(f(x))
f=lambda x,c=0:[[c,len(x)]]+[j for k in x for j in(f(k,c+1)if list==type(k)else[])]

Try it online!

Answer 11

05AB1E, 30 bytes

"Ddi¯ëИÊi®δ.VDU0ζ€àXgšëg¸"©.V

Try it online or verify all test cases.

Explanation:

"..."              # Push the recursive string explained below
     ©             # Store it in variable `®` (without popping)
      .V           # Eval and execute it as 05AB1E code
                   # (using the implicit input-list as initial argument)
                   # (after which the result is output implicitly)

  i                # If
D                  # a copy of the current value
 d                 # is >= 0 (thus an integer):
   ¯               #  Push an empty list
ë   i              # Else-if
 Ð                 # a copy of the current value
   Ê               # is NOT equal to
 И                # a flattened copy of the current value (thus it's a ragged
                   # list):
      δ            #  Map over each inner list:
     ® .V          #   And do a recursive call by 05AB1E-executing string `®`
         DU        #  Store a copy of the result in variable `X`
            ζ      #  Zip/transpose; swapping rows/columns,
           0       #  with 0 as filler for unequal length lists
              à    #  Get the maximum
             €     #  of each inner list
                 š #  And then prepend to this list
                g  #  the length
               X   #  of variable `X`
ë                  # Else (thus it's a flattened list):
 g                 #  Push its length
  ¸                #  Wrap it into a list

Answer 12

Jelly, 10 bytes

WẎƬṖḟFẈṀƲ€

A monadic Link that accepts a ragged list of integers and yields a list of non-negative integers giving the depth-wise dimensions as required.

Try it online!

How?

WẎƬṖḟFẈṀƲ€ - Link: ragged list of integers, L
W          - wrap L in a list
  Ƭ        - (starting with that) collect up inputs while distinct applying:
 Ẏ         -   tighten (drop first level of the inner lists)
   Ṗ       -   pop (remove the final input)
         € - for each:
        Ʋ  -   last four links as a monad:
     F     -     flatten (to a list of integers)
    ḟ      -     filter these out (only filters out integers at depth 1)
      Ẉ    -     length of each
       Ṁ   -     maximum

Answer 13

Charcoal, 34 bytes

⊞υＡＷυ«≔υθ≔⟦⟧υＦθＦΦκ⁼λ⁺⟦⟧λ⊞υλ⟦Ｉ⌈ＥθＬκ

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

⊞υＡ

Push the input list to the predefined empty list.

Ｗυ«

Repeat until the list of lists is empty.

≔υθ≔⟦⟧υ

Save it and start a new list.

ＦθＦΦκ⁼λ⁺⟦⟧λ⊞υλ

Push all of the elements of the lists that are themselves lists to the list.

⟦Ｉ⌈ＥθＬκ

Output the maximum length of all of the original lists on its own line.