An Array of Challenges #2: Separate a Nested Array

Question

_{Note: This is #2 in a series of array-manipulation 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 code-golf, 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.

Answer 1

Brachylog, 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]

Answer 2

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.

Answer 3

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.

Answer 4

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)
}

Answer 5

Retina, 34 bytes

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

Try it online!

Answer 6

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

Answer 7

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.

Answer 8

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
}

Answer 9

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]

Answer 10

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))

Answer 11

Pyth - 29 bytes

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

Test Suite.

Answer 12

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.

Answer 13

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.

Answer 14

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