22
\$\begingroup\$

Given a ragged list of positive integers, where the maximum depth is \$d_\text{max}\$, return the same list, except for every element \$e\$, its depth is \$d_\text{max}+1-d_e\$ (where \$d_e\$ is the depth of that element).

Your output should contain the minimal number of brackets, and you can assume the same from your input. Or in other words, "],[" doesn't appear in the input, and shouldn't appear in the output. You can assume that nonempty inputs contain at least one element with depth 1.

Test cases

[] <-> []
[[1,2],3,4] <-> [1,2,[3,4]]
[1,[2],1,[3],1] <-> [[1],2,[1],3,[1]]
[3,[2,[1],2],3] <-> [[[3],2],1,[2,[3]]]
[1,2,3,4] <-> [1,2,3,4]
[[[1]],10] <-> [1,[[10]]
\$\endgroup\$
6
  • \$\begingroup\$ Can we assume sublists are nonempty? \$\endgroup\$
    – att
    Feb 1, 2022 at 20:23
  • \$\begingroup\$ @att Yes, you can. The empty list only appears in the first test case. \$\endgroup\$
    – AnttiP
    Feb 1, 2022 at 20:25
  • 1
    \$\begingroup\$ Can we finish a list with a comma? (so the third example would be [[1,],2,[1,],3,[1,],]) \$\endgroup\$ Feb 2, 2022 at 9:54
  • \$\begingroup\$ @CommandMaster Yes, trailing commas are fine \$\endgroup\$
    – AnttiP
    Feb 2, 2022 at 19:32
  • 3
    \$\begingroup\$ @tsh I think this contradicts the nonempty lists contain at least one element with depth 1 condition (the outer list has no elements of depth 1). \$\endgroup\$
    – pajonk
    Feb 3, 2022 at 5:19

12 Answers 12

4
\$\begingroup\$

Retina 0.8.2, 83 bytes

+`],
,]
T`[]`][
+`,]
],
{`^(?!\[((\[)|(?<-2>])|\d|,)*(?(2)^)]$).*
[$&]
\[([][])]
$1

Try it online! Link include test cases. Explanation:

+`],
,]
T`[]`][
+`,]
],

Exchange ], with ,[, and also flip the leading [s and trailing ]s.

{`

Repeat until the string has been rebalanced.

^(?!\[((\[)|(?<-2>])|\d|,)*(?(2)^)]$).*
[$&]

If it's unbalanced then wrap it in []s.

\[([][])]
$1

Collapse unnecessary [] pairs.

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

Jelly, 31 30 27 bytes

ŒJẈạṀ$‘Ø0jIr0Ṣ€Ṡị“[],”żFFḊṖ

I'm pretty rusty in Jelly, so can probably be golfed a bit further. It indeed can:
-3 bytes thanks to @JonathanAllan.

Input as a list; output as a string.

Port of my 05AB1E answer. The Ø0jIr0Ṣ€Ṡị“[],”żFFḊṖ is a slight modification from @xigoi's Jelly answer for the Build a list from a depth map challenge.

Try it online or verify all test cases.

Explanation:

                 # Main link, taking the input-list as argument:
ŒJẈ              #  Determine the depth of each integer:
ŒJ               #   Get the multidimensional arguments
  Ẉ              #   Get the length of each inner list
   ạṀ$‘          #  Invert this depth-list:
     $           #   Apply the previous two links as monad:
    Ṁ            #    Get the maximum of this list of depths
   ạ             #    Calculate the absolute difference
      ‘          #   Increase each 0-based depth by 1
Ø0jIr0Ṣ€Ṡị“[],”  #  Create a string to zip with:
Ø0j              #   Surround the list with leading/trailing 0
   I             #   Forward-differences
    r0           #   Map each integer `n` to a list in the range [n,0]
      Ṣ€         #   Sort each range
        Ṡ        #   Signum (-1 if <0; 0 if 0; 1 if >0)
         ị“[],”  #   Index into "[]," ("[" if 1; "," if 0; "]" if -1)
ż                #  Zip/transpose, using the list above
 F               #  and the flattened input as arguments
  F              #  Then flatten the result
   ḊṖ            #  And remove the leading/trailing ","
                 #  (after which the result is output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ ⁸Fż@¥ could just be żF. \$\endgroup\$ Feb 2, 2022 at 12:50
  • \$\begingroup\$ @JonathanAllan I had the feeling that part could be shorter, and I tried a couple of things, but putting the F after the ż not for whatever reason.. Pretty obvious now that I see it. Thanks! \$\endgroup\$ Feb 2, 2022 at 13:26
3
\$\begingroup\$

R, 172 bytes

Or R>=4.1, 151 bytes by replacing three function occurrences with \s.

function(l,`?`=unlist,g=function(l)"if"(is.list(l),1+?Map(g,l),0),h=function(v)"if"(any(v),{y[]=cumsum(c(T,y<-v<2)|y);Map(h,split(v-1,y))},v))relist(?l,h(max(g(l))-g(l)+1))

Try it online!

Explanation outline

  1. Compute the depths of elements using recursive function g.
  2. Compute the target depths.
  3. Compute the target structure of the list using a recursive function h just like here: Build a list from a depth map.
  4. Use an obscure R function relist to assign original values to the new structure (as suggested by @Giuseppe).
\$\endgroup\$
2
\$\begingroup\$

Python3, 274 bytes:

from itertools import*
f=lambda x,c=0:[i for j in x for i in([(j,c)]if int==type(j)else f(j,c+1))]
g=lambda x,m:[j for a,b in groupby(x,key=lambda x:x[1]==m)for j in(lambda b:[u for u,_ in b]if a else[[*g(b,m-1)]])([*b])]
r=lambda x:g(l:=f(x),max(b for _,b in l))if x else x

Try it online!

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

Python 3.8 (pre-release), 191 bytes

f=lambda a:(a*0==0)*[(0,a)]or[(d+1,x)for y in a for d,x in f(y)]
def g(a):
 s=",".join("["*(z:=max(f(a))[0]+1-n)+f"{x}"+z*"]"for n,x in f(a))
 for _ in s:s=s.replace("],[",",")
 return s or[]

Try it online!

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

Python, 165 bytes

lambda x,i=0:x and[*eval(",".join((j-i)*"["+(i-(i:=j))*"],"+str(k)for j,k in d(x,-min(d(x))[0]))+i*"]")]
d=lambda x,c=0:x*-1and[(c,x)]or sum((d(y,c-1)for y in x),[])

Attempt This Online!

Old Python, 169 bytes

lambda x,i=0:x and[*eval(",".join(((n:=j-min(d(x))[0])-i)*"["+(i-(i:=n))*"],"+str(k)for j,k in d(x))+i*"]")]
d=lambda x,c=0:x*-1and[(c,x)]or sum((d(y,c-1)for y in x),[])

Attempt This Online!

Old Python, 174 bytes

lambda x,i=0:x and[*eval(",".join(((n:=j-min(sum(d(x),())))-i)*"["+(i-(i:=n))*"],"+str(k)for j,k in d(x))+i*"]")]
d=lambda x,c=0:x*-1and[(c,x)]or sum((d(y,c-1)for y in x),[])

Attempt This Online!

Old Python, 178 bytes

lambda x,i=0:x and eval("["+",".join(((n:=j-min(sum(d(x),())))-i)*"["+(i-(i:=n))*"],"+str(k)for j,k in d(x))+-~i*"]")
d=lambda x,c=0:x*-1and[(c,x)]or sum((d(y,c-1)for y in x),[])

Attempt This Online!

Based on this answer to a related challenge.

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

Wolfram Language (Mathematica), 75 72 bytes

If[v@#,#/.l->List,#0[##&@@@SequenceReplace[#,{a__}?v:>!l@a]]]&
v=VectorQ

Try it online!

-9 bytes if lower levels can have non-List heads: Try it online!

                           SequenceReplace[#,{a__}        ]     group consecutive
                                                  ?v              non-List elements
                                                    :> l@a        by wrapping with l
                     ##&@@@                           !         flatten out Lists
                  #0[                                      ]    recurse
If[v@#,          ,                                          ]     until no Lists left
       #/.l->List                                               turn l into List

Wolfram Language (Mathematica), 76 74 bytes

#/.{{__d}:>#0/@d/@SplitBy[D@@@#,Head],{__}:>#0[d/@#]}&
d@{a__}=d@a:{__d}=a

Try it online!

main function:
#/.                                   {__}:>#0[d/@#]    get depths
#/. {__d}:>                                             construct by:
               d/@SplitBy[D@@@#,Head]                     group this layer
           #0/@                                           recurse
                                                          (atoms are unchanged)

depth helper:
        d@a:{__d}=a     don't change lists that only have d[...]s
d@{a__}=          a     splat other lists
                        (stay unevaluated on atoms)

The first step of the main function wraps each value in a number of ds equal to their final depth. Then the final structure is constructed recursively in a manner similar to this answer.

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

05AB1E, 44 bytes

_"Ddië®δ.V>"©.V˜ZαU˜εXNèF…[ÿ]]',ý…[ÿ]…],[',:

I knew this approach would be pretty long, but not sure what a good alternative would be..

Input as a list; output as a string.

Try it online or verify all test cases.

Explanation:

In pseudo-code I do the following steps:

  1. Determine the (0-based) depth of each integer in the nested input-list (_"Ddië®δ.V>"©.V˜Zα - try it online).
  2. Flatten the input-list (˜).
  3. Use a minor modification of my 05AB1E answer for the Build a list from a depth map challenge with the list of step 1 to mold the flattened input-list (as string..) (εXNèF…[ÿ]}}',ý…[ÿ]…],[',:).

As for the actual code:

_           # Transform each integer in the (implicit) input to 0
 "..."      # Push the recursive string explained below
      ©     # Store it in variable `®` (without popping)
       .V   # Evaluate and execute it as 05AB1E code
  D         # Duplicate the current list
   dië      # If it's not an integer (so it's a list):
       δ    #  Map over each item:
      ® .V  #   Do a recursive call
      >     #  Then increase each integer in this list by 1
˜           # Flatten the result
 Z          # Push the maximum depth (without popping the list)
  α         # Pop and push the absolute difference
   U        # Pop and store this list in variable `X`
˜           # Flatten the (implicit) input-list
 ε          # Map over each integer:
  XNè       #  Get the depth from `X` at the same index
     F      #  Loop that many times:
      …[ÿ]  #   Wrap it in square blocks
 ]          # Close both the inner loop and outer map
  ',ý      '# Join everything by "," delimiter
     …[ÿ]   # Wrap the entire string in square blocks as well
  …],[',:  '# Replace all "],[" with ","
            # (after which the string is output implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 156 bytes

f=(a,i=d=+(m=b=[]))=>a.map?a.map(v=>f(v,i+1))|i||eval('b='+[...b,[f,'b']].map(g=a=>d^([v,x]=a,v+=~m)?d-->v?"["+g(a):"],"+g(a,d+=2):x)):b.push([i<m?i:m=i,a])

Try it online!

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

Jelly, 27 bytes

Is there something shorter than the ¬ȦƇẈƊ this uses?

ŒṖṚ¬ȦƇẈƊÞṪḢ’$Ȧ¡€
ŒJẈÇŒṪ¿ṁ@F

A monadic Link accepting a ragged list that yields a ragged list.

Try it online! Or see the test-suite.

How?

Firstly, get the depths of the items.

While there are any non-zero integers at any depth group together as many zeros, and lists that are only zeros at all depths, as possible and decrease all the other integers by one.

Lastly, mould a flattened version of the input like that ragged list.

ŒJẈÇŒṪ¿ṁ@F - Main Link: ragged list, A
ŒJ         - multidimensional indices of A
  Ẉ        - length of each -> flat list of depths
      ¿    - while...
    ŒṪ     - ...condition: truthy multidimensional indices
   Ç       - ...do: call the helper link
         F - flatten A
        @  - with swapped arguments:
       ṁ   -   mould like

ŒṖṚ¬ȦƇẈƊÞṪḢ’$Ȧ¡€ - Helper link: ragged list, Current State
ŒṖ               - all partitions of the Current State
  Ṛ              - reverse (to have longest last rather than first)
        Þ        - sort by:
       Ɗ         -   last three links as a monad:
   ¬             -     logical NOT (vectorises)
     Ƈ           -     filter keep those for which:
    Ȧ            -       any and all?
      Ẉ          -     length of each
         Ṫ       - tail
               € - for each:
              ¡  -   repeat...
             Ȧ   -   ...times: any and all?
            $    -   ...action: last two links as a monad:
          Ḣ      -     head
           ’     -     decrement

Alternative helper, same byte count:

ŒṖṚŒṪƇẈ$ÞḢḢ’$Ȧ¡€
\$\endgroup\$
4
  • 1
    \$\begingroup\$ @DialFrost - I accepted the edit, didn't know jelly-lang highlighting existed. It doesn't seem to do much highlighting though, maybe my red-green colourblindness isn't helping - are $ and Ȧ the same colour? Where can the definition be found, is it somewhere on github? \$\endgroup\$ Feb 3, 2022 at 12:19
  • \$\begingroup\$ er i just tried lang-jelly, as it looked like the functions could be coloured, and yes the $ and the Ȧ are the same colour of green. I dont know where the definition can be found though... i dont code in jelly :P \$\endgroup\$
    – DialFrost
    Feb 3, 2022 at 12:28
  • 3
    \$\begingroup\$ There is no lang-jelly, a list of available languages can be found on MSE. If you specify a language the system doesn't know it tries to autodetect the language (whatever that means) and in this case highlighted and @F as variables (maybe Perl?) \$\endgroup\$
    – ovs
    Feb 3, 2022 at 12:32
  • \$\begingroup\$ Thanks @ovs, confirmed useless then; oh well. \$\endgroup\$ Feb 3, 2022 at 12:33
0
\$\begingroup\$

JavaScript (Node.js), 137 bytes

x=>(y=JSON.stringify(x).replace(/,\[|],/g,t=>t>'['?(b+=']]',',['):(a+='[[','],'),a=b=''),g=t=>t?t.map?t[1]?t:g(t[0]):[t]:[])(eval(a+y+b))

Try it online!

First with lots of outer brackets then clean some

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

Charcoal, 122 120 bytes

≔&θ⁰η≔⟦η⟧ζFζFιF⁼κ⁺⟦⟧κ«UMκ⊖μ⊞ζκ»⊞υθ⊞υηFυFιF⁼κ⁺⟦⟧κ⊞υκF⮌υ«≔⟦⟧ζWι⊞ζ⊟ιF⮌ζ¿⁺⟦⟧κFκ⊞ιλ⊞ικ»≔⮌θθ≔⁰ζF⁻η⊖⌊η«F⁻ζι]→F⁻ιζ[I⊟θ≔ιζ»Fζ]UB,

Try it online! Link is to verbose version of code. Explanation: Not an easy problem to solve without access to recursion.

≔&θ⁰η

Make a deep clone of the input and set all of the integers in that clone to zero. (BitwiseAnd fully vectorises, unlike, say, Times.)

≔⟦η⟧ζFζFιF⁼κ⁺⟦⟧κ«UMκ⊖μ⊞ζκ»

Perform a breadth-first search over the clone and decrement each sublist. (Again, it is fortunate that Decremented fully vectorises, although I still have to MapCommand it because I need to modify each sublist in-place.) The resulting list ends up with values appropriate to their depth.

⊞υθ⊞υηFυFιF⁼κ⁺⟦⟧κ⊞υκF⮌υ«≔⟦⟧ζWι⊞ζ⊟ιF⮌ζ¿⁺⟦⟧κFκ⊞ιλ⊞ικ»

Flatten both the input and the depth clone in-place.

≔⮌θθ≔⁰ζF⁻η⊖⌊η«F⁻ζι]→F⁻ιζ[I⊟θ≔ιζ»Fζ]UB,

Adjust the depth list so that the minimum depth is 1, and use that to build the desired output list from the depth list and the flattened input list. (See my answer to Build a list from a depth map for more detail.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.