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

• Luis Mendo: Is output flexible? Like numbers in different lines, where each line is one level; or other array delimiters/separators
• nimi: Related
• Daniel: @LuisMendo, yeah it's flexible
• sbisit: You are missing one bracket pair around 8 at line So, our output is...... However, you fixed it in the examples snippet.
• nimi: Some answers output an empty line for nesting levels with not elements. Is it ok to return an empty array in such cases, e.g. you first example as [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[]]]], [[[[[8]]]]]]?

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

• Cyoce: Might be able to save a few bytes by making an alias to filter. Maybe start with F=(x,y)=>x.filter(y)
• Neil: @Cyoce Turned out to be 30 in the end!
• Patrick Roberts: You definitely have some golfing left to do on this. I think you can safely replace [].concat(...v(1)) with v(1) to save 14 bytes. There are probably a few other things as well but I'm having a hard time keeping track of the nested parentheses in my head.
• Neil: @PatrickRoberts [].concat(...v(1)) is a very different beast to v(1), otherwise I wouldn't do it! For a simple example, consider a = [2, [3], [[4]]] then v(1) = [[3], [[4]]] but [].concat(...v(1)) = [3, [4]].
• Patrick Roberts: @Neil oh, wow I really should have tested my suggestion before opening my mouth. I feel like there should be a shorter way of doing this though..

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>

• Patrick Roberts: Given that there are only nested arrays and positive integers, and it's specified that none of the arrays in the input are empty, an easier test for your ternary operator would be v[0] instead of v.map. Saves 1 byte.

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

• Arnauld: @Shebang Thanks for noticing. This should be fixed.
• Kade: I believe that looks good now! :)

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!

• BlackCap: Do notation saves a byte h l=R$do d<-[1..];[i|(e,i)<-0#l,d==e]!d

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!