20
\$\begingroup\$

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 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]
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Jan 23 at 14:21
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    Jan 23 at 14:33

14 Answers 14

9
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ Nice approach! I’ll do a J translation later. \$\endgroup\$
    – Jonah
    Jan 24 at 13:05
5
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ 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:. \$\endgroup\$
    – ovs
    Jan 23 at 23:53
  • \$\begingroup\$ 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 \$\endgroup\$
    – Jonah
    Jan 23 at 23:56
  • 1
    \$\begingroup\$ Found a better approach. \$\endgroup\$
    – ovs
    Jan 24 at 7:58
  • \$\begingroup\$ Very, very nice! Shaved off 22 bytes for my J solution. \$\endgroup\$
    – Jonah
    Jan 24 at 15:54
4
\$\begingroup\$

Charcoal, 29 bytes

≔⁰ηFA«F⁻ηι]→F⁻ιη[Iι≔ιη»Fη]UB,

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

≔⁰η

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υι«≔⟦⟧θ⊞§υ±¹θ⊞υθ»≔…υιυ⊞§υ±¹ι»⭆¹§υ⁰

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

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

... nest a list.

»≔…υιυ

Truncate the current depth to the next depth.

⊞§υ±¹ι

Append the next depth value to its list.

»⭆¹§υ⁰

Pretty-print the final list.

\$\endgroup\$
4
\$\begingroup\$

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

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
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 59 41 40 bytes

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

Try it online!

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

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!

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

Perl 5 -p, 86 bytes

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

Try it online!

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

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.

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

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.

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

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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