Sort a nested list

Question

You must write a program or function that sorts a nested list. Here are the rules for sorting a nested list:

Let's take this list as an example:

((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Each element in this list has a "priority". An element counts as a number or a sublist. First, get the priority of each element at the same depth. If an element is just a number, its priority is the same as the number itself. If an element is a sublist, its priority is the sum of all the numbers in it, not including any sub-sublists.

So, the priorities of all the elements of depth 1 are:

 (  7 )  2  7  (    3       )  9
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Sort each element by priority. If there is a tie, you must keep the same order as the original list.

 2  (     3      )  (  7 )  7  9
(2, (2, 1, (3, 4)), (5, 2), 7, 9) 

Repeat for every sublist. So on this sublist

(2, 1, (3, 4))

Our priorities look like:

 2  1  (  7  )
(2, 1, (3, 4))

So sorted, it looks like:

(1, 2, (3, 4))

(3, 4) is already sorted, so we're done. Repeat for (5, 2) which results in (2, 5) and we're done! Our final list is:

(2, (1, 2, (3, 4)), (2, 5), 7, 9) 

Rules:

• Highly doubtful, but just in case Mathematica has something for this, no nested list sorting builtins are allowed. Regular sorting functions are allowed.

• I/O can be in any reasonable format.

• Every sublist will contain at least one number or list. Also, sublists can be nested several levels deep. For example, in (1, 2, (((3)))) the (((3))) has a priority of 0, since it has only sublists in it.

• Invalid lists (unmatched parentheses, non-numbers, wrong bracket types, negative numbers, etc.) result in undefined behavior.

Test I/O:

(1, 2, 3) ---> (1, 2, 3)

(1, 2, 6, 3, 9, 8) ---> (1, 2, 3, 6, 8, 9)

(4, 3, (2), (1)) ---> ((1), (2), 3, 4)

(4, 3, (2), ((1))) ---> (((1)), (2), 3, 4)

(5, (1, 2, (9, 8))) ---> ((1, 2, (8, 9)), 5)

(3, (1, 2), (2, 1)) ---> (3, (1, 2), (1, 2))

(3, (1, 2, (99)), (2, 1, (34))) ---> (3, (1, 2, (99)), (1, 2, (34)))

(7, 2, (1, (9, 12)), (4, 3, 2, (1, 2))) ---> ((1, (9, 12)), 2, 7, (2, 3, (1, 2), 4))

Shortest answer in bytes wins.

Answer 1

Jelly, 13 bytes

fFSµ€Ụị߀µ¹<?

Try it online! or verify all test cases.

How it works

fFSµ€Ụị߀µ¹<?  Main link. Input: A (list)

   µ€          Apply the chain to the left to each item B in A.
 F             Flatten B.
f              Filter; intersect B with flattened B, yielding a list.
               This returns the numbers in B if B is a list, [B] if B is a number.
  S            Compute the sum of the resulting list.
     Ụ         Sort the indices of A according to the computed sums.
       ߀      Recursively apply the main link to each B in A.
      ị        Retrieve the items of the list (right) at those indices (left).
         µ     Convert the preceding chain into a single link.
            ?  If:
           <     A compared with itself is truthy:
                   Execute the link to the left.
          ¹      Else, apply the identity function to A.

Comparing (<) a number with itself yields 0 (falsy), but comparing a non-empty list with itself yields a list of 0's (truthy), so < can be used to distinguish numbers from lists.

Answer 2

Python 2, 114 101 78 73 62 bytes

k=lambda t:t*(t<[])or t.sort(key=k)or sum(z for z in t if[]>z)

I knew there was a better way to filter lists out.

Sorts a python list (and its sublists) in-place.

https://eval.in/540457 thanks @tac for letting me know in-place solutions are acceptable, and @xnor + @feersum for further optimizations!

Answer 3

Lua, 172 bytes

function p(a)if type(a)~="table"then return a end s(a)local t=0 for i,v in next,a do t=t+p(v)end return t end
function s(t)table.sort(t,function(a,b)return p(a)<p(b)end)end

The function s sorts a Lua table (a data structure that serves as a list among other things in Lua) in place according to the rules.

Answer 4

Mathematica, 50 bytes

#0/@SortBy[#,Tr@Cases[#,_Integer,{0,1}]&]~Check~#&

Simple recursive method that uses SortBy. Ignore the messages.

Answer 5

Haskell, 160 151 135 bytes

import Data.List
data T=N Int|T[T]deriving Show
p(N x)=x
p(T t)=sum$[x|N x<-t]
f(N x)=N x
f(T t)=T$sortBy((.p).compare.p)$map f$t

The first problem is nested lists. Haskell requires that all elements of a list have the same type; in particular, an integer and a list of integers aren't the same type. In other words, a variable-nested list isn't a list, it's a rose tree!

So first, we have to define a data type for rose trees:

data T = N Int | T [T]

(Strictly, deriving Show is only necessary if you want to see the results. But that's a technicality.) With this definition in place, we can write a list such as (1, 2, (3, 4)) as

T [N 1, N 2, T [N 3, N 4]]

which is considerably less readable. But whatever; it's a trivial, mechanical translation. Prefix every number with N and every subtree with T.

Now we need to compute priorities. This would be easy if the priority of a subtree was simple the sum of all elements it contains. That would be a trivial recursive loop. But since it isn't, we need to define two functions: one which recurses, and one which does not.

p (N x) = x
p (T t) = sum $ map q t

q (N x) = x
q _     = 0

If we were to sum all subelements, then q would not need to exist, saving a huge number of characters. Oh well!

Edit: Actually, several commentors point out that you can avoid q using a list comprehension: [ x | N x <- t]. Good call, guys!

(In fact, p would not need to exist either; we could have the compiler auto-generate an Ord instance for us in a handful of characters, and this default implementation would match the spec.)

Finally, we need to recursive over all sub-trees and sort them:

f (N x) = N x
f (T t) = T $ sortBy (\ x y -> compare (p x) (p y)) $ map f $ t

That is, f sorts a tree by recursively applying itself to all elements (map f), and then calling the sortBy function to sort the top-level. The first line says that sorting a number does nothing, and is necessary to terminate the recursion.

Answer 6

CLISP, 380 bytes

(defun q(L)(if(null L)L(append(append(q(car(s(cdr L)(car L))))(list(car L)))(q(cadr(s(cdr L)(car L))))))))(defun s(L E)(if(not(atom(car L)))(setq L(cons(q(car L))(cdr L))))(cond((null L)'(nil nil))((<(v(car L))E)(list(cons(car L)(car(s(cdr L)E)))(cadr(s(cdr L)E))))(T(list(car(s(cdr L)E))(cons(car L)(cadr(s(cdr L)E)))))))(defun v(L)(if(atom L)L(apply'+(remove-if-not #'atom L))))

Call the function q with a list.

I'm a lisp noob, please don't kill me^^

Answer 7

Pyth, 15 bytes

L?sIbbossI#NyMb

Test suite

A recursive function, that works as follows:

L?sIbbossI#NyMb
L                  define y(b):
 ?sIb              If b is an integer:          (invariant under the s function)
     b             Return it.
            yMb    Else, apply y recursively to all of the elements of b,
      o            Then sort b by
        sI#N       For each element, the elements of that list that are integers.
                   This is luckily a nop on integers.
       s           Summed.

Answer 8

Java, 219 bytes

import java.util.*;List f(List l){l.sort(Comparator.comparing(o->{if(o instanceof Integer)return(Integer)o;f((List)o);return((List) o).stream().filter(i->i instanceof Integer).mapToInt(i->(Integer)i).sum();}));return l;}

With line breaks:

import java.util.*;
List f(List l){
    l.sort(Comparator.comparing(o -> {
        if (o instanceof Integer)
            return (Integer) o;
        f((List) o);
        return ((List) o).stream().filter(i -> i instanceof Integer).mapToInt(i -> (Integer) i).sum();
    }));
    return l;
}

There's a lot of casting going on which really racks up the byte count. :P

Integer values are fed into a Comparator, and nested lists are sorted first before the sum of only the integer values are given to the Comparator. These values are how the Comparator determines their position within the list when it is sorted.

Try it here.

Answer 9

JavaScript (ES6), 86 bytes

f=a=>a.map?a.map(f).sort((a,b)=>p(a)-p(b),p=a=>a.map?a.map(a=>t+=a.map?0:a,t=0)|t:a):a

All that array checking :-(