24
\$\begingroup\$

Given a non-flat list of integers, output a list of lists containing the integers in each nesting level, starting with the least-nested level, with the values in their original order in the input list when read left-to-right. If two or more lists are at the same nesting level in the input list, they should be combined into a single list in the output. The output should not contain any empty lists - nesting levels that contain only lists should be skipped entirely.

You may assume that the integers are all in the (inclusive) range [-100, 100]. There is no maximum length or nesting depth for the lists. There will be no empty lists in the input - every nesting level will contain at least one integer or list.

The input and output must be in your language's native list/array/enumerable/iterable/etc. format, or in any reasonable, unambiguous format if your language lacks a sequence type.

Examples

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

[3, 1, [12, [14, [18], 2], 1], [[4]], 5] => [[3, 1, 5], [12, 1], [14, 2, 4], [18]]

[2, 1, [[5]], 6] => [[2, 1, 6], [5]]

[[54, [43, 76, [[[-19]]]], 20], 12] => [[12], [54, 20], [43, 76], [-19]]

[[[50]], [[50]]] => [[50, 50]]
\$\endgroup\$

15 Answers 15

5
\$\begingroup\$

Pyth, 17

 us-GeaYsI#GQ)S#Y

The leading space is important. This filters the list on whether the values are invariant on the s function, then removes these values from the list and flatten it one level. The values are also stored in Y and when we print we remove the empty values by filtering if the sorted value of the list is truthy.

Test Suite

Alternatively, a 15 byte answer with a dubious output format:

 us-GpWJsI#GJQ)

Test Suite

Expansion:

 us-GeaYsI#GQ)S#Y     ##   Q = eval(input)
 u          Q)        ##   reduce to fixed point, starting with G = Q
        sI#G          ##   get the values that are not lists from G
                      ##   this works because s<int> = <int> but s<list> = flatter list
      aY              ##   append the list of these values to Y
     e                ##   flatten the list
   -G                 ##   remove the values in the list from G
              S#Y     ##   remove empty lists from Y
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 56 54 52 bytes

-2 bytes due to Alephalpha.

-2 bytes due to CatsAreFluffy.

Cases[#,_?AtomQ,{i}]~Table~{i,Depth@#}/.{}->Nothing&

Actually deletes empty levels.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Cases[#,_?AtomQ,{i}]~Table~{i,Depth@#}~DeleteCases~{}& \$\endgroup\$
    – alephalpha
    Feb 20, 2016 at 12:14
  • 1
    \$\begingroup\$ Cases[#,_?AtomQ,{i}]~Table~{i,Depth@#}/.{}->Nothing&, 2 bytes shorter \$\endgroup\$ Feb 20, 2016 at 15:31
3
\$\begingroup\$

Python 2, 78 bytes

f=lambda l:l and zip(*[[x]for x in l if[]>x])+f(sum([x for x in l if[]<x],[]))
\$\endgroup\$
1
\$\begingroup\$

Retina, 79

I know the Retina experts will golf this more, but here's a start:

{([^{}]+)}(,?)([^{}]*)
$3$2<$1>
)`[>}],?[<{]
,
(\d),+[<{]+
$1},{
<+
{
,*[>}]+
}

Try it online.

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

Mathematica 55 64 62 bytes

#~Select~AtomQ/.{}->Nothing&/@Table[Level[#,{k}],{k,Depth@#}]&

%&[{1, 2, {3, {4, 5}, 6, {7, {8}, 9}}}]

{{1, 2}, {3, 6}, {4, 5, 7, 9}, {8}}

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

JavaScript, 112 80 bytes

F=(a,b=[],c=0)=>a.map(d=>d!==+d?F(d,b,c+1):b[c]=[...b[c]||[],d])&&b.filter(d=>d)

Thanks Neil for helping shave off 32 bytes.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Lots of opportunities for golfing here. Some easy ones are to remove the !=null as null is falsy anyway. The b= is also unnecessary. Having removed that you can then move the .filter(a=>x) to the &&b which then reduces the outer function to a call to the inner function which you can then inline. I'm left with this: f=(a,b=[],c=0)=>a.map(d=>d[0]?f(d,b,c+1):b[c]=[...b[c]||[],d])&&b.filter(d=>d). \$\endgroup\$
    – Neil
    Feb 19, 2016 at 21:59
  • \$\begingroup\$ @Neil d[0]? would evaluate false if it was equal to 0, which is within the range [-100,100]. And so would d=>d \$\endgroup\$ Feb 19, 2016 at 22:23
  • \$\begingroup\$ @Neil Threw this one up in a rush, so I knew there were other opportunities to shrink it, but this is much better than I could have done even then. Thanks! Oh, and Patrick is right on the null check being necessary for that reason. I went with d===+d though, since it saves 2 bytes on the null check. \$\endgroup\$
    – Mwr247
    Feb 19, 2016 at 22:31
  • 1
    \$\begingroup\$ @Dendrobium That won't handle the last case (or any cases with [...,[[...]]]) properly \$\endgroup\$
    – Mwr247
    Feb 19, 2016 at 23:18
  • 1
    \$\begingroup\$ @PatrickRoberts d=>d is OK since d is always an array or null at that point, but a fair point regarding d[0], although there's always d.map which will be truthy for an array but falsy for a number. \$\endgroup\$
    – Neil
    Feb 20, 2016 at 0:05
1
\$\begingroup\$

Jelly, 24 bytes

fFW®;©ṛ¹ḟF;/µŒḊ’$¡W®Tị¤;

Try it online!

If newline-separated lists were allowed, this could be golfed down to 14 bytes.

fFṄ¹¹?ḟ@¹;/µ¹¿

Try it online!

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

Jelly, 6 bytes

ŒJẈĠịF

Try it online!

Jelly has substantially improved in the past 5 years

How it works

ŒJẈĠịF - Main link. Takes a list L on the left
ŒJ     - Multi-dimensional indices
  Ẉ    - Get the length of each element
         This yields the depth (starting at 1 for flat elements) of each element
   Ġ   - Group the indices of this list by the values
     F - Flatten L
    ị  - Index into

Huh? The way that ŒJẈĠ works is kinda confusing without an example. Let's take L = [3, 1, [12, [14, [18], 2], 1], [[4]], 5] and work through it

ŒJ is one of a series of multi-dimensional commands that reflect the behaviour of their one-dimensional versions. Specifically, this is the "multi-dimensional indices" command, a multi-dimensional version of J, the "indices" command.

Picture L arranged like this:

3 1 12 14 18 2 1 4 5
    12 14 18 2 1 4
       14 18 2   4
          18

That is, each element is repeated down a number of times equal to it's depth. ŒJ doesn't quite leave the elements like this (it changes the specific values, not the shape), but it's enough. then calculates the length of each i.e. how many rows each element goes down:

1 1 2 3 4 3 2 3 1

Ġ the takes this list as it's argument. First, it's generates this list's indices: [1, 2, 3, 4, 5, 6, 7, 8, 9]. We then group these indices by the values of the argument. So because the values at indices 3 and 7 are equal (they're both 2), [3, 7] is grouped. The final result of this is [[1, 2, 9], [3, 7], [4, 6, 8], [5]] as the groups are sorted by the values they're grouped by.

Finally, we index into the flattened L using this list of groups, which yields the intended output

\$\endgroup\$
0
\$\begingroup\$

Python, 108 99 bytes

This seems a bit long to me, but I couldn't make a one-liner shorter, and if I try using or instead of if, I get empty lists in the results.

def f(L):
    o=[];i=[];j=[]
    for x in L:[i,j][[]<x]+=[x]
    if i:o+=[i]
    if j:o+=f(sum(j,[]))
    return o

Try it online

Edit: Saved 9 bytes thanks to Stack Overflow

\$\endgroup\$
4
  • \$\begingroup\$ You should change your indents to single spaces, so they render properly in the code block. You can also use filter(None,o) to remove empty lists that are on the outermost nesting level of o. \$\endgroup\$
    – user45941
    Feb 19, 2016 at 21:35
  • \$\begingroup\$ I prefer to view my code with tabs. Spaces are evil. \$\endgroup\$
    – mbomb007
    Feb 19, 2016 at 21:48
  • \$\begingroup\$ SE Markdown converts tabs to 4 spaces, so there's no escaping them anyway :) Using a single space in the Markdown makes the byte count of the code block actually match the byte count of the code. \$\endgroup\$
    – user45941
    Feb 19, 2016 at 21:50
  • \$\begingroup\$ My code itself contains tabs if you look to edit it, though. It's whats on the inside that counts. ;) \$\endgroup\$
    – mbomb007
    Feb 19, 2016 at 21:51
0
\$\begingroup\$

Python 3, 109 bytes

As ever, stupid Python 2 features like comparing ints and lists mean that Python 3 comes out behind. Oh well...

def d(s):
 o=[]
 while s:
  l,*n=[],
  for i in s:
   try:n+=i
   except:l+=[i]
  if l:o+=[l]
  s=n
 return o
\$\endgroup\$
0
\$\begingroup\$

Perl, 63 bytes

{$o[$x++]=[@t]if@t=grep{!ref}@i;(@i=map{@$_}grep{ref}@i)&&redo}

Input is expected in @i, output produced in @o. (I hope this is acceptable).

Example:

@i=[[54, [43, 76, [[[-19]]]], 20], 12];                              # input

{$o[$x++]=[@t]if@t=grep{!ref}@i;(@i=map{@$_}grep{ref}@i)&&redo}      # the snippet

use Data::Dumper;                                                    # print output
$Data::Dumper::Indent=0;  # keep everything on one line
$Data::Dumper::Terse=1;   # don't print $VAR =
print Dumper(\@o);

Output:

[[12],[54,20],[43,76],[-19]]
\$\endgroup\$
0
\$\begingroup\$

Clojure, 119 bytes

(116 with seq? and input as lists, a trivial modification)

(defn f([v](vals(apply merge-with concat(sorted-map)(flatten(f 0 v)))))([l v](map #(if(number? %){l[%]}(f(inc l)%))v)))

Better intended:

(defn f([v]  (vals(apply merge-with concat(sorted-map)(flatten(f 0 v)))))
       ([l v](map #(if(number? %){l[%]}(f(inc l)%))v)))

When called with two arguments (the current level and a collection) it either creates an one-element unordered-map like {level: value}, or calls f recursively if a non-number (presumambly a collection) is seen.

These mini-maps are then merged into a single sorted-map and key collisions are handled by concat function. vals returns map's values from first level to the last.

If a number is the only one at its level then it remains a vec, others are converted to lists by concat.

(f [[54, [43, 76, [[[-19]]]], 20], 12])
([12] (54 20) (43 76) [-19])

If input was a list instead of vec then number? could be replaced by seq?, oddly vector isn't seq? but it is sequential?. But I'm too lazy to implement that version, re-do examples etc.

\$\endgroup\$
0
\$\begingroup\$

Racket 259 bytes

(let((ol'())(m 0))(let p((l l)(n 0))(cond[(empty? l)][(list?(car l))(set! m(+ 1 n))
(p(car l)(+ 1 n))(p(cdr l)n)][(set! ol(cons(list n(car l))ol))(p(cdr l)n )]))
(for/list((i(+ 1 m)))(flatten(map(λ(x)(cdr x))(filter(λ(x)(= i(list-ref x 0)))(reverse ol))))))

Ungolfed:

(define (f l)
  (define ol '())
  (define maxn 0)
  (let loop ((l l)              ; in this loop each item is added with its level
             (n 0))
    (cond
      [(empty? l)]
      [(list? (first l))
       (set! maxn (add1 n))
       (loop (first l) (add1 n))
       (loop (rest l) n)]
      [else
       (set! ol (cons (list n (first l)) ol))
       (loop (rest l) n )]))

  ; now ol is '((0 1) (0 2) (1 3) (2 4) (2 5) (1 6) (2 7) (3 8) (2 9)) 

  (for/list ((i (add1 maxn)))   ; here similar levels are combined
    (flatten
     (map (λ (x) (rest x))      ; level numbers are removed
          (filter (λ (x) (= i(list-ref x 0)))
                  (reverse ol))))))

Testing:

(f '[1 2 [3 [4 5] 6 [7 [8] 9]]])

Output:

'((1 2) (3 6) (4 5 7 9) (8))
\$\endgroup\$
0
\$\begingroup\$

MATL, 37 bytes

j']['!=dYsXKu"GK@=)'[\[\],]'32YXUn?1M

Try it online!

Works with current release (13.0.0) of the language/compiler.

This produces the output as lines of space-separated values, where each line corresponds to the same nesting level, and different nesting levels are separated by newlines.

j            % read input as string (row array of chars)
']['!        % 2x1 array containing ']'  and '['
=            % test for equality, all combinations
d            % row array obtained as first row minus second row
Ys           % cumulative sum. Each number is a nesting level
XK           % copy to clibdoard K
u            % unique values: all existing nesting levels
"            % for each nesting level
  G          %   push input
  K          %   push array that indicates nesting level of each input character
  @          %   push level corresponding to this iteration
  =          %   true for characters corresponding to that nesting level
  )          %   pick those characters
  '[\[\],]'  %   characters to be replaced
  32         %   space
  YX         %   regexp replacement
  U          %   only numbers and spaces remain: convert string to array of numbers
  n?         %   if non-empty
    1M       %     push that array of numbers again
             %   end if implicitly
             % end for each implicitly
\$\endgroup\$
0
\$\begingroup\$

Stax, 18 bytes

é╔óó)₧ú↔u.≤∟╦Ç╟·○`

Run and debug it

I rhought I'd be able to beat pyth, but ¯\_(○-○)_/¯

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.