18
\$\begingroup\$

As input you will be given a ragged list of positive integers containing at least one integer at some level. For example:

[[],[[1,2,[3]]],[]]

You should output the depth of the least deep integer. For example if the input is just a list of integers, then the every integer is 1 level deep so the answer is 1. There may be a tie for the crown of least deep but it doesn't matter since we only need to output the depth not the least deep integer itself.

This is so answers will be scored in bytes with fewer bytes being the goal.

Test cases

[1] -> 1
[[[[1]]],[]] -> 4
[[[[1]]],[[]]] -> 4
[[[[1]]],[1]] -> 2
[[[6],1,2,3,[4,5]]] -> 2
[[],[[1,2,[3]]],[]] -> 3
[[[[]]],[2]] -> 2
\$\endgroup\$
3
  • 3
    \$\begingroup\$ The possibility of empty lists at any level really negates the point of the "containing at least one integer at some level" limit, because when the problem is done recursively, that no longer holds and the special case must be handled anyway. \$\endgroup\$
    – pxeger
    Jan 13 at 17:45
  • 7
    \$\begingroup\$ @pxeger The restriction there is to make the output format simpler, no "output -1 if there is none" or anything like that. It is not in place to make the problem easier. \$\endgroup\$
    – Wheat Wizard
    Jan 13 at 18:04
  • 2
    \$\begingroup\$ @pxeger Actually, it doesn't. \$\endgroup\$
    – loopy walt
    Jan 14 at 1:52

19 Answers 19

7
\$\begingroup\$

Python 2, 35 bytes

f=lambda a:min(a)<[]or-~f(sum(a,a))

Attempt This Online!

Old Python 2, 36 bytes

f=lambda a:min(a)<[]or-~f(sum(a,[]))

Attempt This Online!

Python, 45 bytes

f=lambda a:int in map(type,a)or-~f(sum(a,[]))

Attempt This Online!

Old Python, 46 bytes

f=lambda a:int in map(type,a)or 1+f(sum(a,[]))

Attempt This Online!

Outputs True for 1. Does a bfs for integers.

Details:

The bfs, or breadth first search, is implemented as follows: If there is an int at level 1 return 1. If not there are only lists; we can sum (concatenate) them; this eliminates depth 1 nodes, combines all former depth 2 nodes into the new depth 1 tier and pulls each level below up one tier. We can now recursively repeat until we find the first integer.

Shortcuts in Python 2:

Python 2 but not Python 3 has a total ordering on all objects, in particular, every list is greater than every integer. The type check can therefore be cheaply done using min.

And one dirty trick:

The sum function is meant for numbers. If you apply it to lists you explicitly have to set the starting value from 0 to []. But, technically, any list will do, so to save a byte we use a itself instead. While this is rather dirty one can check that it leaves the min unchanged.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Wow, this is a genius reinterpretation of the obvious algorithm for the challenge! \$\endgroup\$
    – pxeger
    Jan 14 at 15:39
  • \$\begingroup\$ I think I understand how this works, but could you add an explanation? It's not obvious, particularly to those who are used to thinking in Python 3 now. \$\endgroup\$
    – DLosc
    Feb 1 at 21:58
6
\$\begingroup\$

Jelly, 4 bytes

ŒJẈṂ

Try It Online!

-1 byte thanks to Razetime

ŒJẈṂ    Main Link
ŒJ      Get the multidimensional index of each scalar value
  Ẉ     Length of each coordinate = depth of each value
   Ṃ    Minimum
\$\endgroup\$
3
  • 4
    \$\begingroup\$ is L€ right \$\endgroup\$
    – Razetime
    Jan 13 at 13:41
  • 2
    \$\begingroup\$ The right language for the job. ŒJ is a very useful builtin here. 05AB1E doesn't even have a builtin to get all indices of a certain element in a regular list, let along a multi-dimensional list, haha. \$\endgroup\$ Jan 13 at 13:52
  • \$\begingroup\$ @Razetime oh yeah ofc \$\endgroup\$
    – hyper-neutrino
    Jan 13 at 14:44
3
\$\begingroup\$

R, 66 60 57 bytes

f=function(l)"if"(all(Map(is.list,l)),1+f(unlist(l,F)),1)

Try it online!

-3 bytes thanks to pajonk.

\$\endgroup\$
4
  • \$\begingroup\$ I have tried to develop a recursive solution based on your while code, but couldn't make it work. Congratulations on succeeding in doing it yourself! \$\endgroup\$
    – pajonk
    Jan 13 at 20:03
  • \$\begingroup\$ Apparently, all accepts lists of depth 1 and works just as well, so -3 bytes, \$\endgroup\$
    – pajonk
    Feb 1 at 19:57
  • \$\begingroup\$ @pajonk there should probably be a tip on some of the really useful coercions in R, and a corresponding one on all the really frustrating ones too! \$\endgroup\$
    – Giuseppe
    Feb 1 at 20:28
  • \$\begingroup\$ I've added a specific tip for this situation. If you have something more broad in mind, please don't hesitate to add it. \$\endgroup\$
    – pajonk
    Feb 1 at 20:49
2
\$\begingroup\$

Wolfram Language (Mathematica), 16 bytes

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

Try it online!

Abuses the fact that f/@a = a for any atomic a.

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

JavaScript, 35 bytes

f=x=>x.at?Math.min(...x.map(f))+1:0

x.at is a method (truthy) if x is an Array (requires a newish browser) and is undefined (falsy) if x is a Number. The rest is straightforward.

f=x=>x.at?Math.min(...x.map(f))+1:0
testcases = 
[[1], [[[[1]]],[]], [[[[1]]],[1]], [[[6],1,2,3,[4,5]]], [[],[[1,2,[3]]],[]]]
console.log(testcases.map(f))

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

Vyxal, 6 bytes

⁽LÞZfg

Try it Online!

Can’t be bothered trying to add an explanation on mobile, feel free to edit one in.

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

APL(Dyalog Unicode), 27 bytes SBCS

{⌊/(⍵∊⎕d)/+\1 ¯1 0['[]'⍳⍵]}

Try it on APLgolf!

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

Vyxal, 16 14 13 bytes

≬ƛƛ;⁼;A⁽ÞfŀL›

Try it Online!

Feels too long. Vyxal parsing isn't janky at all why would you even think that?

Explained

≬ƛƛ;⁼;A⁽ÞfŀL›
≬......⁽..ŀ   # call function ≬ on the input until the result of function ⁽ is falsey
≬             # a function that: (this is the predicate for ŀ)
 ƛƛ;⁼;        #   checks whether each item is a list - an empty map over a list equals itself
      A       #   and returns whether all items are truthy under that
              # ----------------------------------------------------
              # N.B. The ≬ modifier (next 3 elements as a lambda) is used here because of the way map lambdas are parsed:
              # Rather than treating them as their own structure type internally, 
              # they are converted to a lambda structure 
              # followed immediately by a token representing the `M` (map) element.
              # This means that map lambdas are considered to be 2 elements
              # ‡ doesn't work because it doesn't catch the extra `M` 
              # token generated while parsing.
              # ------------------------------------------------------
        ⁽Þf   # a function that flattens its argument by 1 depth
           L› # the length of the list collected by ŀ + 1
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

d[¼D1å#€`}¾

Try it online or verify all test cases.

Explanation:

d       # Transform all integers to 1s in the (implicit) input (with >=0 check)
 [      # Loop indefinitely:
  ¼     #  Increase the counter variable (implicitly starts at 0)
  D     #  Duplicate the current list
   1å   #  Check if it contains a 1
     #  #  If it does: stop the infinite loop
   €`   #  Flatten the list one level down
 }¾     # After the loop, push the counter variable
        # (after which it is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 32 bytes

\d+
$'¶
1A`
+`[^][¶]|\[]

O`
\G]

Try it online! Link includes test cases. Explanation:

\d+
$'¶
1A`

Get all the suffixes of the integers.

+`[^][¶]|\[]

Delete everything except unbalanced ]s.

O`
\G]

Output the smallest depth.

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

Ruby, 43 bytes

g=->l{l.any?{|x|x*0==0}?1:1+g[l.flatten 1]}

Try it online!

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

Julia 1.0, 36 30 bytes

!l::Int=0
!l=1+min(Inf,.!l...)

Try it online!

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

Brachylog, 8 bytes

;.≜∋ⁱ⁾İ∧

Try it online!

Cannot be golfed to ∋ⁱ↖.İ∧≜, as failing to pre-label the output variable causes it to hang--perhaps because it gets stuck exploring the elements (digits) of the integers themselves ad infinitum?

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

Whython, 26 bytes

f=lambda l:1+f(sum(l,l))?1

Idea taken from loopy walt's Python 2 answer, which you should upvote.

Attempt This Online!

Explanation

f=lambda l:1+f(sum(l,l))?1
f=                          # Define f as
  lambda l:                 # a function of one argument, l, a list:
               sum(l  )     #  Add (concatenate) each element of l
                    ,l      #  to l
                            #  If all elements of l are lists, this succeeds,
                            #  essentially flattening l by one level and concatenating
                            #  that to the original l
             f(        )    #  Call f recursively on that list
           1+               #  and add 1 to the result
                            #  If there are any integers in l, sum raises an exception
                        ?1  #  Catch that exception and return 1
\$\endgroup\$
0
\$\begingroup\$

APL(Dyalog Unicode), 17 bytes SBCS

{0∊≡¨⍵:1⋄1+∇⊃,/⍵}

Try it on APLgolf!

A dfn submission which takes a ragged array on the right.

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

Charcoal, 32 bytes

≔¹ηW⬤θ⁼κ⁺υκ«≦⊕ηFθFκ⊞υλ≔υθ≔⟦⟧υ»Iη

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

≔¹η

Start off with a depth of 1.

W⬤θ⁼κ⁺υκ«

While all of the elements of the input are arrays, then:

≦⊕η

Increment the depth.

FθFκ⊞υλ≔υθ≔⟦⟧υ

Flatten the array by one level. (This is only four bytes in trunk Charcoal but unfortunately that's not available on TIO.)

»Iη

Output the final depth.

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

Python3, 57 bytes:

f=lambda x:min(isinstance(i,int)or 1+f(i)for i in x if i)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I don't remember the shortest way to check in Python 3, but int==type(i) seems to be shorter. You can also use -~ instead of 1+. \$\endgroup\$ Jan 13 at 17:05
  • \$\begingroup\$ This errors on input containing [[]]. \$\endgroup\$
    – pxeger
    Jan 13 at 17:07
0
\$\begingroup\$

Factor + math.unicode, 68 bytes

[ 1 swap [ dup [ real? ] ∃ ] [ [ 1 + ] dip flatten1 ] until drop ]

Flatten the input by one depth until a number is an element at the surface, keeping track of the number of iterations. This is shorter than the recursive solutions I tried, especially because Factor has no terse way of handling the minimum value of a sequence when it can be empty. (And because recursion is verbose in Factor.)

Since flatten1 postdates build 1525, the one TIO uses, here's a screenshot of running the above code in Factor's REPL:

enter image description here

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

Perl 5 List::Util, 43 bytes

$_=min map/\d/?$d:9e9+($d+=/,/?0:92-ord),@F

Try it online!

Runs through the input as a list of chars. Increases depth $d for each [, decreases for each ] since 92-ord becomes 92 - 91 = +1 for [ and 92 - 93 = -1 for ]. Nothing changes for , and yield current depths for which the minimum is printed for digits. To run all tests $d needs to be reset between each: Try all test cases online! A more sane algorithm would be this one, but 11 bytes longer.

\$\endgroup\$

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.