41
\$\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\$
  • \$\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\$ – Lord Farquaad 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\$ – Lord Farquaad Aug 7 '17 at 12:35

25 Answers 25

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\$
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\$
  • 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\$ – Lord Farquaad Aug 4 '17 at 14:09
13
\$\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\$
  • 10
    \$\begingroup\$ Outgolfs top answer by 33% "I dunno, it feels clunky" \$\endgroup\$ – Lord Farquaad 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\$
  • 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
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\$
  • \$\begingroup\$ Husk is the new Jelly... \$\endgroup\$ – Erik the Outgolfer 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\$
  • 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\$ – officialaimm 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! \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 13:22
  • 1
    \$\begingroup\$ 95 bytes \$\endgroup\$ – ovs Aug 6 '17 at 21:51
  • 2
    \$\begingroup\$ i, is just a short for (i,), which is a tuple containing a. a,*x = x or [0] is python3's extended unpacking. Here is an helpful SO post on this topic with some examples. \$\endgroup\$ – ovs Aug 7 '17 at 9:10
6
\$\begingroup\$

Haskell, 113 107 102 92 bytes

import Data.List
a!(b:c)|b<last a=a!c|1>0=a++[b]!c
a!b=a
g x@(b:c)|i<-[b]!c=i:g(x\\i)
g x=[]

Try it online!

This feels really long.

Explanation

! performs the drop sort on a list, while # collects the trimmings. g then repeatedly applies # until the list is empty recording the results in a list.

\$\endgroup\$
  • 1
    \$\begingroup\$ Replacing head a with a!!0 saves a byte. \$\endgroup\$ – tomsmeding Aug 4 '17 at 21:35
5
\$\begingroup\$

APL, 27 bytes

{⍵≡⍬:⍬⋄(⊂X/⍵),∇⍵/⍨~X←⍵≥⌈\⍵}

Explanation:

  • ⍵≡⍬:⍬: if the input is empty, return the empty list
  • X←⍵≥⌈\⍵: all numbers greater or equal to the running maximum
  • (⊂X/⍵): the list of those numbers,
  • ∇⍵/⍨~X: followed by the result of running this function on the remaining numbers
\$\endgroup\$
  • \$\begingroup\$ Save a byte with {⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}. Morten is getting worried by the lack of response to his emails. Is everything alright? \$\endgroup\$ – Adám Sep 6 '17 at 11:06
  • \$\begingroup\$ Oh dear. I'm happy to here that you managed. See you next week. \$\endgroup\$ – Adám Sep 7 '17 at 9:05
4
\$\begingroup\$

JavaScript (ES6), 64 bytes

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

Ungolfed:

f=(a,l,r=[])=>
  a+a&&                                    //any elements left?
  [a.filter(                               //filter elements that are in order,
    e=>e<l?!r.push(e):(l=e,1)              //push unsorted elements to r
   ),                                      //push() returns the new length of the array,
                                           //... so !push() will always return false
   ...f(r)                                 //recurse on r
  ]

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

console.log(JSON.stringify(f([1, 2, 5, 4, 3, 7])));     // [1, 2, 5, 7][4][3]
console.log(JSON.stringify(f([10, -1, 12])));           // [10, 12][-1]
console.log(JSON.stringify(f([-7, -8, -5, 0, -1, 1]))); // [-7, -5, 0, 1][-8, -1]
console.log(JSON.stringify(f([9, 8, 7, 6, 5])));        // [9][8][7][6][5]
console.log(JSON.stringify(f([10, 13, 17, 21])));       // [10, 13, 17, 21]
console.log(JSON.stringify(f([10, 10, 10, 9, 10])));    // [10, 10, 10, 10][9]
console.log(JSON.stringify(f([5, 4, 3, 8, 7, 6])));     // [5, 8][4, 7][3, 6]
console.log(JSON.stringify(f([0, 2, 5, 4, 0, 7])));     // [0,2,5,7],[4],[0]

\$\endgroup\$
  • 1
    \$\begingroup\$ For a split second there I thought ?! was some fancy new operator... \$\endgroup\$ – Neil Aug 4 '17 at 15:06
  • \$\begingroup\$ Ha, yeah, I should have included an explanation. Now added. \$\endgroup\$ – Rick Hitchcock Aug 4 '17 at 15:16
  • \$\begingroup\$ @Neil ?! \$\endgroup\$ – Patrick Roberts Aug 4 '17 at 15:41
  • \$\begingroup\$ (i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o] Apparently, great minds think (kind of) alike. Unfortunately I can't seem to shave off any more bytes... Just noting, you can remove f= in your code, and maybe my code might give you some ideas on how to golf yours even more. \$\endgroup\$ – David Archibald Aug 5 '17 at 21:22
  • \$\begingroup\$ Thanks, @DavidArchibald. I can't remove f= from my code, because it's recursive. Yours is an interesting approach, but it doesn't seem to work for a couple of the test cases. For example, it returns [[5,8],[4],[3],[7],[6]] for the next-to-last case. \$\endgroup\$ – Rick Hitchcock Aug 5 '17 at 22:26
4
\$\begingroup\$

R, 61 bytes

f=function(x)if(sum(x|1)){print(x[b<-x==cummax(x)]);f(x[!b])}

Try it online!

Recursive function. sum(x|1) is shorthand for length(x), so this recursion will run untill x is empty. cummax takes the cumulative maximum of x, which is then compared to x again. This produces a boolean vector of length x, where all the TRUEs correspond to sorted values. We use that to take a subset of x and print it. The function is then called again on the remainder of x.

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

Java 8, 182 179 177 bytes

import java.util.*;l->{List r=new Stack(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Stack()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}

-3 bytes thanks to @Nevay.
-2 bytes by using Stack instead of Vector.

Explanation:

Try it here.

import java.util.*;            // Required import for List and Vector
l->{                           // Method with ArrayList<Integer> parameter and List return-type
  List r=new Stack(),          //  Return-List
       t;                      //  Temp-List
  for(int p,i,x;               //  Some temp integers
      l.size()>0;)             //  Loop (1) as long as there are still items left in the list
    for(p=l.get(0),            //   Set `p` to the first item of the list
        r.add(t=new Stack()),  //   Add a new inner List to the result-List
        i=0;i<l.size();        //   Inner loop (2) from 0 to the size of the list (exclusive)
         p=x)                  //     After every iteration, save the previous value in `p`
      if((x=l.get(i++))>=p)    //    If the current item is equal or larger than the previous:
        t.add(l.remove(--i));  //     Add it to the temp-List, and remove it from the input-List
                               //   End of inner loop (2) (implicit / single-line body)
                               //  End of loop (1) (implicit / single-line body)
  return r;                    //  Return result-List
}                              // End of method
\$\endgroup\$
  • \$\begingroup\$ Can you use try{}catch{} instead of checking against l.size() to save some? \$\endgroup\$ – TheLethalCoder Aug 4 '17 at 14:33
  • 1
    \$\begingroup\$ You can start the inner loop at 0 and remove the brackets of the outer for-loop l->{List r=new Vector(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Vector()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;} (-3 bytes). \$\endgroup\$ – Nevay Aug 9 '17 at 15:23
3
\$\begingroup\$

C#, 188 203 bytes

int[][]f(int[]a){int[]t=a.Where((n,i)=>i<1||n>=a[i-1]).ToArray(),m=a.Where((n,i)=>i>0&&n<a[i-1]).ToArray();var s=new int[][]{t}.ToList();if(m.Any())s.AddRange(f(m));return s.ToArray();}

The byte count includes +18 for:

using System.Linq;

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @RickHitchcock Fixed at the cost of 15 bytes! Nice spot. \$\endgroup\$ – TheLethalCoder Aug 4 '17 at 14:22
  • \$\begingroup\$ Good job : ) +1 \$\endgroup\$ – Rick Hitchcock Aug 4 '17 at 14:22
3
\$\begingroup\$

C++14, 118 108 bytes

Using the algorithm from w0lf's Haskell answer.

As unnamed generic lambda. First parameter is a container of the values to dropsort (like vector<int>) and second parameter requires a compatible empty container of containers (like vector<vector<int>>) for the return value via reference.

In the first version of the program, there was R.clear;() as first statement, so that the container of containers didnt need to be empty. Peter Cordes thought this could into the specification, so dropping 10 byte for that.

[](auto A,auto&R){for(auto x:A){for(auto&D:R)if(D.back()<x){D.push_back(x);goto F;}R.emplace_back(1,x);F:;}}

Try it online!

Ungolfed:

[](auto A,auto&R){
 for(auto x:A){       //foreach item
  for(auto&D:R)       //foreach result list
   if(D.back()<x){    //x bigger than last element
    D.push_back(x);   //add x
    goto F;           //break and jump over the emplace
   }
  R.emplace_back(1,x);//create new list with this element
  F:;
 }
}
\$\endgroup\$
  • \$\begingroup\$ You can probably get away with omitting the R.clear(), and just require the caller to start with an empty container. \$\endgroup\$ – Peter Cordes Aug 6 '17 at 22:11
  • \$\begingroup\$ @PeterCordes good idea, i might respec my other C++ answers which featured return via reference parameter. \$\endgroup\$ – Karl Napf Aug 7 '17 at 5:20
2
\$\begingroup\$

Python 2, 88 bytes

-4 bytes thanks to Arnold Palmer

b,r=input(),[]
for i in b:
 for l in r:
	if l[-1]<=i:l+=[i];break
 else:r+=[[i]]
print r

Try it online!

Solution similar to @w0lf's haskell [answer][1]

Rare use case for for-else construction

Iterate through sorted lists for l in r (empty at start).
If element(from input) i is larger than last element of list l[-1], add element to list l+=[i], break.
If no list was accepted, add new list with this elemens r+=[[i]]

\$\endgroup\$
  • 1
    \$\begingroup\$ 88 bytes by just taking it out of its function. \$\endgroup\$ – Arnold Palmer Aug 4 '17 at 19:10
1
\$\begingroup\$

R, Work in progress (89, but failing)

Holding some work here, because I backed myself into a corner using %in% (It fails on duplicate entries, in particular the last test case), and I need to go do other things now, but this is here if anybody wants to build on it:

z=function(x){if(length(x)){a=x[x>=cummax(x)]
append(list(a),z(x[!(x%in%a)]))}else{NULL}}

Ungolfed:

z=function(x){
  if(length(x)){
    a=x[x>=cummax(x)]
    append(list(a),z(x[!(x%in%a)]))
  } else {
    NULL
  }
}
\$\endgroup\$
  • \$\begingroup\$ you should probably delete this for the time being so you don't get downvotes while you're fixing it. \$\endgroup\$ – Giuseppe Aug 4 '17 at 15:59
  • 1
    \$\begingroup\$ z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL) works \$\endgroup\$ – Giuseppe Aug 4 '17 at 16:05
  • \$\begingroup\$ the space between ] and c is a newline (or semicolon) \$\endgroup\$ – Giuseppe Aug 4 '17 at 16:18
  • \$\begingroup\$ I've never seen "if" before, but I'm pretty new to R golfing. You should post as your own answer, and I can take mine down. I like what you did with the i index, to get around the %in% problem. \$\endgroup\$ – Alex Axthelm Aug 4 '17 at 17:37
  • \$\begingroup\$ Nah, you did all the hard work! I couldn't wrap my head around this problem until I saw your implementation--I would never have remembered cummax! \$\endgroup\$ – Giuseppe Aug 4 '17 at 17:38
1
\$\begingroup\$

JavaScript (ES6), 71 70 68 bytes

a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o

Pretty simple, just iterates the array, looks for the first inner array whose last value is <= to the next value to drop, if none exists, append a new inner array with the next value to the output, otherwise append the next value to the first found inner array that matches the condition.

Updates

Thanks to Neil, saved three bytes converting (...,o) to ...&&o and re-organizing the callback to map() to be more compact.

f=a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o;[[1,2,5,4,3,7],[10,-1,12],[-7,-8,-5,0,-1,1],[9,8,7,6,5],[10,13,17,21],[10,10,10,9,10],[5,4,3,8,7,6],[0,2,5,4,0,7]].map(f).map(JSON.stringify).map(v=>console.log(v))
.as-console-wrapper{max-height:100%!important}

\$\endgroup\$
  • 1
    \$\begingroup\$ &&o is a byte shorter than (,o). \$\endgroup\$ – Neil Aug 4 '17 at 15:21
  • \$\begingroup\$ @Neil gah! Great catch, thank you \$\endgroup\$ – Patrick Roberts Aug 4 '17 at 15:27
  • 1
    \$\begingroup\$ I like your [...b].pop(), but I think (o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n) saves you a byte or two. \$\endgroup\$ – Neil Aug 4 '17 at 15:30
  • \$\begingroup\$ At this rate, I'll feel obligated to mark this as a community post... damn \$\endgroup\$ – Patrick Roberts Aug 4 '17 at 15:38
  • \$\begingroup\$ Just because of a couple of tweaks? It's still basically the same code... \$\endgroup\$ – Neil Aug 4 '17 at 18:29
1
\$\begingroup\$

Japt, 29 bytes

@lOpP)<1}a@=f_<VªOoV=Z+S}V=Ug

Test it online!

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

C (gcc), 176 175 173 bytes

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;main(a){while(scanf("%d",*l+w)>0)++w;while(i=w){P(l[a=!a][w=0])for(j=1;j<i;++j){x=l[a][j];x<t?l[!a][w++]=x:P(x)}puts("");}}

Try it online!

Somewhat readable version:

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;
main(a)
{
    while(scanf("%d",*l+w)>0)++w;
    while(i=w)
    {
        P(l[a=!a][w=0])
        for(j=1;j<i;++j)
        {
            x=l[a][j];
            x<t?l[!a][w++]=x:P(x)
        }
        puts("");
    }
}
\$\endgroup\$
  • \$\begingroup\$ 175 bytes. \$\endgroup\$ – Mr. Xcoder Aug 4 '17 at 13:53
  • \$\begingroup\$ Uhh, of course, how stupid -- thanks! \$\endgroup\$ – Felix Palmen Aug 4 '17 at 13:55
1
\$\begingroup\$

PHP, 91 103 96 85 bytes

(Edited to add 12 chars of print_r($r); to meet requirement to output)
(Edited to remove 7 bytes when allowing PHP Errors)
(Edited to remove 11 bytes when golfing the assignment further)

while($a){$b=$d=[];foreach($a as$i)${max($b)>$i?d:b}[]=$i;$a=$d;$r[]=$b;}print_r($r);

Given input $a, it produces result $r

Pretty:

while ($a) {
    $b = $d = [];
    foreach ($a as $i) {
        ${max($b) > $i ? d : b}[] = $i;
    }
    $a   = $d;
    $r[] = $b;
}

The pseudo-recursive outer loop initializes the keep $b and discard $d arrays to empty, then does a basic drop sort loop, finally setting the discards as the new input and adding the keeps to the result $r

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

PHP, 102 bytes, 98 bytes

<?php function s($i){static$s;foreach($i as$v)${$v<max($l)?f:l}[]=$v;$s[]=$l;!$f?:s($f);return$s;}

Try it online!

-4 bytes, thanks to @Umbrella

Explanation

<?php

The function takes the input list as an array.

function s($i) {

$s, which will become the finally returned list of lists, is declared static. This extends its scope to all calls of this function, allowing the function to be called recursively without having to pass this result list as an argument or to return it.

    static $s;

Loop through each value in the list.

    foreach ($i as $v)

Is it less than the biggest current list member?

        $v < max($l) ?

Yes, put it on list $f for further sorting.

                        $f[] = $v :

No, put it on list $l.

                        $l[] = $v;

Push list $l onto the list of lists.

    $s[] = $l;

If there's anything in list $f, send it round again for further sorting.

    !$f ?: s($f);

Return the list of lists.

    return $s;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Accounting for the 31 chars I left out as <?php function d($a){return$r;}, you heartily crushed me. Aside, I just realized we both forgot to output. \$\endgroup\$ – Umbrella Aug 7 '17 at 14:04
  • \$\begingroup\$ I've been golfing my solution down to try to beat yours without using yours and I found a way yours can be improved: I think you can save four characters by replacing $v<max($l)?$f[]=$v:$l[]=$v; with ${$v<max($l)?f:l}[]=$v; -- at least, it works in my tests. \$\endgroup\$ – Umbrella Aug 7 '17 at 19:50
  • \$\begingroup\$ @Umbrella, isn't returning, outputting??? And thanks for those 4 bytes. I never think of working like that, using code to evaluate the variable name. I must remember to consider that in future challenges… 🤔 \$\endgroup\$ – WebSmithery Aug 13 '17 at 15:51
  • \$\begingroup\$ Found it, consensus seems to accept returning as output: codegolf.meta.stackexchange.com/questions/2447/… \$\endgroup\$ – Umbrella Aug 14 '17 at 18:07
0
\$\begingroup\$

Sage, 102 bytes

def f(w,a=[]):
 for x in w:
  q,c=exists(a,lambda b:b[-1]<=x)
  if q:c+=[x]
  else:a+=[[x]]
 return a

Very similar to @Dead Possum's answer.
Appends each member x of w to the first list in a {list of lists} with x greater than it's last element.
if none, appends [x] to a.

I would really like it if exists returned a if nothing was found! Also trying to apply @officialaimm's one-line idea ...

Question: If I removed my code from the function, I'd have to assign w to input right? So would it save bytes?

\$\endgroup\$
0
\$\begingroup\$

Ocaml, 69 62 bytes

let rec d=function h::i::t when h>i->d(h::t)|h::t->h::d t|x->x

Explanation:

let rec d = function (* Implicitly take an list as a parameter *)
    (* If the list starts with two elements h and i and h is greater than i, drop i and sort the list starting with h and the rest t *)
    | h::i::t when h > i -> d (h::t) 
    (* If h is not greater than i, make a new list starting with h and a tail containing the drop sorted rest *)
    | h::t -> h::d t
    (* If none of the cases apply, the list is empty. *)
    | x -> x
\$\endgroup\$
0
\$\begingroup\$

APL, 100 88 83 79 78 57 56 77 76 bytes

{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)}

-0 bytes thanks to Kritixi Lithos...

Try it online!

There's got to be some better way to do this (There is). Any tips are very greatly appreciated and welcome.

How?

(Note, some of this explanation might be wrong, as I forgot how this worked)

{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)} - separate the argument into nested drop-sorts
{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}  - un-nesting (passed the result of the above)
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘     - fixing array mishaps (passed the result of the above)
\$\endgroup\$
  • \$\begingroup\$ {⍬≢⍴⍵} can become (⍬≢⍴) \$\endgroup\$ – Cows quack Aug 6 '17 at 14:51
  • \$\begingroup\$ ALready did that without seeing your comment, \$\endgroup\$ – Zacharý Aug 6 '17 at 14:55
  • \$\begingroup\$ What is the purpose of {(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}? It seems to be separated from everything else \$\endgroup\$ – Cows quack Aug 6 '17 at 14:55
  • \$\begingroup\$ Without it, the first test case would be something like [[1,2,5,7],[4],3], instead of the required [[1,2,5,7],[4],[3]]. \$\endgroup\$ – Zacharý Aug 6 '17 at 14:57
  • \$\begingroup\$ You might be able to shorten that dfn to just (,¨) \$\endgroup\$ – Cows quack Aug 6 '17 at 14:59
0
\$\begingroup\$

Jelly, 26 bytes

<»\¬x@ðW;µ⁸Ñ
<»\x@µÑ
1Ŀ¹L?

This is the same method as marinus' APL answer.

Try it online!.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 125 109 106 bytes

-16 18 bytes from Zacharý

-1 by removing { and } by changing the incrementer to include the "set last to the current"

m=x=>{z=[[],[]];l=NaN;for(i=0;i<x.length;l=x[i++])if(l>x[i])z[1].push(x[i]);else z[0].push(x[i]);return z}

Basically, asks is the current item greater than the last item, add to the first list. Otherwise, add to the second.

Found out during this that comparing any number to NaN will always result false. Interesting!

Explanation:

m = x => {                         // Create function
  z = [[], []];                      // Initialize dropsort output
  l = NaN;                           // Initialize last element
  for (i = 0; i < x.length; l=x[i++])// For each item in input...
    if (l > x[i])                    // If current item is greater than previous
      z[1].push(x[i]);               // Then add it to the first part of output
    else                             // Elsewise
      z[0].push(x[i]);               // Add it to the nonordered part of the dropsort
                                     // Set last item to current item
  }                                  // Repeat
  return z                           // Return finished dropsort
}                                    // End function

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Do you have to use var? \$\endgroup\$ – Zacharý Aug 6 '17 at 20:19
  • \$\begingroup\$ @Zacharý, let me check! \$\endgroup\$ – Stan Strum Aug 6 '17 at 21:01
  • \$\begingroup\$ The parens aren't needed around x. \$\endgroup\$ – Zacharý Aug 14 '17 at 11:11

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.