# Determine the depth of an array

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 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
``````
-
After discussion in chat I've decided to allow length built-ins, because some languages require them to iterate over an array cleanly. – Martin Ender Feb 8 at 23:09
Just for general education: `≡` is APL's built-in primitive for exactly this. – Adám Feb 9 at 16:09
@MartinBüttner I've run into a tiny problem. I started doing this in java, unfourtunetly when testing inputs the commas are causing it to split the inputs into multiple command line arguments rather then one. Can I use the escape character `\ ` in the inputs? EDIT: nevermind just tried it like that. That doesn't even work either. Darn can I not use CMD args? – Ashwin Gupta Feb 10 at 5:21
@AshwinGupta can't you wrap the command line argument in quotes? You can also read input from STDIN or submit a function that takes an actual array object as a parameter. – Martin Ender Feb 10 at 10:39
@MartinBüttner oh I didn't know that quotes thing I'll try it out. Currently just using Scanner. (System.in). I believe that is a form of STDIN? – Ashwin Gupta Feb 10 at 22:02

# K, 4 bytes

``````#,/\
``````

In K, `,/` will join all the elements of a list. The common idiom `,//` iterates to a fixed point, flattening an arbitrarily nested list completely. `,/\` will iterate to a fixed point in a similar way, but gather a list of intermediate results. By counting how many intermediate results we visit before reaching the fixed point (`#`), we get the answer we want: the maximum nesting depth.

"Count of join over fixed-point scan".

In action:

`````` (#,/\)'(,1
1 2 3
,1 2 3
(3;(3;,3;3);3)
,((,1;2);(3;,4)))
1 1 2 3 4
``````
-
Nice! Your solution isn't specific to k5, btw. It works equally well in k4. – mollmerx Feb 9 at 12:56

# Retina, 10

• Saved 1 byte thanks to @ӍѲꝆΛҐӍΛПҒЦꝆ
• Saved 14 extra bytes thanks to @MartinBüttner
```+`\w|}{

{
```

Here the input format is a bit contrived - `_` characters are used for list separators, so an input would look like this `{1_{{2_3_{{4}_5}_6_{7_8}}_9_{10_{{{11}}}}_12_13}_14}`

• Stage 1 - repeatedly remove `}{` and all other `\w` characters. This has the effect of a) making all lists at all levels consist of only one element and b) removing all non-list-structural characters.
• Stage 2 - count remaining `{`. This gives the deepest level of nesting.

Try it online.

If that's too much of a stretch, then the previous answer was:

# Retina, 13

Assumes lists are contained in curly braces `{}`.

```+`[^}{]|}{

{
```
-
Your code can be shortened to 13 bytes (11 if you stretch the input format a bit). Let me know if you want a hint. :) (I don't really want to post it myself, since it's virtually the same solution.) – Martin Ender Feb 9 at 7:33
It's two things. a) You can save a byte or so by slightly tweaking the input format. b) You can save a lot of bytes regardless of that... can you find a shorter (and much simpler) solution if you try not to handle multiple test cases in a single run? – Martin Ender Feb 9 at 18:19
I didn't even think of that. That's amount byte saved then. My change to the input format would have been even weaker. Regarding b) remember what Retina's very first and simplest mode of operation was? – Martin Ender Feb 9 at 18:35
yep. My a) was referring to removing spaces from the input though. And you can then save two more bytes by using `_` instead of `,` but that might be a bit of a stretch. – Martin Ender Feb 9 at 18:37
@MartinBüttner Nice idea! Agreed - `_` separators might be too contrived. So I'm leaving both versions in the answer – Digital Trauma Feb 9 at 18:47

## Python 2, 33 bytes

``````f=lambda l:l>{}and-~max(map(f,l))
``````

Recursively defines the depth by saying the depth of a number is 0, and the depth of a list is one more than the maximum depth of its elements. Number vs list is checked by comparing to the empty dictionary `{}`, which falls above numbers but below lists on Python 2's arbitrary ordering of built-in types.

-
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

# Pyth - 1110 7 bytes

1 bytes saved thanks to @Dennis

4 bytes saved thanks to @Thomas Kwa

``````eU.usNQ
``````

Keeps on summing the array till it stops changing, which means its just a number, does this cumulatively to save all the intermediate results and gets length by making a urange with the same length as list and taking the last element.

-
`m!!d` can become `&R1`. – Dennis Feb 8 at 22:21
@Dennis cool, that's smart – Maltysen Feb 8 at 22:21
@ThomasKwa `l` isn't allowed in OP. – Maltysen Feb 8 at 22:25
@ThomasKwa that is really smart, thanks! – Maltysen Feb 8 at 22:31
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

``````'['#x=x-1
']'#x=x+1
_#x=x
maximum.scanr(#)0
``````

Usage example: `maximum.scanr(#)0 \$ "[1, [[3]], [5, 6], [[[[8]]]], 1]"` -> `5`.

Haskell doesn't have mixed lists (`Integer` mixed with `List of Integer`), so I cannot exploit some list detection functions and I have to parse the string.

Im starting at the right with `0` and add 1 for every `]`, subtract 1 for every `[` and keep the value otherwise. `scanr` keeps all intermediate results, so `maximum` can do it's work.

-

# MATL, 11 14 15 bytes

``````'}{'!=dYsX>
``````

Curly braces are used in MATL for this type of arrays. Anyway, the input is taken and processed as a string, so square brackets could equally be used, modifying the two characters in the code.

Try it online!

``````          % implicitly take input as a string (row array of chars)
'}{'!     % 2x1 (column) char array with the two curly brace symbols
=         % 2-row array. First / second row contains 1 where '}' / '{' is found
d         % second row minus first row
Ys        % cumulative sum of the array
X>        % maximum of the array
% implicitly display result
``````
-
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

# Octave, 29 bytes

``````@(a)max(cumsum(92-(a(a>90))))
``````

Maps `[` to 1 and `]` to -1, then takes the max of the cumulative sum.

Input is a string of the form

``````S6 = '[1, [[3]], [5, 6], [[[[8]]]], 1]';
``````

Sample run on ideone.

-
Should you use `{`, `}`? The Octave equivalent to the arrays in the OP are cell arrays, I think – Luis Mendo Feb 9 at 10:42
@LuisMendo No, because that's 2 extra bytes :) Plus, since I never actually create the array, simply parse the input string, I don't think it matters. But you've reminded me to add the expected input to my answer. – beaker Feb 9 at 16:20
True! Longer ASCII code – Luis Mendo Feb 9 at 17:16
@LuisMendo Actually, 1 byte longer. That second comparison only needs to be greater than '9'. But you get the idea :D – beaker Feb 9 at 17:20

# Julia, 55 26 bytes

``````f(a)=0a!=0&&maximum(f,a)+1
``````

This is a recursive function that accepts a one-dimensional array with contents of type `Any` and returns an integer. When passing an array to the function, prefix all brackets with `Any`, i.e. `f(Any[1,Any[2,3]])`.

The approach is pretty simple. For an input a, we multiply a by 0 and check whether the result is the scalar 0. If not, we know that a is an array, so we apply the function to each element of a, take the maximum and add 1.

Saved 29 bytes thanks to Dennis!

-
Dat golf. <filler> – El'endia Starman Feb 10 at 7:27

# JavaScript (ES6), 35 bytes

``````f=a=>a[0]?Math.max(...a.map(f))+1:0
``````

## Explanation

Recursive function that returns the maximum depth of an array, or `0` if passed a number.

``````var solution =

f=a=>
a[0]?                   // if a is an array
Math.max(...a.map(f)) // return the maximum depth of each element in the array
+1                    // add 1 to increase the depth
:0                      // if a is a number, return 0

// Test cases
result.textContent =
`[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`
.split`\n`.map(t=>(c=t.split`->`.map(p=>p.trim()),c[0]+" == "+c[1]+": "+(solution(eval(c[0]))==c[1]?"Passed":"Failed"))).join`\n```````
``````<input type="text" id="input" value="[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]" />
<button onclick="result.textContent=solution(eval(input.value))">Go</button>
<pre id="result"></pre>``````

-
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

# Mathematica, 27 20 bytes

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

Simple recursive function.

-
It's possible to void the `If`, saving 7 bytes. (Let me know if you want a hint.) – Martin Ender Feb 9 at 7:39
@MartinBüttner I give up... A `Replace`-based solution is at least as long as this one... – LegionMammal978 Feb 9 at 12:16
`Map`ping over an integer is a no-op: `Max[#0/@#]+1&[0#]-1&`. The `-1` can also go inside the inner call like `...&[0#-1]&`. – Martin Ender Feb 9 at 12:30

## Ruby, 53 bytes

``````i=0;p gets.chars.map{|c|i+=('] ['.index(c)||1)-1}.max
``````

Input from STDIN, output to STDOUT.

``````i=0;                 initialize counter variable
p                    output to STDOUT...
gets                 get line of input
.chars               enumerator of each character in the input
.map{|c|             map each character to...
i+=                  increment i (and return the new value) by...
('] ['.index(c)||1)  returns 0 for ], 2 for [, 1 for anything else
-1                   now it's -1 for ], 1 for [, 0 for anything else
therefore: increment i on increase in nesting, decrement i
on decrease, do nothing otherwise
}.max                find the highest nesting level that we've seen
``````
-
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

# Jelly, 10 7 bytes

``````¬;/SÐ¿L
``````

### How it works

``````¬;/SÐ¿L  Main link. Input: A (list)

¬        Negate all integers in A. This replaces them with zeroes.
Ð¿   Cumulative while loop.
S       Condition: Compute the sum of all lists in A.
If the sum is an integer, it will be zero (hence falsy).
;/        Body:      Concatenate all lists in A.
L  Count the number of iterations.
``````

### Update

While writing this answer, I noticed that Jelly behaves rather weirdly for ragged lists, because I calculated the depth of a list as the incremented minimum of depths of its items.

This has been addressed in the latest version, so the following code (6 bytes) would work now.

``````¬SSÐ¿L
``````

This sums the rows of the array instead of concatenating them.

-

# Mathematica, 18 bytes

``````Max@#+1&//@(0#-1)&
``````
-

## Python 3, 42 39 bytes

-3 bytes thanks to Sp3000

This is essentially a port of xnor's Python 2 solution:

``````f=lambda l:"A"<str(l)and-~max(map(f,l))
``````

Unfortunately, `[] > {}` returns an `unorderable types` error, so that particular clever trick of xnor's cannot be used. In its place, `-0123456789` are lower in ASCII value than `A`, which is lower than `[]`, hence the string comparison works.

-

## CJam (15 bytes)

``````q~{__e_-M*}h],(
``````

Online demo

### Dissection

``````q~      e# Read line and parse to array
{       e# Loop...
_     e#   Leave a copy of the array on the stack to count it later
_e_-  e#   Remove a flattened version of the array; this removes non-array elements from
e#   the top-level array.
M*    e#   Remove one level from each array directly in the top-level array
}h      e# ...until we get to an empty array
],(     e# Collect everything together, count and decrement to account for the extra []
``````

For the same length but rather more in ugly hack territory,

``````q'[,-{:~_}h],2-
``````
-
`s/ugly/beautiful/` – Dennis Feb 10 at 20:05
@Dennis, I was referring specifically to the use of `'[,-` to strip the string down to `[]`, which relies on the contents being limited. The approach which flattens works regardless of the contents of the array. – Peter Taylor Feb 10 at 22:05

## Pyth, 15 13 bytes

-2 bytes by @Maltysen

``````eSm-F/Ld`Y._z
``````

Counts the difference between the cumulative counts of `[` and `]`, and takes the maximum. `Y` is the empty array, and its string representation (```) is conveniently `[]`.

Try it here.

-
Length built-ins are now allowed if it helps. – Martin Ender Feb 8 at 23:10

# 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
{            }%              map this block on the string
_91=\93=-                  1 if it's an opening bracket, -1 if closing
+_                cumulative sum
:e>           fold maximum function
``````
-

## Minkolang 0.15, 3129 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 ]
d    Duplicate top of stack for the running total
``````
-

# Sed, 40 characters

(39 characters code + 1 character command line option.)

``````s/[^][]+//g
:;s/]\[//;t
s/]//g
s/\[/1/g
``````

Input: string, output: unary number.

Sample run:

``````bash-4.3\$ sed -r 's/[^][]+//g;:;s/]\[//;t;s/]//g;s/\[/1/g' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
111111
``````

## Sed, 33 characters

(32 characters code + 1 character command line option.)

If trailing spaces are allowed in the output.

``````s/[^][]+//g
:;s/]\[//;t
y/[]/1 /
``````

Input: string, output: unary number.

Sample run:

``````bash-4.3\$ sed -r 's/[^][]+//g;:;s/]\[//;t;y/[]/1 /' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
111111
``````
-

# PHP, 8472 64 bytes

``````for(;\$c=\$argv[1][+\$i++];)\$c>A&&\$t=max(\$t,\$z+=92-ord(\$c));echo\$t;
``````

Run like this:

``````php -r 'for(;\$c=\$argv[1][+\$i++];)\$c>A&&\$t=max(\$t,\$z+=92-ord(\$c));echo\$t;' "[1, [[3]], [5, 6], [[[[8]]]], 1]"
``````
• Saved 12 bytes by just counting braces of the string representation instead
• Saved 8 bytes by simplifying string comparisons and using ordinal number of the char in case of `[` and `]`
-

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

-

# 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
``````
-

# 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
``````
-

# C, 98 69 bytes

29 bytes off thanks @DigitalTrauma !!

``````r,m;f(char*s){for(r=m=0;*s;r-=*s++==93)r+=*s==91,m=r>m?r:m;return m;}
``````

Takes an string as input and return the result as integer.

Live example in: http://ideone.com/IC23Bc

-

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

-

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

-

# Perl 6, 53 bytes

The closure:

``````{my (\$m,\$d);/[\[{\$d++;\$m=max \$m,\$d}|\]{\$d--}|.]*/;\$m}
``````

Needs an argument, eg:

``````{my (\$m,\$d);/[\[{\$d++;\$m=max \$m,\$d}|\]{\$d--}|.]*/;\$m}("[[[3]][2]]")
3
``````

Explanation:

``````{ my (\$m,\$d);                 # start closure, declare variables

/                           # start regex match

[                          # start (non-capturing) group

\[ {\$d++;\$m=max \$m,\$d} | # match [ and track depth; OR

\] {\$d--}              | # match ] and track depth; OR

.                        # match one character

]*                         # repeat group

/;                          # end regex

\$m                          # return max depth
}
``````
-

## 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;}
``````
-

# 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
``````
-