16
\$\begingroup\$

Given a multidimensional, rectangular array of nonnegative integers, sort it at every depth (lexicographically), starting from the innermost.

For example, with this array:

[ [ [5, 1, 4], 
    [10, 7, 21] ], 
  [ [9, 20, 2],
    [4, 2, 19] ] ]

You'd sort at the deepest first:

[ [ [1, 4, 5], 
    [7, 10, 21] ], 
  [ [2, 9, 20],
    [2, 4, 19] ] ]

Then sort at the next depth, lexicographically:

[ [ [1, 4, 5], 
    [7, 10, 21] ], 
  [ [2, 4, 19], 
    [2, 9, 20] ] ]

lexicographic comparison of arrays means comparing the first element, and if they're equal comparing the second, and so on all the way down the line. Here we see that [2, 4, 19] is less than [2, 9, 20] because although the first elements are equal (2) the second aren't - 4 < 9.

Finally, sort at the top depth (lexicographically):

[ [ [1, 4, 5], 
    [7, 10, 21] ], 
  [ [2, 4, 19], 
    [2, 9, 20] ] ]

The first one is less than the second, because [1, 4, 5] is less than [2, 4, 19] because 1 is less than 2.

You may take the lengths of dimensions and/or depth of the array as well.

Testcases

[2, 1] -> [1, 2]
[[[10, 5, 9], [6, 4, 4]], [[2, 6, 3], [3, 3, 2]], [[3, 8, 6], [1, 5, 6]]] -> [[[1, 5, 6], [3, 6, 8]], [[2, 3, 3], [2, 3, 6]], [[4, 4, 6], [5, 9, 10]]]
[[[6, 9], [12, 17]], [[9, 6], [9, 8]]] -> [[[6, 9], [8, 9]], [[6, 9], [12, 17]]]
[[[9, 1], [2, 5]], [[8, 5], [3, 5]]] -> [[[1, 9], [2, 5]], [[3, 5], [5, 8]]]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is gonna sound weird, but can I assume the integers are smaller than 0x10ffff? \$\endgroup\$ Jan 23 at 22:05
  • 1
    \$\begingroup\$ @taRadvylfsriksushilani Aha, Unicode magic… \$\endgroup\$
    – Adám
    Jan 23 at 22:06

16 Answers 16

11
\$\begingroup\$

Python 2, 30 bytes (@SurculoseSputum)

def f(L):L>f<map(f,L)<L.sort()

Attempt This Online!

Old Python 2, 32 bytes (@ovs)

f=lambda s:s>f<s.sort(key=f)or s

Attempt This Online!

Old Python 2, 33 bytes (@ovs)

f=lambda s:s>[]<s.sort(key=f)or s

Attempt This Online!

Old Python 2, 34 bytes

f=lambda s:s>=[]<s.sort(key=f)or s

Attempt This Online!

This works by side-effect (of in-place sort). It uses comparison to [] as a type check and chained comparison to short circuit (in-place sort returns None, so the chained comparison will always fail)

\$\endgroup\$
11
  • 1
    \$\begingroup\$ @ovs thanks! Re your first point: I think we still need to return s otherwise sort will be asked to sort a bunch of Nones if there is any nesting. Or am I missing something? \$\endgroup\$
    – loopy walt
    Jan 23 at 22:43
  • 2
    \$\begingroup\$ For the comparison you can use the function f itself, which according to Python 2 weird ordering is more than any integer but less than a list. Regarding the output method I missed that you used the return values for sorting, my initial idea for solving this problem was using map to recurse and sorting afterwards, where you get away with returning None. \$\endgroup\$
    – ovs
    Jan 23 at 23:06
  • 1
    \$\begingroup\$ @solid.py It rearranges the original list in such a way that if you were to apply map(f,_) afterwards you would get a sorted list, \$\endgroup\$
    – loopy walt
    Jan 24 at 11:04
  • 1
    \$\begingroup\$ @solid.py I'm not 100% sure how this is actually implemented, but I'm fairly confident the following is a valid mental model: The key function, f say, is applied to each element of the sort argument l. The transformed list is then argsorted and the resulting order applied to the original list; one way to think of it is to form triples `(f(l[0]),0,l[0]), f(l[1]),1,l[1]),...), sort them and then return the last elements of the sorted triples. - the present case is special in that we ultimately do not want the original elements but the transformed ones. ... \$\endgroup\$
    – loopy walt
    Jan 24 at 16:40
  • 1
    \$\begingroup\$ @solid.py To enforce this behaviour we let f act in-place. However, we also need f to return the updated values because as we just learned sort sorts based on the values returned by f. \$\endgroup\$
    – loopy walt
    Jan 24 at 16:45
7
\$\begingroup\$

Jelly, 6 bytes

ߌḊ¡€Ṣ

Try it online!

How it works

ߌḊ¡€Ṣ - Main link f(M). Takes a multidimensional array M on the left
    €  - Over each inner element E of M:
 ŒḊ    -   Get its depth, D
ß  ¡   -   Call f(E) D times
     Ṣ - Sort the result

Essentially, as sorting is idempotent, f is also idempotent, and so we can apply it as many times as we want with no extra side effects. Therefore, we iterate over each element of M, depth-wise, apply f to it, then sort the result.

\$\endgroup\$
7
\$\begingroup\$

Wolfram Language (Mathematica), 18 bytes

Sort//@#/.Sort->D&

Try it online!

Essentially copied from this earlier answer. Relies on the array being rectangular; otherwise, LexicographicSort (introduced 12.3) is required instead

Sort//@#            sort all levels
        /.Sort->D   un-Sort atoms
\$\endgroup\$
5
  • \$\begingroup\$ Could you add an explanation? Normally I've seen // used like a pipe, and /@ as map, but I can't make sense of //@ here. Also, how does D (derivative) come into play? Is it something else here? \$\endgroup\$
    – Jonah
    Jan 24 at 1:00
  • 3
    \$\begingroup\$ @Jonah //@ is MapAll, and D is identity when called on a single argument. That last part is necessary since e.g. Sort[1] does not become 1. \$\endgroup\$
    – att
    Jan 24 at 1:22
  • \$\begingroup\$ Thanks! Followup q: Why is the identity version of D not documented here? Or does it somehow fall out of the 1st or 3rd case? \$\endgroup\$
    – Jonah
    Jan 24 at 2:02
  • 1
    \$\begingroup\$ @Jonah To be honest, I first found out while doing a brute-force search for identities. It does make sense in context of the 3rd case, though the presentation does imply that there needs to be at least one variable; deriving w.r.t. no variables is the same as not performing a derivation. \$\endgroup\$
    – att
    Jan 24 at 2:38
  • \$\begingroup\$ It is curious thatD doesn't throw an error when not given a differentiation variable. For example, you could also say Integrate@f is like doing an integration wrt no variables; but that returns an error rather than f. \$\endgroup\$
    – theorist
    Jan 25 at 2:53
6
\$\begingroup\$

APL (Dyalog Extended), 18 12 bytes

Anonymous prefix lambda. Takes list of lists… as argument.

{×≡⍵:∧∇¨⍵⋄⍵}

Try it online!

{} "dfn"; argument is :

× [if] signum of
 depth of
 argument
: (i.e. if the argument has depth) then:

   sort the
   recursion on
  ¨ each of
    the argument

 else:

   return the argument

\$\endgroup\$
4
\$\begingroup\$

SWI-Prolog, 72 59 49 bytes

f([H|T],S):-f(H,Q),f(T,R),msort([Q|R],S).
f(E,E).

Try it online!

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

Vyxal, 6 bytes

λ-[vxs

Try it Online!

-5 thanks to @emanresuA in vychat

Explained

λ-[vxs
λ      # a lambda that takes a single argument n and:
 -     #   subtracts n from itself (scalars return 0 which is falsey, lists return a list of 0s which is truthy) - borrowed from https://codegolf.stackexchange.com/a/241658/78850
  [    #  and if that item is a list
   vx  #    call this lambda on each item
     s #    and sort the result
\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 34 bytes

f(a)=if(#a',vecsort(apply(f,a)),a)

Try it online!

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

Ruby, 30 bytes

f=->b{b*0==0?b:b.map(&f).sort}

Try it online!

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

JavaScript, 70 64 bytes

f=x=>x.sort(g=(a,b)=>1/a?a-b:f(a).some((c,i)=>a=g(c,f(b)[i]))*a)

Try it online!

Saved 6 bytes thanks to tsh.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ f=x=>x.sort(g=(a,b)=>1/a?a-b:f(a).some((c,i)=>a=g(c,f(b)[i]))*a) \$\endgroup\$
    – tsh
    Jan 24 at 7:37
  • \$\begingroup\$ @tsh Nice one. Thanks! \$\endgroup\$ Jan 24 at 15:28
3
\$\begingroup\$

Python 3,  47  36 bytes

Saved 1 byte thanks to @Dialfrost, and 9 bytes thanks to @loopywalt

f=lambda l:l*0!=0==l.sort(key=f)or l
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 46 bytes \$\endgroup\$
    – DialFrost
    Jan 24 at 13:27
  • 1
    \$\begingroup\$ cheaper type check 40 bytes \$\endgroup\$
    – loopy walt
    Jan 24 at 20:24
  • 1
    \$\begingroup\$ @loopywalt Thank you so much, I'm also trying out l*0==[] atm, I think it achieves the same of reducing the list to an empty state, with one byte less. \$\endgroup\$
    – solid.py
    Jan 25 at 8:19
  • 1
    \$\begingroup\$ Good point! And you can save another one going l*0!=0. \$\endgroup\$
    – loopy walt
    Jan 25 at 8:39
  • 1
    \$\begingroup\$ While you're at it: 36. \$\endgroup\$
    – loopy walt
    Jan 25 at 8:47
2
\$\begingroup\$

J, 30 bytes

[:><@#\.@$(4 :'/:"x~y')&.>/@,<

Try it online!

Uses a single fold to explicitly sort each rank, in order. Requires an explicit verb since rank " is a conjunction.

Note: Could save 1 byte with {{ }} but it fails on TIO's J version.

J, 23 17 bytes, port of Adam's recursive APL solution

[:/:~$:^:(#@$)"_1

Try it online!

-6 thanks to ovs!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 17 bytes on the second one by using ^: instead of @.. \$\endgroup\$
    – ovs
    Jan 23 at 23:21
  • \$\begingroup\$ Nice one. Now, if you wish to play hard mode, please have a shot at this monstrosity. \$\endgroup\$
    – Jonah
    Jan 23 at 23:28
2
\$\begingroup\$

Haskell + hgl, 15 bytes

x=Fe<sr<m x*~|p

Takes input as a free monad of lists.

Explanation

In Haskell we use a free monad of lists. A very simplified definition would look like:

data Ragged a
  = Pur a
  | Fe [Ragged a]

It's either a terminal element (wrapped in Pur) or a list of more ragged lists (wrapped in Fe).

We could write the code then like:

x (Fe y)=
  Fe < sr < m x $ y
x (Pur y)=
  p y

In the Fe case we map x across the input to sort all lower levels, sort the result and wrap it back in a free.

In the pure case we just wrap it back in a pure using p.

Now hgl has a special operator to do this sort of case for us. We use the *~| operator which is the equivalent to a pattern match on the cases of a Free.

So now we rewrite both options as a function Fe<sr<m x and p and supply them as args to *~|.

We can't get rid of the x= this time because the definition is recursive.

Reflections

Wow, I couldn't get this one in point free. That's probably an issue.

hoF for hoistFree nearly is useful here. If we just wanted to for example reverse every level hoF rv would work fine. But we can't just place sr in there instead of rv. sr needs the elements to be Ord. Instead we have to do this.

There should probably be a version of hoist which allows this sort of thing. Would save 9 bytes here.

maF ::
  ( Functor f
  , Functor g
  )
    => (f (Free g a) -> g (Free g a)) -> Free f a -> Free g a
\$\endgroup\$
2
\$\begingroup\$

BQN, 13 bytesSBCS

⊢{∧⚇𝕨𝕩}´≡-↕∘≡

Run online!

{∧𝕊⍟≡¨𝕩} is a translation of J, {×≡𝕩?∧𝕊¨𝕩;𝕩} is a shorter direct translation of dyalog extended, but using the depth modifier is cooler.

-2 from Adam.

\$\endgroup\$
5
  • \$\begingroup\$ ⊢{∧⚇𝕨𝕩}´≡-↕∘≡ \$\endgroup\$
    – Adám
    Jan 24 at 8:11
  • 1
    \$\begingroup\$ The recursive version could be {∧𝕊⍟=˘𝕩} if you take an actual array \$\endgroup\$
    – ovs
    Jan 24 at 9:23
  • \$\begingroup\$ question says depth, so dunno if that will be right \$\endgroup\$
    – Razetime
    Jan 24 at 10:37
  • \$\begingroup\$ The input is a rectangular array, so it can be represented by an array. And = and ˘ for an array are the same as and ¨ for an equivalent nested list. This is the same as the 17 byter on the J answer. (That means {∧𝕊⍟≡¨𝕩} works for your current input format) \$\endgroup\$
    – ovs
    Jan 24 at 10:55
  • \$\begingroup\$ ah i see, i'll put it in \$\endgroup\$
    – Razetime
    Jan 24 at 11:38
2
\$\begingroup\$

05AB1E, 15 bytes

"ИÊi®δ.V}{"©.V

Try it online or verify all test cases.

Explanation:

As mentioned in similar challenges, 05AB1E lacks recursive functions unfortunately, making it pretty long by mimicking the behavior with a string and 05AB1E-eval.

"..."       # Push the recursive string mentioned below
     ©      # Store it in variable `®` (without popping)
      .V    # Evaluate and execute it as 05AB1E code
            # (after which the result is output implicitly)

Ð˜Ê         # Check that this is the maximum depth of this (inner) list:
Ð           #  Triplicate the current list
 ˜          #  Flatten the top copy
  Ê         #  Check that the top two copies are NOT equal
   i    }   # If this is truthy, so we've reached the maximum depth:
     δ      #  Map over each inner item:
    ® .V    #   Do a recursive call (by 05AB1E-evaluating string `®`)
         {  # Sort the list
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 22 bytes

!x::Int=x
!x=sort(.!x)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 49 bytes

⊞υθFυFιF⁼κ⁺⟦⟧κ⊞υκW∧υ⊟υ«≔⟦⟧ηWι⊞η⊟ιW⁻ηιF№η⌊κ⊞ι⌊κ»Iθ

Try it online! Link is to verbose version of code. Outputs using Charcoal's default output format, where depth 1 arrays print their elements on their own line but the arrays themselves are double-spaced from each other, then depth 2 arrays are triple-spaced from each other etc. Explanation:

⊞υθ

Start enumerating all of the arrays at each depth.

FυFι

Process all elements of each array.

F⁼κ⁺⟦⟧κ⊞υκ

If this element is itself an array then push it to the list of all arrays.

W∧υ⊟υ«

Process the list in reverse order.

≔⟦⟧ηWι⊞η⊟ι

Move the elements from this array into a temporary array.

W⁻ηιF№η⌊κ⊞ι⌊κ

Move them back in ascending order.

»Iθ

Output the final array.

\$\endgroup\$
3
  • \$\begingroup\$ neil how ru so good at this language and quick qns, how do you understand it? its not in english? \$\endgroup\$
    – DialFrost
    Jan 24 at 13:27
  • 1
    \$\begingroup\$ @DialFrost Verbose mode is almost readable. -v tells Charcoal to convert from Verbose mode to proper Charcoal, and -l tells it to print that before executing it. \$\endgroup\$
    – Neil
    Jan 24 at 13:34
  • \$\begingroup\$ oh ic thats why although i still dont understand this language haha \$\endgroup\$
    – DialFrost
    Jan 24 at 14:06

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.