Build a list from a depth map

Question

You will be given as input a non-empty list of positive integers. For example:

[1,2,2,2,1]

You want to produce a ragged list as output which has this as its "depth map". This list should have the same elements in the same order but each element n should be at the depth equal to its value.

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

This is a list where the 1s are at the first level, the 2s are nested in there, the threes would be nested in that etc.

There are multiple outputs that fit this description:

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

We want the simplest one, that is the one with the fewest lists total. So in this case

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

only has 2 lists whereas all the other examples had more.

Task

Take a depth map and produce the simplest ragged list that it could represent as outlined above.

This is code-golf so the goal is to minimize the size of your source code as scored in bytes.

Test cases

[1] -> [1]
[2] -> [[2]]
[3] -> [[[3]]]
[10] -> [[[[[[[[[[10]]]]]]]]]]
[1,2] -> [1,[2]]
[2,2] -> [[2,2]]
[2,1,2] -> [[2],1,[2]]
[1,2,3,2] -> [1,[2,[3],2]] 
[1,2,3,3,3,2,1] -> [1,[2,[3,3,3],2],1]
[1,2,1,2,1,3,3,1] -> [1,[2],1,[2],1,[[3,3]],1]

Answer 1

Retina, 23 21 bytes

Input are comma-separated integers, output is in the same format as the test cases.

\d+
*[$&$&*]
+`],\[
,

Try it online!

Wraps each number on its own, then repeatedly replaces ],[ with ,.

Answer 2

BQN, 28 bytes^SBCS

{⟨0⟩:0;1+𝕊¨{⊐+`»⊸∨¬×𝕩}⊸⊔𝕩-1}

Run online!

A single recursive function that builds the output as a nested list.

⟨0⟩:0 Base case: If the argument is a list containing a single 0, return 0 as a scalar value.

𝕩-1 Decrement each value.
{⊐+`»⊸∨¬×𝕩}⊸⊔ Group adjacent positive integers, and put each 0 in its own group.
𝕊¨ recursively call the function on each group.
1+ Add 1 to each number.

Answer 3

JavaScript (ES6),  80 79  74 bytes

Saved 5 bytes thanks to @tsh

This builds a weird and dirty string internally but eventually returns a clean ragged list.

a=>eval('_='+[...a,'_'].map(g=v=>d^v?d++<v?"["+g(v):"],"+g(v,d-=2):v,d=0))

Try it online!

How?

Starting with \$d=0\$, for each entry \$v\$ in the original array followed by an extra "_":

• if the current depth \$d\$ is less than \$v\$: we append the string "[" repeated \$v-d\$ times before \$v\$ and update \$d\$ to \$v\$
• if \$d\$ is greater than \$v\$: we append the string "]," repeated \$d-v\$ times before \$v\$ and update \$d\$ to \$v\$. (NB: The trailing "_" triggers this case and closes all pending brackets.)
• if \$d=v\$: we just leave \$v\$ unchanged

We then prepend "_=", which implicitly joins everything with commas, and we evaluate the resulting string.

For instance, [1,2,3,3,3,2,1] is turned into:

"_=[1,[2,[3,3,3,],2,],1,],_"

which is evaluated to:

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

Answer 4

Python 3, 75 bytes

f=lambda x,l=0:x and"],"*(l-x[0])+"["*(x[0]-l)+"%s,"%x+f(x[1:],x[0])or"]"*l

Try it online!

Python's % formatter coming in clutch.

Output is a list in string format that can be evaluated by Python to the correct answer.

Simple recursive function that walks down the input list. l just stores the value of the last element.

Python 3.8 (pre-release), 71 bytes

lambda x,i=0:",".join((j-i)*"["+(i-(i:=j))*"],"+str(j)for j in x)+i*"]"

Try it online!

Using the walrus operator removes the need for recursion, and the trailing comma can be added by str.join. Suggested by @loopywalt.

Answer 5

J, ^{63 59} 37 bytes

<:<@([:>:L:0$:^:(0<{.));.1~1,2~:/\=&1

Try it online!

^{-22 thanks to approach suggested by ovs! It's similar or the same as his BQN answer's.}

J, original approach ⁶³ 59 bytes

g=.((,$:/@,&.>/@]^:[~[:(1=*+.1<<.)/,&L.){.),}.@]
[:g/<^:]"+

Try it online!

This is ridiculous. Someone please find a better approach that still uses boxes and let me know what it is...

The basic approach is:

• Individually wrap each element to its depth.
• Recursively meld together neighboring elements using a fold.

Answer 6

Charcoal, 29 bytes

≔⁰ηＦＡ«Ｆ⁻ηι]→Ｆ⁻ιη[Ｉι≔ιη»Ｆη]ＵＢ,

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

≔⁰η

Start with a depth of 0.

ＦＡ«

Loop through the depths.

Ｆ⁻ηι]

Add ]s as necessary to reduce the depth to the current depth.

→

Leave a space between values.

Ｆ⁻ιη[

Add ]s as necessary to increase the depth to the current depth.

Ｉι

Output the current depth.

≔ιη

Save the current depth as the previous depth.

»Ｆη]

Output the necessary closing ]s at the end.

ＵＢ,

Replace all the interior spaces with commas. (The leading space simply gets skipped, since it wasn't actually printed.)

Actually creating the list in memory takes 44 bytes:

⊞υ⟦⟧ＦＡ«Ｗ‹Ｌυι«≔⟦⟧θ⊞§υ±¹θ⊞υθ»≔…υιυ⊞§υ±¹ι»⭆¹§υ⁰

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

⊞υ⟦⟧

Start with an empty list.

ＦＡ«

Loop over the depths.

Ｗ‹Ｌυι«

While the next depth is larger than the current depth, ...

≔⟦⟧θ⊞§υ±¹θ⊞υθ

... nest a list.

»≔…υιυ

Truncate the current depth to the next depth.

⊞§υ±¹ι

Append the next depth value to its list.

»⭆¹§υ⁰

Pretty-print the final list.

Answer 7

05AB1E, 22 bytes

εDG…[ÿ]]',ý…[ÿ]…],[',:

Input as list, output as string. It kinda feels like cheating, but I saw multiple other answers do the same.. And I guess we could technically add an eval.

Try it online or verify all test cases.

A port of @xigoi's Jelly answer is 22 bytes as well:

0.ø¥Ý€{.±…,[]sèJI.ιJ¦¨

Try it online or verify all test cases.

Explanation:

ε         # Map over each integer in the (implicit) input-list:
 D        #  Duplicate the integer
  G       #  Pop and loop the integer-1 amount of times:
   …[ÿ]   #   Wrap it in block-quotes as string
]         # Close both the inner loop and outer map
 ',ý     '# Join the strings with "," delimiter
    …[ÿ]  # Wrap the entire string into block-quotes as well
…],[',:  '# Replace all "],[" with ","
          # (after which the resulting string is output implicitly)

0.ø       # Surround the (implicit) input-list with leading/trailing 0
   ¥      # Get the deltas/forward-differences of this list
    Ý     # Transform each value to a list in the range [0,value]
     €{   # Sort each inner list
       .± # Convert each to its sign (-1 if <0; 0 if 0; 1 if >0)
…,[]sè    # Modular 0-based index each into ",[]"
      J   # Join each inner list of characters to a string
I.ι       # Interleave it with the input-list
   J      # Join it together again
    ¦¨    # Remove the leading/trailing ","
          # (after which the resulting string is output implicitly)

Answer 8

Jelly, 20 bytes

Ø0jIr0Ṣ€Ṡị“[],”ż⁸FḊṖ

Try it online!

A string-based approach.

Explanation

Ø0jIr0Ṣ€Ṡị“[],”ż⁸FḊṖ
Ø0j                  Surround with zeroes
   I                 Increments
    r0               Raplace each element x with the range x..0
      Ṣ€             Sort each range
        Ṡ            Replace each number with its sign
         ị“[],”      Perform the mapping: 1 -> "[", -1 -> "]", 0 -> ","
               ż⁸    Zip with the original input
                 F   Flatten
                  ḊṖ Remove the leading and trailing commas

Answer 9

Wolfram Language (Mathematica), 59 41 40 bytes

f@{a:0..}=a
f@l_:=f/@SplitBy[l-1,Sign]+1

Try it online!

Answer 10

Python3, 112 bytes:

from itertools import*
f=lambda x,n=1:[j for a,b in groupby(x,key=lambda x:x==n)for j in(b if a else[f(b,n+1)])]

Try it online!

Answer 11

Perl 5 -p, 86 bytes

s/\d+,?|$/"]"x($d=$l-$&).","."["x-$d.($l=$&)/ge;s/(\[),|,(])|,(,)/$1$2$3/g;s/^.|..$//g

Try it online!

Answer 12

Ruby, 54 bytes

f=->a,d=1{a.chunk{_1>d}.flat_map{_1 ? [f[_2,d+1]]:_2}}

Attempt This Online!

-16 from AZTECCO.

Answer 13

R, 84 bytes

Or R>=4.1, 77 bytes by replacing the word function with a \.

f=function(v,s=1)"if"(all(v<s),v,{y[]=cumsum(c(T,y<-v==s)|y);Map(f,split(v,y),s+1)})

Try it online!

Outputs the actual list structure.

Answer 14

Vyxal 2.4.1 D, 20 bytes

Ġƛh‹(w);S`⟩|⟨`\|øVḢṪ

Try it Online!

A big mess. We're using v2.4.1 because v2.6+ prettyprint lists with spacing.

Ġ                    # Group consecutive identical elements
 ƛ     ;             # Map...
  h‹( )              # item-1 times...
     w               # wrap in a list
        S            # Stringify
         `⟩|⟨`\|øV   # Replace `⟩|⟨` with `|`
                  ḢṪ # Remove the first and last characters.