# Build a list from a depth map

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.

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

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

• 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.
– xnor
Jan 23 at 14:21
• @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. Jan 23 at 14:33

# 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 ,.

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

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

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

• Non-recursive version that takes advantage of Python's tolerance to trailing commas (-4) tio.run/##VY3RboQgEEXf/… Jan 24 at 3:01

# BQN, 28 bytesSBCS

{⟨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.

• Nice approach! I’ll do a J translation later. Jan 24 at 13:05

# 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 63 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.
• 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:.
– ovs
Jan 23 at 23:53
• 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 Jan 23 at 23:56
• – ovs
Jan 24 at 7:58
• Very, very nice! Shaved off 22 bytes for my J solution. Jan 24 at 15:54

# Charcoal, 29 bytes

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


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

≔⁰η


ＦＡ«


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:

⊞υ⟦⟧


ＦＡ«


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.

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

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

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


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)

• I'm surprised nobody came up with a “non-cheating” way that would be shorter. Jan 25 at 10:41
• @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. Jan 25 at 11:21

# 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


# Wolfram Language (Mathematica), 5941 40 bytes

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


Try it online!

# 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!

# Perl 5 -p, 86 bytes

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


Try it online!

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

• Nice answer! I think you can remove "a.all?{_1==d}?a:" Jan 24 at 16:47
• oh wow, thanks! Jan 25 at 3:08

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

• 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. Feb 2 at 21:29
• Though I suppose relist could be used for this other question plus your solution here once you build the inverted depth map Feb 2 at 21:47
• @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 :-) Feb 3 at 5:24

# Vyxal 2.4.1D, 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.
`