Simplificate an array

Question

Input

An array that can contain arrays or positive, consecutive, ascending integers. The arrays can have any number of arrays inside of them, and so on and so forth. No arrays will be empty.

Output

This array simplificated

How to simplificate an array

We will use the array, [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]] as our example.

First, we check how deep the values are nested. Here are the depths and the numbers at those depths:

0  1
1  2 3 9
2  4 7
3  5 6
5  8

We construct the output array by taking the numbers in the original array, grouping them by how deep they are nested, and then nesting the groups at depths of the original depths of their elements. Arrange the numbers in ascending order and ascending depth.

So, our output is [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]

Examples

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

Answer 1

Perl, 52 bytes

Just a recursive subroutine. (unusual for a Perl answer, I know..)

sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}

Call it like that :

$ perl -E 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9])'
1
2 3 9
4 7
5 6

8

Each line of the output corresponds to a depth level of the array (hence the empty line in the example above).

It can be turned into a full program for just a few more bytes : add -n flag and an eval (inside @{ } to transform the input into an array and not an arrayref) to transform the input into a Perl array :

perl -nE 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(@{+eval})' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"

---

My previous approach was slightly longer (65 bytes), but still interesting, so I'll let it here :

perl -nE '/\d/?push@{$;[$d-1]},$_:/]/?$d--:$d++for/\[|]|\d+/g;say"@$_"for@' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"

Answer 2

JavaScript (ES6), 139 109 bytes

f=(a,v=b=>a.filter(a=>b^!a[0]))=>a[0]?v().concat((a=f([].concat(...v(1))),b=v())[0]?[b]:[],v(1).map(a=>[a])):[]

Explanation using the example input: v is a helper method which returns the arrays (with parameter 1) or values (with no parameter). We start with a = [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]], which is nonempty. We filter out the arrays, giving [1]. We then recursively call ourselves on the arrays concatenated together, which is [2, 3, [4], [[5, 6], 7, [[[8]]]], 9], the result being [2, 3, 9, [4, 7], [[5, 6]], [[[[8]]]]]. We again filter out the arrays, which gives us the second term of our output, [2, 3, 9], however we have to be careful not to insert an empty array here. It them remains to wrap the arrays [4, 7], [[5, 6]], [[[[8]]]] inside arrays and append them to the output, resulting in [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]].

Answer 3

Jelly, 8 bytes

fFṄḟ@;/ß

Output is one level per line, with empty lines for levels without elements. Try it online!

How it works

fFṄḟ@;/ß  Main link. Argument: A (array)

 F        Flat; yield all integers (at any level) in A.
f         Filter; intersect A with the integers, yielding those at level 0.
  Ṅ       Print the filtered array and a linefeed. Yields the filtered array.
     ;/   Reduce by concatenation.
          This decreases the levels of all integers at positive levels by 1.
   ḟ@     Swapped filter-false; remove the integers at level 0 in A from the array
          with decreased levels.
       ß  Recursively call the main link on the result.
          The program stops once A is empty, since ;/ will result in an error.

Answer 4

05AB1E, 27 26 25 21 bytes

D˜gFvyydi„ÿ ?}}¶?.gG«

Try it online! (slightly modified as .g isn't on TIO yet)

Explanation

D˜gF                    # flattened input length times do
    vy                  # for each y current level of list
      ydi„ÿ ?}          # if y is a digit, print with space
              }         # end v-loop
               ¶?       # print newline
                 .g     # calculate length of stack (this should be .g but I can't test)
                   G«   # length stack times, concatenate items on stack

The main strategy is to loop over each possible level of the nested array and print any digits on one row, while keeping the non-digits (lists) in a list one level less nested.

Answer 5

JavaScript (ES6) 121 144 152

Edit Revised a lot, 1 byte saved thx Patrick Roberts, and 21 more just reviewing the code

Recursive function working on arrays in input and output. I don't like the request of having elements at depth 1 as single elements in output array (while greater levels are grouped as one element): [l1,l1, [l2...], [[l3...]] ]. While this would be more direct: [ [l1...], [[l2...]], [[[l3...]]] ]

f=(l,d=0,r=[])=>l.map(v=>v[0]?f(v,d+1,r):r[d]=[...r[d]||[],v])
r.reduce((r,v,d)=>d?[...r,(n=d=>d-->1?[n(d)]:v)(d)]:v,[])

Newline added for readability.

Some notes: the line 2 is evaluated again and again at each recursive call, but only the last iteration at the end of recursion is useful.
The special handling when d==0 in line 2 takes care of the anomaly for level 1 elements.
The n recursive function handles the array nesting in output

Test

f=(l,d=0,r=[])=>l.map(v=>v[0]?f(v,d+1,r):r[d]=[...r[d]||[],v])
&&r.reduce((r,v,d)=>d?[...r,(n=d=>d-->1?[n(d)]:v)(d)]:v,[])

console.log=x=>O.textContent+=x+'\n'

test=[
 [ 
   [1, [2,3], 4], /* -> */ [1, 4, [2,3]]
 ]
,[
   [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]], 
   // ->
   [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]
 ]
,[
  [[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]],
  // ->
  [4, [2, 5], [[1, 3, 6]], [[[7]]], [[[[8, 9]]]], [[[[[[10]]]]]]] 
 ]
,[  
  [1], /* -> */ [1]
 ]
,[  
  [1, [2], [[3]], [[[4]]], [[[[5]]]]],
  // ->
  [1, [2], [[3]], [[[4]]], [[[[5]]]]]
 ]
,[  
  [1, [[[[2], 3]]], [[4]]],
  [1, [[4]], [[[3]]], [[[[2]]]]]
]]

test.forEach(t=>{
  var i=t[0], k=t[1], r=f(i),
      si=JSON.stringify(i),
      sr=JSON.stringify(r),
      sk=JSON.stringify(k)
  
  console.log((sr==sk?'OK ':'KO ')+si + " => " + sr)
})

<pre id=O></pre>

Answer 6

JavaScript (ES6) 168 bytes

f=a=>(s=[],b=-1,k=0,a.replace(/\d+|\[|\]/g,a=>a=='['?b++:a==']'?b--:(s[b]=s[b]||[]).push(a)),'['+s.map((a,b)=>k=a&&(k?',':'')+'['.repeat(b)+a+']'.repeat(b)).join``+']')

Demo

Answer 7

PHP, 145 Bytes

<?function c($r){$n=[];foreach($r as$k=>$v)if(is_array($v)){$n=array_merge($n,$v);unset($r[$k]);}if($n)$r[]=c($n);return$r;}print_r(c($_GET[a]));

Breakdown

function c($r){
  #usort($r,function($x,$y){return is_array($x)<=>is_array($y)?:$x<=>$y;}); 
#no need to sort and a simple sort($r); do it sort array after scalar
  $n=[];
  foreach($r as$k=>$v)if(is_array($v)){$n=array_merge($n,$v);unset($r[$k]);} # put arrays on the same depth together
  if($n)$r[]=c($n); # recursive if an array exists
  return$r; #return changes
}
print_r(c($_GET[a])); #Output and Input

Answer 8

JavaScript (ES6), 127 137 134 bytes

Takes an array as input and returns a string.

f=(a,l=[],d=0,o='')=>`[${a.map(x=>x[0]?f(x,l,d+1,o+'['):l[d]=(l[d]?l[d]+',':o)+x),l.map((s,d)=>x+s+']'.repeat(d,x=','),x='').join``}]`

Test cases

f=(a,l=[],d=0,o='')=>`[${a.map(x=>x[0]?f(x,l,d+1,o+'['):l[d]=(l[d]?l[d]+',':o)+x),l.map((s,d)=>x+s+']'.repeat(d,x=','),x='').join``}]`

console.log(f([1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]));
console.log(f([[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]]));
console.log(f([1]));
console.log(f([1, [2], [[3]], [[[4]]], [[[[5]]]]]));
console.log(f([1, [[[[2], 3]]], [[4]]]));

Answer 9

Pyth, 19 16 bytes

W=Qsf!&sITp+TdQk

Try it online. Test suite.

Note the leading space. Outputs levels on rows like the Perl answer.

Explanation

• Implicit input in Q.
• filter items T of Q on:
  • Check if sum is Identity on T.
  • If it was (it was a number), print T plus a space +…d.
  • If it wasn't (it was an array), keep it.
• sum the items. This removes a layer of arrays from each item. If none are left, yields 0.
• Assign = the result to Q.
• While the result is nonempty, print the empty string k and a newline.

Answer 10

Haskell, 124 123 bytes

data L=I Int|R[L]
d#R l=((d+1)#)=<<l
d#i=[(d::Int,i)]
[]!_=[]
l!1=l
l!d=[R$l!(d-1)]
h l=R$do d<-[1..];[i|(e,i)<-0#l,d==e]!d

As Haskell doesn't support mixed lists (integers and list of integers) by default, I define a custom list type L. Usage example:

*Main> h (R[I 1, R[I 2, I 3], R[ R[I 4]], R[ R[ R[I 5, I 6], I 7, R[R[R[I 8]]]], I 9]])
R [I 1,R [I 2,I 3,I 9],R [R [I 4,I 7]],R [R [R [I 5,I 6]]],R [R [R [R [R [I 8]]]]]]

Note: it takes some time to run, because it loops through all positive Ints (32 or 64bit) to look for a nest level that deep. Also: the custom list type cannot be printed by default, so if you want to see the result as in the example above, you need to add deriving Show to the data declaration (-> data L=I Int|R[L] deriving Show). Because it's not needed for returning a L-list from a function, I don't count the bytes.

How it works:

data L=I Int|R[L]               -- custom list type L, which is either an Int
                                -- (-> I Int) or a list of some L (-> R [L]) 

d#R l=((d+1)#)=<<l              -- # makes a list of (depth, I-number) pairs from
d#i=[(d::Int,i)]                -- a given L-list, e.g.
                                -- 0 # (R[I 1,R[I 2,I 3],I 4]) -> [(1,I 4),(2,I 2),(2,I 3),(1,I 4)]
                                -- the type annotation ::Int makes sure that all
                                -- depths are bounded. Without it, Haskell
                                -- would use arbitrary large numbers of type
                                -- ::Integer and the program won't finish

[]!_=[]                         -- ! wraps a list of Is with (d-1) additional
l!1=l                           --  R constructors
l!d=[R$l!(d-1)]

h l=                            -- main function, takes a L-list
      do d<-[1..]               -- for each nest level d make
        [i|(e,i)<-0#l,d==e]     -- a list of all I where the depth is d
                           !!d  -- and wrap it again with d-1 Rs         
     R$                         -- wrap with a final R

Edit @BlackCap saved a byte by switching from >>= to do notation. Thanks!

Answer 11

APL (Dyalog Unicode), 22 bytes

{⍬≢⍵:∇⊃,/⍵~⎕←⍵/⍨0=≡¨⍵}

Try it online!

Similar to Dennis' answer, a test case per line.

Answer 12

Red, 174 bytes

func[a][i: charset"0123456789"d: 0 m: copy #()parse mold a[any["["(d: d + 1)|"]"(d: d - 1)|" "|
copy t any i(either m/:d[append m/:d to 1 t][m/:d: to[]t])]]sort/skip to[]m 2]

Try it online!

A naive approach using the string representation of the array, keeping track of the depth by counting the [and ]. The integers are stored into a map which keys are the depths.

Answer 13

R, 96 bytes

f=function(x,`+`=list,`-`=unlist,i=sapply(x,is.list))c(+sort(-x[!i]),if(length(x[i]))+f(x[i]-F))

Try it online!

Outputs a nested list.

Ungolfed code

simplificate=
f=function(x){                      # recursive function f with argument x;
 islist=sapply(x,is.list)           # first determine which elements of x are lists
 c(                                 # now make a list of two groups of elements:
  list(sort(unlist(x[!islist]))),   # the first is the non-list elements of x,
  if(length(x[islist])){            # then (but only if there were some)
   list(                            # the second is a list of
    f(                              # the results of a recursive call to f
     unlist(x[islist],              # with the list elements of x as an argument,
      recursive=FALSE)))            # after unlisting by one level.
  }
 )
}

---

Or, 88 bytes

f=function(x,`-`=unlist,i=sapply(x,is.list))if(length(x)){print(sort(-x[!i]));f(x[i]-F)}

Try it online!

Outputs elements from each level on a different line. This meets the flexible output allowed in the comments, but feels a bit sneaky when R is happily able to output a nested list as originally asked for in the challenge...

Answer 14

Python 3, 104 bytes

v=lambda l,m={},i=1:m if l==[]else v(l[1:],v(l[0],m,i+1)if str(l[0])>'A'else{**m,i:m.get(i,[])+l[:1]},i)

Try it online!