36
\$\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\$
  • \$\begingroup\$ Add a testcase with bigger than single digit numbers for string based answers. \$\endgroup\$ – orlp Dec 20 '16 at 22:44
  • \$\begingroup\$ @orlp good idea. \$\endgroup\$ – FlipTack Dec 20 '16 at 22:45
  • 2
    \$\begingroup\$ Can we assume a certain maximum depth? Say, 16? \$\endgroup\$ – orlp Dec 20 '16 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 '16 at 23:11
  • \$\begingroup\$ May I output as a string? \$\endgroup\$ – Rohan Jhunjhunwala Dec 20 '16 at 23:17

14 Answers 14

4
\$\begingroup\$

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]
\$\endgroup\$
  • \$\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 '16 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 '16 at 9:02
  • \$\begingroup\$ Ok :) nice answer! \$\endgroup\$ – FlipTack Dec 29 '16 at 9:30
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\$
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\$
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\$
  • \$\begingroup\$ Nice one, this is the method I used with my initial Python solution for the test cases :) \$\endgroup\$ – FlipTack Dec 21 '16 at 10:14
  • \$\begingroup\$ is.list(y) instead of class(y)=='list' ? can't verify that that will actually work. \$\endgroup\$ – Giuseppe Nov 6 '17 at 14:14
  • \$\begingroup\$ 180 bytes \$\endgroup\$ – Giuseppe Nov 7 '17 at 22:34
3
\$\begingroup\$

Retina, 34 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ How does the (?<-2>) work? \$\endgroup\$ – Kritixi Lithos Dec 21 '16 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\$ – Martin Ender Dec 21 '16 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\$
  • \$\begingroup\$ Is * like argument to code block? \$\endgroup\$ – Downgoat Dec 21 '16 at 4:25
  • \$\begingroup\$ @Downgoat in this case it wraps the argument d-1 times. $func is a function that can be manipulated. \$\endgroup\$ – Conor O'Brien Dec 21 '16 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\$
  • \$\begingroup\$ Where does the result get initialised? \$\endgroup\$ – Neil Dec 20 '16 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 '16 at 21:59
  • \$\begingroup\$ Doesn't that mean that you'd only be able to call it once? \$\endgroup\$ – Neil Dec 20 '16 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 '16 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 '16 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\$
  • \$\begingroup\$ You can change a+=[n(l,d)] to a+=n(l,d), (note the trailing comma) \$\endgroup\$ – FlipTack Dec 20 '16 at 21:52
  • \$\begingroup\$ Do you even need to assign to t? \$\endgroup\$ – Zacharý Dec 23 '16 at 20:44
  • \$\begingroup\$ Does this work when you call it more than once? \$\endgroup\$ – Zacharý Dec 23 '16 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\$ – Zacharý Dec 23 '16 at 23:12
  • \$\begingroup\$ repl.it/EwPz \$\endgroup\$ – Zacharý Dec 23 '16 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
    \$\begingroup\$ In both code blocks, I think you omitted the leading f=. \$\endgroup\$ – Conor O'Brien Dec 20 '16 at 21:46
  • \$\begingroup\$ @ConorO'Brien Yet again... \$\endgroup\$ – Neil Dec 20 '16 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\$
0
\$\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\$

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.