Inverted ragged list

Question

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]]

Answer 1

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.

Answer 2

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)

Answer 3

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

Answer 4

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!

Answer 5

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!

Answer 6

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.

Answer 7

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.

Answer 8

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)

Answer 9

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!

Answer 10

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:

ŒṖṚŒṪƇẈ$ÞḢḢ’$Ȧ¡€

Answer 11

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

Answer 12

Charcoal, 122 120 bytes

≔＆θ⁰η≔⟦η⟧ζＦζＦιＦ⁼κ⁺⟦⟧κ«ＵＭκ⊖μ⊞ζκ»⊞υθ⊞υηＦυＦιＦ⁼κ⁺⟦⟧κ⊞υκＦ⮌υ«≔⟦⟧ζＷι⊞ζ⊟ιＦ⮌ζ¿⁺⟦⟧κＦκ⊞ιλ⊞ικ»≔⮌θθ≔⁰ζＦ⁻η⊖⌊η«Ｆ⁻ζι]→Ｆ⁻ιζ[Ｉ⊟θ≔ιζ»Ｆζ]ＵＢ,

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

≔⟦η⟧ζＦζＦιＦ⁼κ⁺⟦⟧κ«ＵＭκ⊖μ⊞ζκ»

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.

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

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

≔⮌θθ≔⁰ζＦ⁻η⊖⌊η«Ｆ⁻ζι]→Ｆ⁻ιζ[Ｉ⊟θ≔ιζ»Ｆζ]ＵＢ,

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