23
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can we assume the numbers are integers? \$\endgroup\$ – isaacg Mar 22 '16 at 6:20
  • \$\begingroup\$ @isaacg Yes, you can. \$\endgroup\$ – DJMcMayhem Mar 22 '16 at 7:08
5
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Some more optimization: k=lambda t:t*(t<[])or sum(z for z in t if[t.sort(key=k)]>z). \$\endgroup\$ – xnor Mar 22 '16 at 7:38
  • \$\begingroup\$ @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. \$\endgroup\$ – Orez Mar 22 '16 at 14:19
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Mar 22 '16 at 23:29
  • \$\begingroup\$ False is 0 for the purposes of + and by extension, sum. Can't think of how that saves bytes, though. \$\endgroup\$ – CalculatorFeline Mar 23 '16 at 14:57
  • \$\begingroup\$ @CatsAreFluffy list.sort returns None, not False. \$\endgroup\$ – Dennis Mar 26 '16 at 17:00
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I love how type(a) returns a string \$\endgroup\$ – cat Mar 31 '16 at 1:28
  • \$\begingroup\$ Finally an answer using Lua. \$\endgroup\$ – Leaky Nun Apr 2 '16 at 8:33
3
\$\begingroup\$

Mathematica, 50 bytes

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

Simple recursive method that uses SortBy. Ignore the messages.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ sortBy (\ x y -> compare (p x) (p y)) is just sortOn p. Use the infix version of map in p: sum$q<$>t. \$\endgroup\$ – nimi Mar 22 '16 at 17:01
  • \$\begingroup\$ @nimi Where is sortOn defined? I've always wanted to know... \$\endgroup\$ – MathematicalOrchid Mar 22 '16 at 17:17
  • \$\begingroup\$ Data.List since 4.8.0.0. \$\endgroup\$ – nimi Mar 22 '16 at 17:26
  • 2
    \$\begingroup\$ 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. :) \$\endgroup\$ – Will Ness Mar 24 '16 at 14:33
  • 1
    \$\begingroup\$ have you included 2 bytes for each newline in your count? I think we're allowed to count them as singles. Also, there's no need for $ in sum$[x|N x<-t]. So, 135-5-1=129. :) \$\endgroup\$ – Will Ness Jul 31 '16 at 12:37
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Haha, I was hoping somebody would do it in lisp! \$\endgroup\$ – DJMcMayhem Mar 22 '16 at 17:26
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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();} \$\endgroup\$ – Andreas Mar 22 '16 at 22:38
  • \$\begingroup\$ I think there is a lot more to squeeze, too. \$\endgroup\$ – Andreas Mar 22 '16 at 22:38
  • \$\begingroup\$ 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. \$\endgroup\$ – TNT Mar 22 '16 at 23:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Blue Mar 23 '16 at 11:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Andreas Mar 23 '16 at 16:14
0
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ map.map.map.map.map.map.map.map.map \$\endgroup\$ – cat Mar 22 '16 at 22:30

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.