40
\$\begingroup\$

Note: This is #2 in a series of challenges. For the previous challenge, click here.

Separating Nested Lists

To separate values in a nested list, flatten it, and then wrap each value so it is at the same nested depth as before.

That is to say, this list:

[1, [2, 3], [4, 4, [5, 2], 1]]

Would become:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

The Challenge

Your task is to write a program which takes any nested list of positive integers (within your language's limits) and performs this separation operation.

You may submit a function which takes the list as an argument, or a full program which performs I/O.

As this is , the shortest submission (in bytes) wins!*

*Standard golfing loopholes are banned. You know the drill.


Test Cases

Input lists will only ever contain integers in your language's standard integer size. To avoid languages' constraints preventing them from competing, values will not be nested at depths of more than 10.

You may assume that input will not have empty sub-lists: for example - [[5, []]] will not be given. However, the main list could be empty.

[]            ->  []

[[1, 2]]      ->  [[1], [2]]
[3, [4, 5]]   ->  [3, [4], [5]]
[3, [3, [3]]] ->  [3, [3], [[3]]]
[[6, [[7]]]]  ->  [[6], [[[7]]]]
[[5, 10], 11] ->  [[5], [10], 11]

Don't hesitate to leave a comment if I've missed out a corner case.

Example

I threw together a quick (ungolfed) Python 3 solution as an example - you can test it on repl.it.

\$\endgroup\$
8
  • \$\begingroup\$ Add a testcase with bigger than single digit numbers for string based answers. \$\endgroup\$
    – orlp
    Dec 20, 2016 at 22:44
  • \$\begingroup\$ @orlp good idea. \$\endgroup\$
    – FlipTack
    Dec 20, 2016 at 22:45
  • 3
    \$\begingroup\$ Can we assume a certain maximum depth? Say, 16? \$\endgroup\$
    – orlp
    Dec 20, 2016 at 22:51
  • \$\begingroup\$ @orlp I'm going to say yes, the maximum nested depth will be 10, as I'm more interested in your algorithm and method execution than your language's constraints. Will update thread now. \$\endgroup\$
    – FlipTack
    Dec 20, 2016 at 23:11
  • \$\begingroup\$ May I output as a string? \$\endgroup\$ Dec 20, 2016 at 23:17

17 Answers 17

19
\$\begingroup\$

Mathematica, 24 21 bytes

##&@@List/@#0/@#&/@#&

or one of these:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

Explanation

The reason this is so short is that it's basically a recursion that doesn't require an explicit base case.

There's a lot of syntactic sugar here, so let's start by ungolfing this. & denotes an unnamed function left of it, whose argument is written as #. Inside this function #0 refers to the function itself, which allows one to write unnamed recursive functions. But let's start by giving the inner function a name and pulling it out:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

The other important syntactic sugar is f/@x which is short for Map[f, x] i.e. it calls f on every element of x. The reason f[x_] := ... f /@ x doesn't lead to infinite recursion is that mapping something over an atom leaves the atom unchanged without actually calling the function. Hence, we don't need to check for the base case (current element is an integer) explicitly.

So the function f first recurses down to the deepest list inside x, at which point f/@ becomes a no-op. Then we call use ##& @@ List /@ on that. Mapping List over the list simply wraps each element in a separate list, so {1, 2, 3} becomes {{1}, {2}, {3}}. Then we apply ##& to it, which means the head (i.e. the outer list) gets replaced by ##&, so this turns into ##&[{1}, {2}, {3}]. But ##& simply returns it's arguments as a Sequence (which you can think of as an unwrapped list, or a sort of "splat" operator in other languages).

So ##& @@ List /@ turns a list {1, 2, 3} into {1}, {2}, {3} (kind of, that last thing is actually wrapped in the head Sequence, but that vanishes as soon as we use the value anywhere).

That leaves the question why f itself isn't already the solution to the challenge. The problem is that the outermost list should be treated differently. If we have input {{1, 2}, {3, 4}} we want {{1}, {2}, {3}, {4}} and not {{1}}, {{2}}, {{3}}, {{4}}. My original solution fixed this by passing the final result as a list of arguments to Join which would restore the outer level of lists, but this one just skips the outer level by using f itself in a map on the output. Hence f is only applied to the individual elements of the outermost list and never gets to touch that list.

As for the other three solutions, the first one simply applies the recursion outside of f which works just as well. The other two solutions avoid a repeated Map operation by first composing two functions and then mapping the result only once.

\$\endgroup\$
0
8
\$\begingroup\$

J, 19 18 bytes

(<@]/@,~>)S:0 1{::

This is an anonymous verb that takes and returns boxed arrays, which are J's (rather cumbersome) version of nested arrays. See it pass all test cases.

Explanation

This uses the somewhat exotic operations {:: (map) and S: (spread), which operate on boxed arrays. {:: replaces each leaf with the boxed path to that leaf. S: applies a given verb to a given nesting depth, then splats the results into an array.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.
\$\endgroup\$
5
\$\begingroup\$

Brachylog v1, 16 bytes

:{##:0&:ga|g}ac|

Try it online!

Explanation

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]
\$\endgroup\$
3
  • \$\begingroup\$ What does the Z argument do on TIO? Without it this seems to output with true/false, which makes it seem like Z is necessary in the byte count. \$\endgroup\$
    – FlipTack
    Dec 28, 2016 at 19:30
  • \$\begingroup\$ @FlipTack Z tells Brachylog that the output argument is a variable. This is this variable that gets unified with the resulting output. When you remove it it tells Brachylog the output is an anonymous variable, and instead will print whether the main predicate succeeds or fails. This is the same as in Prolog where the result is "put" in a variable. \$\endgroup\$
    – Fatalize
    Dec 29, 2016 at 9:02
  • \$\begingroup\$ Ok :) nice answer! \$\endgroup\$
    – FlipTack
    Dec 29, 2016 at 9:30
3
\$\begingroup\$

R, 199 bytes

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

This question was HARD. R's lists are a bit weird and it is absolutely not straightforward to loop over all the elements of sublists. It is also not straightforward to then determining the depth of that list. Then the challenge becomes to recreate the list with all the elements separated, so we also need a way to adaptively create a list of a certain depth.

The solution consists of two big parts. A recursive function that loops over all the lists and records the depth:

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

When we have the depths of every entry of the vector unlist(l), stored in d, we implicitly create a list through lapply, and fill it with the following function:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

In this apply call, we create an object q with the value of the entry in the list, check its depth and see if it is nonzero. If it is zero, we can just leave it as a numeric value. If it is non-zero, we need to nest it in that amount of lists. So we call a for-loop d times and repeatedly call q=list(q).

lapply then puts all these values of q in a list, creating the desired output.

Complete program with proper spacing and such:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}
\$\endgroup\$
3
  • \$\begingroup\$ Nice one, this is the method I used with my initial Python solution for the test cases :) \$\endgroup\$
    – FlipTack
    Dec 21, 2016 at 10:14
  • \$\begingroup\$ is.list(y) instead of class(y)=='list' ? can't verify that that will actually work. \$\endgroup\$
    – Giuseppe
    Nov 6, 2017 at 14:14
  • \$\begingroup\$ 180 bytes \$\endgroup\$
    – Giuseppe
    Nov 7, 2017 at 22:34
3
\$\begingroup\$

Retina, 34 bytes

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ How does the (?<-2>) work? \$\endgroup\$
    – user41805
    Dec 21, 2016 at 12:35
  • \$\begingroup\$ @KritixiLithos It's a balancing group. It pops from capture stack 2 which lets me keep track of the current nesting depth. \$\endgroup\$ Dec 21, 2016 at 12:37
2
\$\begingroup\$

C (gcc), 147 bytes

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Example input:

1 [23 3] [40 4 [5 2] 1]

Example output:

1 [23] [3] [40] [4] [[5]] [[2]] [1]
\$\endgroup\$
2
\$\begingroup\$

stacked, noncompeting, 25 bytes

{e d:e$wrap d 1-*}cellmap

This is a function in that it modifies the top member of the stack. If you want a bonafide function, just add [ and ] to the beginning and end. Try it here!

Here's a readable version:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Test case:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Output without newlines:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))
\$\endgroup\$
2
  • \$\begingroup\$ Is * like argument to code block? \$\endgroup\$
    – Downgoat
    Dec 21, 2016 at 4:25
  • \$\begingroup\$ @Downgoat in this case it wraps the argument d-1 times. $func is a function that can be manipulated. \$\endgroup\$ Dec 21, 2016 at 4:47
2
\$\begingroup\$

PHP, 101 94 bytes

saved 1 byte thanks to @Christoph, saved another 6 inspired by that.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

recursive function, pretty straight forward

breakdown

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}
\$\endgroup\$
10
  • \$\begingroup\$ Where does the result get initialised? \$\endgroup\$
    – Neil
    Dec 20, 2016 at 21:52
  • \$\begingroup\$ @Neil: PHP doesn´t require explicit initialization. Either $r gets elements in the loop or the function returns an empty array. It may yield notices, but those are not printed with the default config. \$\endgroup\$
    – Titus
    Dec 20, 2016 at 21:59
  • \$\begingroup\$ Doesn't that mean that you'd only be able to call it once? \$\endgroup\$
    – Neil
    Dec 20, 2016 at 23:59
  • 1
    \$\begingroup\$ You might as well get crazy: !cos(). cos() returns null for every array and a float != 0 for every positiv integer. I mean ... who cares for warnings? \$\endgroup\$
    – Christoph
    Dec 21, 2016 at 9:56
  • 1
    \$\begingroup\$ @Christoph: warnings are printed, notices are not (in thje default config). But it´s a great idea! On is_int: Reversing the condition doesn´t save anything; I need a space between else and foreach. BUT: $b[0] for an integer is NULL. \$\endgroup\$
    – Titus
    Dec 21, 2016 at 16:13
2
\$\begingroup\$

Python 2, 122 106 bytes

Pretty terrible score, just a straightforward implementation.

Thanks to @Zachary T for helping save 16 bytes!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Call x with one argument to run. For some reason it can only be run once.

\$\endgroup\$
10
  • \$\begingroup\$ You can change a+=[n(l,d)] to a+=n(l,d), (note the trailing comma) \$\endgroup\$
    – FlipTack
    Dec 20, 2016 at 21:52
  • \$\begingroup\$ Do you even need to assign to t? \$\endgroup\$
    – Adalynn
    Dec 23, 2016 at 20:44
  • \$\begingroup\$ Does this work when you call it more than once? \$\endgroup\$
    – Adalynn
    Dec 23, 2016 at 20:49
  • \$\begingroup\$ You can move n to the function and remove the first argument since it's always going to be l. \$\endgroup\$
    – Adalynn
    Dec 23, 2016 at 23:12
  • \$\begingroup\$ repl.it/EwPz \$\endgroup\$
    – Adalynn
    Dec 23, 2016 at 23:20
2
\$\begingroup\$

JavaScript (Firefox 30-57), 53 bytes

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

Best ES6 answer I have so far is 76 bytes:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r
\$\endgroup\$
2
  • 2
    \$\begingroup\$ In both code blocks, I think you omitted the leading f=. \$\endgroup\$ Dec 20, 2016 at 21:46
  • \$\begingroup\$ @ConorO'Brien Yet again... \$\endgroup\$
    – Neil
    Dec 20, 2016 at 21:50
1
\$\begingroup\$

Pyth - 29 bytes

.b]FYt-F/LN`[)PsM._:`Q"\d"3.n

Test Suite.

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

Perl 6, 60 47 bytes

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

(Try it online.)

Explanation:

  1. [... for |$^a]: Iterate over the input array, and construct a new array from it.
  2. $_ ~~ List ?? ... !! ...: For each element, check if it is itself an array.
  3. |([$_] for .&f): If the element is an array, recursively apply the function to it, iterate over the elements of the new array returned from that recursive call, wrap each element in an array of its own, and slip them into the outer list.
  4. $_: If the element is not an array, pass it on as-is.
\$\endgroup\$
1
\$\begingroup\$

Haskell, 71 bytes

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Again I have to define my own list type, because Haskell's natives lists can't be arbitrarily nested. This new type L can be returned from a function but not be printed by default, so in order to see a result I define a show instance for L:

instance Show L where
  show (N n)=show n
  show (C l)=show l

Now we can do some test in the REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

How it works: a simple recursion which passes the nesting level as a function of C constructors. We start with the identity function id and whenever there's a list (-> pattern match d#C l=) we add a further layer of C (-> C .pure.d) to the recursive call of # to all elements of the list. If we encounter a number, we simply apply the nesting-level-function d to the number.

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

APL (Dyalog), 44 bytes*

Anonymous tacit prefix function. Takes nested APL list as argument and returns a nested APL array.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-⌿'[]'∘.=j←⎕JSON⍵}

Try it online!

{} apply the following explicit function where the argument is represented by :

⎕JSON⍵ convert the argument to JSON

j← store in j

'[]'∘.= table where j equals open (top row) and close (bottom row) brackets

-⌿ top row minus bottom row (vertical difference reduction)

+\ cumulative sum (this gives the nesting level for each character)

()⊆ partition, beginning a new partition whenever a 1 is not preceded by a 1 in…

  j∊⎕D where each character of j is a member of the set of Digits

⊃¨ pick the first of each (this gives nesting level per multi-digit number)

∊{ apply the following function to each nesting level (), using the corresponding element from the ϵnlisted (flattened) argument as left argument ():

,⍺ ravel (listify) the number (because scalars cannot be enclosed)

⊂⍣⍵ enclose times

 disclose (because the innermost list is itself an enclosure)


* Using Dyalog Classic with ⎕ML←3 (default on many systems), substituting for and for . Tio!

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

Jelly, 12 10 bytes

FWṛ¡"ŒJẈ’Ɗ

Try it online!

How it works

FWṛ¡"ŒJẈ’Ɗ - Main link. Takes a list l on the left
F          - Flatten l
         Ɗ - Group the three previous commands over l:
     ŒJ    -   Multidimensional indices of l
       Ẉ   -   Get the length of each
        ’  -   Decrement
           - This gets the depth of each element in l
    "      - Zip together l and the depths, d
   ¡       - Do the following...
  ṛ        -   d times:
 W         -     Wrap the element of l
\$\endgroup\$
1
\$\begingroup\$

J, 23 bytes

([:;^:(1<L.)<"+L:0)^:L.

Try it online!

Since J requires boxing for ragged arrays, we use boxing level for array nesting level. Thus for example:

Original:
┌─────┐
│┌───┐│
││1 2││
│└───┘│
└─────┘
Transformed:
┌───┬───┐
│┌─┐│┌─┐│
││1│││2││
│└─┘│└─┘│
└───┴───┘


Original:
┌─┬───────┐
│3│┌─┬───┐│
│ ││3│┌─┐││
│ ││ ││3│││
│ ││ │└─┘││
│ │└─┴───┘│
└─┴───────┘
Transformed:
┌─┬───┬─────┐
│3│┌─┐│┌───┐│
│ ││3│││┌─┐││
│ │└─┘│││3│││
│ │   ││└─┘││
│ │   │└───┘│
└─┴───┴─────┘
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 11 bytes

f?⁽L€f‹¨£(w

Try it Online!

       ¨£   # Zip
f           # Input flattened
  ⁽L€       # Replace elements with depths
 ?          # in input
     f‹     # Flatten and decrement
       ¨£   # Zipwith...
         (w # Repeatedly wrap
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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