Determine the depth of an array

Question

A simple challenge for your Monday evening (well, or Tuesday morning in the other half of the world...)

You're given as input a nested, potentially ragged array of positive integers:

[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]

Your task is to determine its depth, which is the greatest nesting-depth of any integer in the list. In this case, the depth of 11 is 6, which is largest.

You may assume that none of the arrays will be empty.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient list or string format that supports non-rectangular arrays (with nested arrays of different depths), as long as the actual information isn't preprocessed.

You must not use any built-ins related to the shape of arrays (including built-ins that solve this challenge, that get you the dimensions of a nested array). The only exception to this is getting the length of an array.

Standard code-golf rules apply.

Test Cases

[1]                                                               -> 1
[1, 2, 3]                                                         -> 1
[[1, 2, 3]]                                                       -> 2
[3, [3, [3], 3], 3]                                               -> 3
[[[[1], 2], [3, [4]]]]                                            -> 4
[1, [[3]], [5, 6], [[[[8]]]], 1]                                  -> 5
[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14] -> 6
[[[[[[[3]]]]]]]                                                   -> 7

Answer 1

CJam, 19 22 23 bytes

0l{_91=\93=-+_}%:e>

Similar idea to my MATL answer.

Thanks to Peter Taylor for removing 3 bytes

Try it here

0                            push a 0
l                            read line as string
{            }%              map this block on the string
  _91=\93=-                  1 if it's an opening bracket, -1 if closing
           +_                cumulative sum
               :e>           fold maximum function

Answer 2

Perl 5, 34 bytes

32, plus two for -p

{s&]\[|[^][]&&g&&redo}$_=@a=/]/g

Stolen from Digital Trauma's Retina answer… which is 26% shorter than this. :-)

Or, equally:

{s&]\[|[^][]&&g&&redo}$_=y///c/2

Answer 3

Ruby, 51 characters

(Started as improvement suggestion for Doorknob's Ruby answer but ended differently. So I posted it as separate answer. Upvotes for the depth counting idea (?\\<=>$&, descending from '] ['.index(c)) should go to the original answer.)

m=i=0
gets.gsub(/\[|\]/){m=[m,i+=?\\<=>$&].max}
p m

Input: string, output: number.

Sample run:

bash-4.3$ ruby -e 'm=i=0;gets.gsub(/\[|\]/){m=[m,i+=?\\<=>$&].max};p m' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
6

Answer 4

Minkolang 0.15, 31 29 24 bytes

Overhauled my algorithm upon inspiration by Luis Mendo's CJam answer and saved 5 bytes!

od5&j$ZN.d"["=$r"]"=~++d

Try it here!

Explanation

Essentially, what this code does is keep a running total with +1 for each [ and -1 for each ], keeping track of the maximum value reached, outputting that maximum at the end. Looping is handled by the toroidal nature of Minkolang's codebox.

od           Take character from input and duplicate it (0 if input is empty)
  5&         Pop top of stack and skip the following five spaces if 0
    j$Z      Push the maximum value of the stack
       N.    Output as number and stop.

  d                  Duplicate top of stack for character tests
   "["=              +1 if the character is [
       $r            Swap top two items of stack
         "]"=~       -1 if the character is ]
              ++     Add twice
                d    Duplicate top of stack for the running total

Answer 5

Ruby, 41 characters

f=->a,d=1{a.map{|e|f[e,d+1]rescue d}.max}

Parameter: array, return: number.

Sample run:

2.1.5 :001 > f=->a,d=1{a.map{|e|f[e,d+1]rescue d}.max}
 => #<Proc:0x0000000214d258@(irb):1 (lambda)> 

2.1.5 :002 > f[[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]]
 => 6 

Answer 6

Oracle SQL 11.2, 133 bytes

SELECT MAX(d)FROM(SELECT SUM(DECODE(SUBSTR(:1,LEVEL,1),'[',1,']',-1,0))OVER(ORDER BY LEVEL)d FROM DUAL CONNECT BY LEVEL<=LENGTH(:1));

Un-golfed

SELECT MAX(d)
FROM   (
         SELECT SUM(DECODE(SUBSTR(:1,LEVEL,1),'[',1,']',-1,0))OVER(ORDER BY LEVEL) d 
         FROM   DUAL 
         CONNECT BY LEVEL<=LENGTH(:1)
       );

The CONNECT BY creates one row per character in the input string.

The SUBSTR isolates the character corresponding to the row number.

The DECODE translates each '[' to 1, each ']' to -1 and every other character to 0.

The analytic SUM sums each 1, -1 and 0 from the preceding rows, including the current row;

The MAX sums is the depth.

Answer 7

Java 8, 95

This is a lambda expression for a ToIntFunction<String>. Input is taken as a String in the OP's examples format.

s->{int d=e=-1;for(String t:s.split("[")){d=++e>d?e:d;e-=t.split("]",-1).length()-1;}return d;}

fairly straightfoward. Split the string using [ as the delimiter. For each of them, increment the counter e and compare it with the counter d, keeping the larger of them in d. Then split the current iteration's string using ] as the delimiter this time and subtract the number of extra splits from e.

Answer 8

Ruby, 42 characters

f=->a{a==a.flatten(1)?1:f[a.flatten(1)]+1}

Example:

irb(main):001:0> f.call([[[1,2],[2,3]],[[3,4],[5]]])
=> 3

And it's actually readable. :)

Answer 9

Swift - 76 bytes

func d(_ a:[Any])->Int{return 1+(a.map{$0 is Int ?0:d($0 as![Any])}).max()!}

A recursive function that returns one plus the max of all non ints in the array using map.

Answer 10

Lua, 101 100 bytes

d,c=0,0 print((...):gsub(".",function(s)c=s=='['and c+1 or s==']'and c-1 or c d=c>d and c or d end))

Try it online!

How it works

-- Passed To Command Line: "[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]"

-- Deepest Sub-Array Count, Current Depth
deepest, current = 0, 0

-- We abuse gsub() to iterate over every character in the input string and run a function for it
(...):gsub(".", function(s)
    -- The current depth is incremented if s (the current character) is equal to [, OR decremented if s is equal to ], OR left alone
    current = (s == '[' and current+1) or (s == ']'and current-1) or current
    -- If current is > deepest then deepest = current else deepest = current, we're using boolean logic like a ternary operator
    deepest = current > deepest and current or deepest
end)

print(deepest)
```

Answer 11

Haskell + hgl, 20 bytes

y=dPF(p 0)$P1<mx<m y

Takes input as a free monad of lists (Free List a).

Explanation

A ragged list can contain either a terminal element or a list of more ragged lists.

dPF is a function which takes a function to convert terminal elements and a function to convert lists of ragged lists and uses them to convert a ragged list. This is captured in the type signature:

dPF :: (a -> b) -> ([Free [] a] -> b) -> Free [] a -> b

We give it two functions, for terminal elements it is very simple, terminal elements always have depth 0, so we give it p 0, meaning always return zero.

For lists we get the maximum depth of each element and add 1 using the function we are defining recursively. P1<mx<m y.

Reflections

• We spend 6 bytes to envoke dpF properly dPF()$. This should have an infix function. Even if the operator precedence was bad it would have saved a byte.
• It's not an issue here because the lists can't be empty, but we should have a maximum with default function.
• Max with map also seems common enough to implement.
• Might have not saved bytes here, but this is the second time I have wanted a fix function. Should probably add that before I hit a place where I really need it.

Answer 12

tinylisp, 48 bytes

(load library
(d f(q((x)(i(v x)0(+ 1(max(map f x

Try it online!

-11 from Dlosc

gets depth of a quoted list.

Answer 13

Wolfram Language (Mathematica), 16 bytes

Max[#0/@-1^#]+1&

Try it online!

The relatively low precedence of prefix - means -1^# is evaluated before the high-precedence /@.

Answer 14

Perl 6, 70 bytes

Whole program that reads the given examples terminated with newline or EOF from STDIN.

# perl6 % <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'

my $i;dd [max] lines.comb.map:{$i++when '[';$i--when ']'}

lines takes text line by line from STDIN and returns a list of Str. Calling .comb on a list will convert that into a Str and then split it into graphenes. Any block in Perl 6 is born with one positional argument that ends up in $_. map called with any callable expect it to have one positional argument. What is nice because when ']' is short for when $_ ~~ ']'. The returned list is fed to [max] and reduced to it's biggest value.

Answer 15

C#, 99 Bytes

int f(string s){int m=0,w=0;foreach(char c in s){if(c=='[')w++;if(c==']')w--;if(w>m)m=w;}return m;}

Answer 16

Axiom 106 bytes

RL(a:Union(List(Any),Any)):INT==(a case List(Any)=>(g:List(Any):=a;r:=1;for i in g repeat r:=r+RL(i);r);0)

ungolf

RL(a:Union(List(Any),Any)):INT==
  a case List(Any)=>
          g:List(Any):=a
          r:=1
          for i in g repeat r:=r+RL(i)
          r
  0

results

(3) -> for i in[[1],[1,2,3], [[1,2,3]], [3,[3,[3],3],3]]repeat output[i, RL(i)]
   [[1],1]
   [[1,2,3],1]
   [[[1,2,3]],2]
   [[3,[3,[3],3],3],3]

Answer 17

C++14, 72 70 67 bytes

-2 bytes for removing the curly brackets at for and -3 bytes for replacing m=l>m?l:m with m+=l>m.

As unnamed lambda returning via reference parameter:

[](auto&s,int&m){int l=m=0;for(auto c:s)l+=(c==91)-(c==93),m+=l>m;}

s can be std::string or char[]

Ungolfed and usage:

#include<string>
#include<iostream>

auto f=
[](auto&s,int&m){
 int l=m=0;
 for(auto c:s)
  l+=(c==91)-(c==93),
  m+=l>m;     
}
;


int main(){
 std::string S[] = {
  "[1]",
  "[1, 2, 3]",
  "[[1, 2, 3]]",
  "[3, [3, [3], 3], 3]",
  "[[[[1], 2], [3, [4]]]]",
  "[1, [[3]], [5, 6], [[[[8]]]], 1]",
  "[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]",
  "[[[[[[[3]]]]]]]"
 };

 for (auto s:S){
  int m;
  g(s,m);
  std::cout << m << std::endl;
 }

}

Answer 18

Clojure, 57 bytes

(fn[s](apply max(reductions +(map #({\[ 1 \] -1}% 0)s))))

Also based on parsing a string:

(f "[3, [3, [3], 3], 3]")

Answer 19

R: 53 bytes.

d=function(L) ifelse(is.list(L),max(sapply(L,d))+1,0)

Recursive function, it adds one point everytime it finds an inner list. It chooses only the element with the maximum depth...

Answer 20

Scala, 56 bytes

val f:Any=>Int={case l:Seq[_]=>l.map(f).max+1 case _=>0}

Make sure the inputs are Seqs and not Lists (I used Seq to save a byte).

Try it online!

Answer 21

Pip, 14 bytes

{a*0&1+MX:fMa}

Try it online!

Explanation

A recursive function that takes the list as its argument.

{            }  Anonymous function:
 a               The first argument
  *0             Times 0
                 (This gives 0 if the argument is a number, or a [possibly nested]
                  list of 0s if the argument is a list)
    &            Logical AND (short-circuiting)
                 (Since 0 is falsey and non-empty lists are truthy in Pip, this
                  halts the recursion and returns 0 if we've reached the inside of
                  the innermost lists; otherwise...)
          fMa    Map this function recursively to each element of a
       MX:       Get the max (: is a no-op to manipulate operator precedence)
     1+          Add 1

Answer 22

C (gcc), 62 bytes

n;m;f(char* s){for(;*s;s++)*s^91?*s^93?0:n--:++n>m?m=n:0;m=m;}

Try it online!

Answer 23

Nekomata, 2 bytes

ˡ∑

Attempt This Online!

ˡ∑
ˡ   Loop until failure and return the number of iterations:
 ∑      Sum

Answer 24

Uiua, 11 bytes

-2⧻{⍥⊸/◇⊂∞}

Try it!

Repeatedly reduce with conjoin (/◇⊂) until a fixed point (⍥...∞), then get the number of iterations (⧻{...⊸...}) and subtract 2 (-2).