# Sort a nested list

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))
``````

-
Can we assume the numbers are integers? – isaacg Mar 22 at 6:20
@isaacg Yes, you can. – Dr Green Eggs and Iron Man Mar 22 at 7:08

# Jelly, 13 bytes

``````fFSµ€Ụịß€µ¹<?
``````

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

-
0 is False, but a box of 0s is True, but an empty box is False. Interesting how Python works. :P – cat Mar 22 at 22:38
Looks like 25 bytes (when encoded in UTF-8) to me. – Rotsor Mar 26 at 18:42
@Rotsor That sounds about right. However, Jelly uses custom code page that encodes all 256 characters it understands as single bytes. – Dennis Mar 26 at 19:02

# Python 2, 1141017873 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!

-
Some more optimization: `k=lambda t:t*(t<[])or sum(z for z in t if[t.sort(key=k)]>z)`. – xnor Mar 22 at 7:38
@xnor I think that solution is not quite correct: eval.in/540447 . For this example, we recurse down to the first sublist and grab the initial `z` from it, 5. Then in the conditional, we sort the list we're iterating over(!), so when we grab the next z it is ALSO 5, leading to a sum of 10. We then sort the outer list with these keys and get [6, [1, 5]], which is incorrect as "If there is a tie, you must keep the same order as the original list." The interesting thing is we call `sort` on both lists twice, so this only happens on equal keys:if the sublist were less it would sort back. – Orez Mar 22 at 14:19
Good catch. It's funny that the iteration continues with the now-sorted list. I feel like there should still be a shorter way to stick in the `None` output of `t.sort(key=k)`, but I'm not seeing it. – xnor Mar 22 at 23:29
`False` is 0 for the purposes of `+` and by extension, `sum`. Can't think of how that saves bytes, though. – CalculatorFeline Mar 23 at 14:57
@CatsAreFluffy `list.sort` returns `None`, not `False`. – Dennis Mar 26 at 17:00

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

-
I love how `type(a)` returns a string – cat Mar 31 at 1:28
Finally an answer using Lua. – Leaky Nun Apr 2 at 8:33

# Mathematica, 50 bytes

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

Simple recursive method that uses `SortBy`. Ignore the messages.

-

# 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^^

-
Haha, I was hoping somebody would do it in lisp! – Dr Green Eggs and Iron Man Mar 22 at 17:26

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

-
`sortBy (\ x y -> compare (p x) (p y))` is just `sortOn p`. Use the infix version of map in `p`: `sum\$q<\$>t`. – nimi Mar 22 at 17:01
@nimi Where is `sortOn` defined? I've always wanted to know... – MathematicalOrchid Mar 22 at 17:17
– nimi Mar 22 at 17:26
@nimi Oh cool, so they finally added it to `base`? Neat. If I update GHC someday I'll look forward to that... – MathematicalOrchid Mar 22 at 17:30
you can still shave off some 16 bytes with the list comprehension trick, `p(T t)=sum[x|N x<-t]` and `data T=N Int|T[T]deriving Show`. :) – Will Ness Mar 24 at 14:33

# 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.
``````
-

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

-
Here is the same technique at 154 bytes `int f(List l){l.sort(Comparator.comparing(o->o instanceof Integer?(int)o:f((List)o)));return l.stream().mapToInt(o->o instanceof Integer?(int)o:0).sum();}` – Andreas Mar 22 at 22:38
I think there is a lot more to squeeze, too. – Andreas Mar 22 at 22:38
But there are a couple issues: you cannot explicitly convert `Object` to `int` like that, and the challenge seems to require that a list is output. – TNT Mar 22 at 23:19
You actually save 1 byte by changing the instanceof to check for List instead of Integer. Integer is 7 bytes w/o curly braces, but List is 6 bytes with it. – Blue Mar 23 at 11:23
@TNT You can cast an Object to a primitive in java 1.7 or higher. Of course if the Object is null you'll get a npe. I don't see any problem with sorting the list in place, the challenge doesn't seem to speak to the issue directly. – Andreas Mar 23 at 16:14

## 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 :-(

-
`map.map.map.map.map.map.map.map.map` – cat Mar 22 at 22:30