42
\$\begingroup\$

As described in this question:

Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

To use one of their test cases, an input of {1, 2, 5, 4, 3, 7} yields {1, 2, 5, 7}, as 4 and 3 are both dropped for being smaller than the previously "sorted" value, 5.

We don't want "sorting" algorithms, we want them to be the real deal. Therefore, I want you to write a program that, given a list of numbers, outputs a list of DropSorted lists (to be a complete sorting algorithm, we would need to merge these lists, but merging two sorted lists has been done before, and asking you to do it again is pretty much asking two questions, so this question is specifically the "splitting" step of our complete DropSort).

The arrangement and content of our lists is crucial, however. The output of your program must be equivalent to the output of a DropSort, followed by a DropSort of the discarded values, and so on until you have only have a list of sorted chains. Again, borrowing the existing test suite (and adding two more):

Input                  -> Output
{1, 2, 5, 4, 3, 7}     -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12}           -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5}        -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21}       -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10}    -> {{10, 10, 10, 10}, {9}}  //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6}     -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7}     -> {{0, 2, 5, 7}, {4}, {0}}

You may assume the input is non-empty.

This is , so standard rules apply!

\$\endgroup\$
5
  • \$\begingroup\$ Can we output like [5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]? \$\endgroup\$
    – Mr. Xcoder
    Aug 4 '17 at 12:59
  • 5
    \$\begingroup\$ @Xcoder, well I don't mind the syntax, but you still have to sort the second list (and split it in this case). Knowing when to stop is part of the challenge ;). And Stewie, I don't really know what to tell you. I saw the DropSort challenge and thought this sounded fun. Any chance you used your time machine to jump ahead and see this question? Just don't use it to see the best answer! \$\endgroup\$ Aug 4 '17 at 13:09
  • \$\begingroup\$ Note that adding the sorting of the left-overs takes the solutions out of linear time. \$\endgroup\$
    – ikegami
    Aug 6 '17 at 22:51
  • \$\begingroup\$ Should {3,4,5,3,4,5,3,4,5} result in {{3,4,5,5,5},{3,4,4},{3}}? \$\endgroup\$
    – QBrute
    Aug 7 '17 at 10:00
  • \$\begingroup\$ @QBrute I think that's right. \$\endgroup\$ Aug 7 '17 at 12:35

24 Answers 24

23
\$\begingroup\$

Haskell, 67 59 58 bytes

(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]

Explanation: Given a list of lists (that are already sorted) and a value x, the ! operator will place x at the end of the first list whose last element is less than or equal to x. If no such list exists, the list [x] is placed at the end.

Try it online.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ This is an incredibly clever solution. I honestly expected most people to just DropSort over and over until there was nothing left, but I hoped someone would think of a more creative way. \$\endgroup\$ Aug 4 '17 at 14:09
14
\$\begingroup\$

Husk, 10 bytes

hUmü<¡Ṡ-ü<

Try it online!

This is a combination of my other Husk answer and xnor's Haskell answer. The duplicate ü< feels clunky, but I don't know how to get rid of it...

Explanation

The function ü< translates to nubBy(>) in Haskell. It traverses a list from left to right, keeping those elements for which no previously kept element is strictly greater. In other words, it performs dropsort. The leftover elements are obtained by taking list difference of the original list and the result of ü<.

hUmü<¡Ṡ-ü<  Implicit input, say x = [2,3,5,4,4,2,7].
     ¡      Iterate
      Ṡ-    list difference between argument
        ü<  and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
  m         Map
   ü<       dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
 U          Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h           Drop last element: [[2,3,5,7],[4,4],[2]]
\$\endgroup\$
1
  • 11
    \$\begingroup\$ Outgolfs top answer by 33% "I dunno, it feels clunky" \$\endgroup\$ Aug 4 '17 at 20:21
11
\$\begingroup\$

Haskell, 50 bytes

import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I nearly had this, just didn't know the \\ function : ( \$\endgroup\$
    – H.PWiz
    Aug 4 '17 at 18:15
  • 2
    \$\begingroup\$ Oh that is indeed a very handy function! Very nice solution=) \$\endgroup\$
    – flawr
    Aug 5 '17 at 8:44
10
\$\begingroup\$

MATL, 15 10 9 bytes

5 bytes off using @beaker's idea of cumulative maximum

t"ttY>=&)

Input is a numeric row vector, in the format [1, 2, 5, 4, 3, 7] (commas are optional). The output contains lists separated by newlines, with the numbers in each list separated by spaces.

Try it online! Or verify all test cases.

Explanation

Given an array, the code picks from it every entry that equals the cumulative maximum up to that entry.

For example, given

1 2 5 4 3 7

the code picks the first, second, third and sixth entries:

1 2 5     7

Then the process is repeated on the subarray formed by the remaining entries (in the original order):

      4 3

This needs to be done until the subarray of remaining entries is empty. An upper bound on the required number of iterations is the input size. The last iterations may not be needed. In that case they operate on an empty array, producing additional empty arrays.

At the end, the stack contains the required arrays and possibly several empty arrays, which are not displayed at all.

t        % Implicit input. Duplicate
"        % Do as many times as the input size
  tt     %   Duplicate twice
  Y>     %   Cumulative maximum
  =      %   Compare for equality. Will be used as logical index
  &)     %   Two-output indexing: pushes indexed subarray, and then
         %   a subarray with the remaining entries
         % End (implicit)
         % Display stack (implicit). Empty arrays are not displayed
\$\endgroup\$
7
\$\begingroup\$

Husk, 16 bytes

hUm₁≤¡₁>
ṠfSz⁰G▲

Try it online!

Explanation

This first line is the main function, and the second is a higher order helper function (it takes a function as argument and returns a new function). It's accessed by the subscript . The idea is that ₁≤ performs dropsort and ₁> gives the leftover elements.

ṠfSz⁰G▲  Helper function, takes binary function p (as ⁰) and list x (implicit).
         For example, p = (≤) and x = [2,4,3,4,5,2].
     G▲  Left scan on x with maximum: [2,4,4,4,5,5].
  Sz     Zip with x
    ⁰    using the function p: [1,1,0,1,1,0].
Ṡf       Keep elements of x at truthy indices: [2,4,4,5].

In the main function, we iterate the leftovers function ₁> and apply the dropsort function ₁≤ to the results.

hUm₁≤¡₁>  Main function, implicit list argument, say x = [2,4,3,4,5,2].
     ¡    Iterate
      ₁>  the leftovers function: [[2,4,3,4,5,2],[3,2],[2],[],[],[],...
  m       Map
   ₁≤     the dropsort function: [[2,4,4,5],[3],[2],[],[],[],...
 U        Prefix of unique elements: [[2,4,4,5],[3],[2],[]]
h         Drop last element (an empty list): [[2,4,4,5],[3],[2]]
\$\endgroup\$
2
  • \$\begingroup\$ Husk is the new Jelly... \$\endgroup\$ Aug 4 '17 at 14:01
  • 1
    \$\begingroup\$ @EriktheOutgolfer Beaten by MATL. :/ \$\endgroup\$
    – Zgarb
    Aug 4 '17 at 15:42
6
\$\begingroup\$

Python 3, 131 112 103 95 bytes

Thanks a lot @Mr. Xcoder for a smashing 19 bytes!!

Thanks a lot @ovs for an amazing 17 bytes!

def f(x):
 a,*x=x or[0];m=[a];d=[]
 for i in x:[m,d][i<m[-1]]+=i,
 return[m]+(x and(d>[])*f(d))

Try it online!

Explanation:

def f(x):               #recursive function taking list, returns list of lists 
 if len(x)<2:return[x]  #for a single element return [element] 
 m=[x[0]];d=[]          #initialize main and dropped lists
 for i in x[1:]:[m,d][i<m[-1]]+=[i]  #append elements from the argument list accordingly into main and dropped list 
 return[m]+(d>[])*list(f(d)) #add main-list along with further evaluated dropped-list(recursived) into a list of lists
\$\endgroup\$
8
  • 2
    \$\begingroup\$ 116 bytes. The if-else can be collapsed into [m,d][i<m[-1]]+=[i]. \$\endgroup\$
    – Mr. Xcoder
    Aug 4 '17 at 13:18
  • \$\begingroup\$ Woah , Thanks a lot... I was tryng that [m,d] thing but it was not working somehow.... \$\endgroup\$ Aug 4 '17 at 13:20
  • 1
    \$\begingroup\$ 113 bytes. (len(d)>0) is bool(d), because empty lists are falsy in Python. +1, Nice solution! \$\