22
\$\begingroup\$

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]]]]]
\$\endgroup\$
  • \$\begingroup\$ Is output flexible? Like numbers in different lines, where each line is one level; or other array delimiters/separators \$\endgroup\$ – Luis Mendo Oct 27 '16 at 19:14
  • \$\begingroup\$ Related \$\endgroup\$ – nimi Oct 27 '16 at 19:18
  • \$\begingroup\$ @LuisMendo, yeah it's flexible \$\endgroup\$ – Daniel Oct 27 '16 at 19:20
  • \$\begingroup\$ You are missing one bracket pair around 8 at line So, our output is...... However, you fixed it in the examples snippet. \$\endgroup\$ – sbisit Oct 27 '16 at 20:01
  • 2
    \$\begingroup\$ 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]]]]]]? \$\endgroup\$ – nimi Oct 28 '16 at 13:52

10 Answers 10

1
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Might be able to save a few bytes by making an alias to filter. Maybe start with F=(x,y)=>x.filter(y) \$\endgroup\$ – Cyoce Oct 28 '16 at 14:31
  • \$\begingroup\$ @Cyoce Turned out to be 30 in the end! \$\endgroup\$ – Neil Oct 28 '16 at 16:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Patrick Roberts Oct 28 '16 at 17:45
  • 1
    \$\begingroup\$ @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]]. \$\endgroup\$ – Neil Oct 28 '16 at 18:24
  • \$\begingroup\$ @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.. \$\endgroup\$ – Patrick Roberts Oct 28 '16 at 20:09
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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]]"
\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Patrick Roberts Oct 28 '16 at 17:35
  • \$\begingroup\$ @PatrickRoberts cool thanks \$\endgroup\$ – edc65 Oct 28 '16 at 18:08
1
\$\begingroup\$

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

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

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
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Do notation saves a byte h l=R$do d<-[1..];[i|(e,i)<-0#l,d==e]!d \$\endgroup\$ – BlackCap Oct 31 '16 at 9:46
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @Shebang Thanks for noticing. This should be fixed. \$\endgroup\$ – Arnauld Oct 28 '16 at 12:48
  • \$\begingroup\$ I believe that looks good now! :) \$\endgroup\$ – Kade Oct 28 '16 at 12:50

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.