23
\$\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\$

13 Answers 13

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\$
  • 1
    \$\begingroup\$ Cases[#,_?AtomQ,{i}]~Table~{i,Depth@#}~DeleteCases~{}& \$\endgroup\$ – alephalpha Feb 20 '16 at 12:14
  • 1
    \$\begingroup\$ Cases[#,_?AtomQ,{i}]~Table~{i,Depth@#}/.{}->Nothing&, 2 bytes shorter \$\endgroup\$ – CalculatorFeline Feb 20 '16 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\$
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\$
  • 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 '16 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\$ – Patrick Roberts Feb 19 '16 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 '16 at 22:31
  • 1
    \$\begingroup\$ @Dendrobium That won't handle the last case (or any cases with [...,[[...]]]) properly \$\endgroup\$ – Mwr247 Feb 19 '16 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 '16 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\$
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\$
  • \$\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\$ – Mego Feb 19 '16 at 21:35
  • \$\begingroup\$ I prefer to view my code with tabs. Spaces are evil. \$\endgroup\$ – mbomb007 Feb 19 '16 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\$ – Mego Feb 19 '16 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 '16 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\$

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.