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]

• xnor: Are commas required to separate the elements in the output it's a string? And can numbers in the input have multiple digits? These seem like they can matter for the natural string-output approach.
• Wheat Wizard: @xnor I can't find any defaults on how to handle lists as strings. I don't think I am in a position to make a call on what is required there. I would think space separated or whatever would be fine, but this is probably more of a thing for meta since I don't use languages that way.

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+S ×ばつx}⊸⊔x-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.

x-1 Decrement each value.
×ばつx}⊸⊔ Group adjacent positive integers, and put each 0 in its own group.
S ̈ recursively call the function on each group.
1+ Add 1 to each number.

• Jonah: Nice approach! I’ll do a J translation later.

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]

• tsh: Can join be replaced by +''? a=>eval('_='+[...a,'_'].map(g=v=>d^v?d++<v?"["+g(v):"],"+g(v,d-=2):v,d=0))
• Arnauld: @tsh Nice simplification indeed!

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.

• loopy walt: Non-recursive version that takes advantage of Python's tolerance to trailing commas (-4) tio.run/##VY3RboQgEEXf/…

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.

• ovs: No J code, but maybe an idea for a slightly different (recursive) meld step: Group adjacent boxes (keeping scalar integers separated); For each of those groups: Concatenate the boxes and recursively call on the result. I'm not completely sure if this works correctly and is shorter to implement, but it shouldn't need the L:.
• Jonah: Yes, I considered that and think it’s conceptually more elegant. Maybe I’ll try tomorrow and see if it’s shorter. Thanks for looking
• ovs: Found a better approach.
• Jonah: Very, very nice! Shaved off 22 bytes for my J solution.

Answer 6

Charcoal, 29 bytes

≔0ηFA«F−ηι]→F−ιη[Iι≔ιη»Fη]UB,

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

≔0η

Start with a depth of 0.

FA«

Loop through the depths.

F−ηι]

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

→

Leave a space between values.

F−ιη[

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

Iι

Output the current depth.

≔ιη

Save the current depth as the previous depth.

»Fη]

Output the necessary closing ]s at the end.

UB,

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:

⊞υ⟦⟧FA«W‹Lυι«≔⟦⟧θ⊞§υ±1θ⊞υθ»≔...υιυ⊞§υ±1ι»⭆1§υ0

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

⊞υ⟦⟧

Start with an empty list.

FA«

Loop over the depths.

W‹Lυι«

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

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

... nest a list.

»≔...υιυ

Truncate the current depth to the next depth.

⊞§υ±1ι

Append the next depth value to its list.

»⭆1§υ0

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)

• Adamátor: I'm surprised nobody came up with a "non-cheating" way that would be shorter.
• Kevin Cruijssen: @xigoi ovs' BQN answer seems to be a non-cheating approach. Not sure if porting it to Jelly or 05AB1E would shorten the string approach, though.

Answer 8

Jelly, 20 bytes

Ø0jIr0Ṣ€Ṡị"[],"ż8FḊṖ

Try it online!

A string-based approach.

Explanation

Ø0jIr0Ṣ€Ṡị"[],"ż8FḊṖ
Ø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 -> ","
 ż8 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.

• AZTECCO: Nice answer! I think you can remove "a.all?{_1==d}?a:"

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.

• Giuseppe: I thought this would be a great moment to use the obscure relist but I couldn't figure out how to build the list structure. Trying to incorporate relist into your answer gives me 85 bytes.
• Giuseppe: Though I suppose relist could be used for this other question plus your solution here once you build the inverted depth map
• pajonk: @Giuseppe, thanks, that's a nice function I've never heard of before. I'm working on a solution to this other question, but as other answers base on solutions from here, I thought this challenge needs an R answer first :-)

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.