Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Can we assume the numbers are integers? – isaacg Mar 22 at 6:20
    
@isaacg Yes, you can. – Dr Green Eggs and Ham DJ Mar 22 at 7:08
up vote 5 down vote accepted

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.

share|improve this answer
    
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, 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!

share|improve this answer
1  
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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
    
Haha, I was hoping somebody would do it in lisp! – Dr Green Eggs and Ham DJ Mar 22 at 17:26

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.

share|improve this answer
1  
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
    
Data.List since 4.8.0.0. – 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
2  
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.
share|improve this answer

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.

share|improve this answer
1  
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 :-(

share|improve this answer
    
map.map.map.map.map.map.map.map.map – cat Mar 22 at 22:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.