26
\$\begingroup\$

This challenge already describes dropsort. However, I'm kinda lazy and I really only need my array to be a bit more sorted than before, it doesn't need to be sorted all the way.

In Drop Sort, we drop every element less than any element before it. In Lazy Drop Sort, we drop every element less than the one strictly preceding it.

Here's an example. Consider the following array:

8 6 9 9 7 2 3 8 1 3

Let's mark every element less than the one before it.

8 6 9 9 7 2 3 8 1 3
  ^     ^ ^     ^

Notice how neither 3 was marked, nor the last 8. They are all larger than the single element to the left of them.

Completing the algorithm, removing the marked elements, we get:

8 9 9 3 8 3

That basically looks more sorted. Kinda. I'm lazy.

Your task, as you may have already deduced, is to implement this algorithm.

Input is an array of at least 1 positive integer between 1 and 9, so you can take a string of digits as well.

This is , fewest bytes wins!

Additional test cases:

1
1

1 2 3
1 2 3

5 3 1
5

1 2 3 2 1
1 2 3

1 1 1 9 9 9 1 1 1 9 9 9 1 1 1
1 1 1 9 9 9 1 1 9 9 9 1 1

9 9
9 9

5 2 4 2 3
5 4 3
|improve this question
\$\endgroup\$
  • \$\begingroup\$ Can it be a function or it must be a complete program? \$\endgroup\$ – rafa11111 Mar 23 '18 at 0:40
  • \$\begingroup\$ @rafa11111 Either is fine \$\endgroup\$ – Pavel Mar 23 '18 at 0:44
  • \$\begingroup\$ In the case it is a function, can the input array be hardcoded in the main program? And can the length of the array be passed as input to the function? \$\endgroup\$ – rafa11111 Mar 23 '18 at 1:56
  • \$\begingroup\$ @rafa11111 The input can't be hardcoded in the function itself. It doens't matter how the function gets this input in your test program. You can take an array length only if you're using C/C++ or another language where that's the only way to determine an array's length. \$\endgroup\$ – Pavel Mar 23 '18 at 2:08

36 Answers 36

1 2
6
\$\begingroup\$

Husk, 4 bytes

m←ġ<

Try it online!

Explanation

m←ġ<
  ġ<    Group the numbers into decreasing sequences
m←      Keep the first element of each sequence
|improve this answer
\$\endgroup\$
15
\$\begingroup\$

JavaScript (ES6), 28 25 bytes

Saved 3 bytes thanks to @Shaggy

a=>a.filter(n=>~-a<(a=n))

Try it online!

|improve this answer
\$\endgroup\$
  • 2
    \$\begingroup\$ n=>p<=n would have looked awesome ;-) \$\endgroup\$ – ETHproductions Mar 22 '18 at 15:49
  • 4
    \$\begingroup\$ @ETHproductions For +4 bytes, (n=p)=>p<=(p=n) works fine ;) \$\endgroup\$ – Arnauld Mar 22 '18 at 15:52
  • \$\begingroup\$ this answer is blowing my mind, why doesn't this explode when trying to access p for the first time, when it's not defined yet? \$\endgroup\$ – Brian H. Mar 22 '18 at 16:26
  • 1
    \$\begingroup\$ @Shaggy That looks safe. Will update when I'm back in front of a computer. Thanks! \$\endgroup\$ – Arnauld Mar 22 '18 at 17:44
  • 2
    \$\begingroup\$ @Pavel a is initially set to the input array and a-1 would result in NaN (unless it contains a single integer, in which case it is coerced to this integer). \$\endgroup\$ – Arnauld Mar 22 '18 at 19:51
6
\$\begingroup\$

R, 27 bytes

(l=scan())[c(T,diff(l)>=0)]

Try it online!

|improve this answer
\$\endgroup\$
6
\$\begingroup\$

MATL, 9 8 bytes

Saved one byte thanks to Giuseppe.

0yd0<h~)

Try it online!

Explanation:

0                 % Push a zero
 y                % Implicitly grab the input and duplicate it.
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [8 6 9 9 7 2 3 8 1 3]
  d               % The difference between each number of the last element:
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [-2, 3, 0, -2, -5, 1, 5, -7, 2]
   0<             % Which are negative?
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [1 0 0 1 1 0 0 1 0]
     h            % Concatenate. Stack: [8 6 9 9 7 2 3 8 1 3], [0 1 0 0 1 1 0 0 1 0] 
      ~           % Negate. Stack: [8 6 9 9 7 2 3 8 1 3], [1 0 1 1 0 0 1 1 0 1]
       )          % Index. Stack: [8 9 9 3 8 3]
|improve this answer
\$\endgroup\$
5
\$\begingroup\$

Perl 5.10.0 + -nl, 16 bytes

$f>$_||say;$f=$_

Try it online!

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Translation to Perl 6 perl6 -ne '$/>$_||.say;$/=$_' \$\endgroup\$ – Brad Gilbert b2gills Mar 22 '18 at 22:46
  • \$\begingroup\$ @Brad perl6 is a different language (it's not even backwards-compatible) Post it! \$\endgroup\$ – wastl Mar 23 '18 at 5:44
  • \$\begingroup\$ I wrote one that was more idiomatic Perl 6, but it was longer. Also one of the reasons I post here is to show off the language, and to explain it. Posting that translation does nothing but show that it is a slightly more verbose version of Perl. Basically it satisfies none of the reasons why I post on this site. \$\endgroup\$ – Brad Gilbert b2gills Mar 24 '18 at 15:58
5
\$\begingroup\$

Haskell, 29 bytes

f s=[b|(a,b)<-zip(0:s)s,a<=b]

just a simple list comprehension.

|improve this answer
\$\endgroup\$
4
\$\begingroup\$

Japt, 8 7 bytes

Saved 1 byte thanks to @Oliver

k@>(U=X

Test it online!

Alternatives:

f@T§(T=X
k@ä>0 gY
i0 ò> mÅ c
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Came up with the exact same solution :) \$\endgroup\$ – Shaggy Mar 22 '18 at 17:39
4
\$\begingroup\$

Stax, 5 bytes

âÿ╠╦░

Run and debug this online

Unpacking, ungolfing, and commenting the code, we get this.

Z   Push a zero under the input
f   Use the rest of the program as a filter on the input.  Output passing elements.
>   Current element is greater than previous?
_~  Push current element to the input stack; when the main stack is empty, pops fall back to this
!   Logical not; applies to the result of the greater-than

Run this one

The ordering of the instructions is awkward but there's a reason for it. Stax source code packing doesn't always yield the same size output for the same size input. Basically, you have a chance to save a byte if the last character of source has a lower character code. Well, ! has one of the lowest codes you can get for a printable character. (33 specifically) Many 6 byte ASCII stax programs can't pack any smaller. But if they end with a !, then they can. So the reason for this particular ordering of instructions is to ensure that the logical not ends up at the end of the program.

|improve this answer
\$\endgroup\$
4
\$\begingroup\$

J, 12 Bytes

#~1,2&(<:/\)

Explanation:

#~1,2&(<:/\)    | Whole function, executed as a hook
       <:/      | Distribute <: (greater or equal) over an array
    2&(   \)    | Apply to each sub array of length 2
  1,            | Append a 1 to the front
#~              | Choose elements from the original array

Examples:

    2&(<:/\) 8 6 9 9 7 2 3 8 1 3
0 1 1 0 0 1 1 0 1
    1,2&(<:/\) 8 6 9 9 7 2 3 8 1 3
1 0 1 1 0 0 1 1 0 1
    (1 0 1 1 0 0 1 1 0 1) # 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3
    f =: #~1,2&(<:/\)
    f 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Try it online!

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Nice solution! I added a TIO link for your code. \$\endgroup\$ – Galen Ivanov Mar 22 '18 at 18:10
4
\$\begingroup\$

Jelly, 6 bytes

>Ɲ0;¬×

I/O is on strings.

Try it online!

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I'm curious, why operate on strings and not arrays? I was told Jelly is bad at strings. \$\endgroup\$ – Pavel Mar 22 '18 at 19:01
  • 2
    \$\begingroup\$ It is. × shouldn't work for character repetition, but it does. \$\endgroup\$ – Dennis Mar 22 '18 at 19:07
4
\$\begingroup\$

Java 8, 66 55 48 bytes

l->{for(int i=0;;)if(i>(i=l.next()))l.remove();}

-11 bytes after a tip from @OlivierGrégoire.
-7 more bytes thanks to @OlivierGrégoire.

Explanation:

Try it online.

l->{                     // Method with Integer-ListIterator parameter and no return-type
  for(int i=0;;)         //  Loop over all items
    if(i>(i=l.next()))   //   If the current item is larger than the next
      l.remove();}       //    Remove this next item
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Why does everyone start using ~0 when it's basically -1. Personally I would choose the more intuitive solution if the byte-count is the same length (except for while(...) vs for(;...;), in which case I prefer the for. Thanks for another -7 bytes, though. :) \$\endgroup\$ – Kevin Cruijssen Mar 22 '18 at 18:21
  • \$\begingroup\$ It's because I'm bad with 2-complement... I'm so bad I wanted to mean Integer.MIN_VALUE (which is then 1<<31, I guess...) ;-) \$\endgroup\$ – Olivier Grégoire Mar 22 '18 at 18:32
4
\$\begingroup\$

Octave, 21 bytes

@(x)x(~[0,diff(x)<0])

Try it online!

Explanation:

Take a vector x as input, and create a vector [0, diff(x)<0], where diff(x) is a vector with the difference between all adjacent elements. Keep only those that are negative by comparing it to zero, giving us a list of all the elements we want to drop.

We then select the elements from the input vector that we want to keep.

|improve this answer
\$\endgroup\$
4
\$\begingroup\$

V, 25 bytes

òjälá k$yl+@"òç-/d
ç /dw

Try it online!

Hexdump:

00000000: f26a e46c e120 6b24 796c 2b40 2218 f2e7  .j.l. k$yl+@"...
00000010: 2d2f 640a e720 2f64 77                   -/d.. /dw

Worst language for the job. But I did it for a dare.

|improve this answer
\$\endgroup\$
  • 6
    \$\begingroup\$ Side note: ojalá is Spanish for hopefully. \$\endgroup\$ – Dennis Mar 22 '18 at 21:45
  • 2
    \$\begingroup\$ @dennis That's cool. What is k$yl+@"òç-/d Spanish for? \$\endgroup\$ – DJMcMayhem♦ Mar 22 '18 at 21:57
  • 7
    \$\begingroup\$ k$yl+@"òç-/d might be liberally translated as Ouch, who the hell left that cupboard door open? \$\endgroup\$ – Luis Mendo Mar 22 '18 at 22:32
3
\$\begingroup\$

Triangularity, 71 bytes

.....).....
....IEL....
...)rFD)...
..2+)IE)w..
.+h)2_stDO.
={M)IEm}...

Try it online!

How it works?

)IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} – Full program.
)IE                               – Get the 0th input I and evaluate it.
   L)r                            – And push the range [0 ... length of I).
      F                   {       – Filter the integers in this range which satisfy:
       D)2+)IE)w+h)2_stDO=        – This condition. Runs each element E on a separate
                                    stack and discard those that don't meet the criteria.
       D)2+                       – Duplicate and add 2 to the second copy.
           )IE                    – Retrieve I again.
              )                   – Push a 0 onto the stack.
               w                  – Wrap the 0 in a list. [0]
                +                 – Prepend it to I.
                 h                – Head. Trim the elements after index E+2.
                  )2_             – Literal -2.
                     st           – Tail.
                       DO=        – Check whether the result is invariant over sorting.
                           M)IEm} – Last part: indexing into the input.
                           M    } – For each index that satisfies the conditions:
                            )IEm  – Retrieve the element of I at that position.
|improve this answer
\$\endgroup\$
  • 2
    \$\begingroup\$ Out of curiosity (since you are the creator of Triangularity): why not do something similar as Hexagony / Cubically, where a piece of code is automatically filled with the no-op dots? So this program would be )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} which would expand to your current answer? \$\endgroup\$ – Kevin Cruijssen Mar 22 '18 at 16:20
  • \$\begingroup\$ @KevinCruijssen Because I was actually planning to make Triangularity a 2D esolang, but I gave up on the idea so I just sticked to my previous template. I think I'll make some major changes soon, when I release Triangularity v2. (Also it's kinda fun to golf in it in its current form, because a simple 1-byte save inline might instead save you 20 :D... It also applies retroactively when fixing stuff though :C) \$\endgroup\$ – Mr. Xcoder Mar 22 '18 at 16:25
  • \$\begingroup\$ Well, even if you do plan on releasing it as a 2D esolang, my comment still stands (somewhat). )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} would be your code, it would expand to your current template, and then do the 2D commands on that expanded template. EDIT: .....).....\n....IEL....\n...)rFD)...\n..2+)IE)w..\n.+h)2_stDO.\n={M)IEm}... and .....).........IEL.......)rFD).....2+)IE)w...+h)2_stDO.={M)IEm}... and )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} would all three be the exact same program. \$\endgroup\$ – Kevin Cruijssen Mar 22 '18 at 16:28
3
\$\begingroup\$

Python, 40 bytes

f=lambda h,*t:t and h+f(*t)[h>t[0]:]or h

Try it online!

Input as tuple of characters.

Python 3, 41 bytes

p=''
for x in input():x<p or print(x);p=x

Try it online!

String input.

Python 2, 41 bytes

for x in input():
 if x>=id:print x
 id=x

Try it online!

String input, just because strings are greater than id but numbers are smaller.

|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Pick[#,Arg[#-{0}~Join~Most@#],0]&

Try it online!

How it works

The code # - {0}~Join~Most@# turns an array {a,b,c,d,e,f} into {a,b-a,c-b,d-c,e-d,f-e}. Applying Arg to this sets negative numbers to Pi and nonnegative numbers to 0.

Pick[#, ..., 0]& picks out the entries of # where ... has a 0: in our case, exactly the elements that yield a nonnegative number when you subtract the previous element. In other words, these are exactly the entries we want to keep when lazydropsorting.

|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wonder, 27 bytes

-> ':1.!> 'sS#<=.cns2.++[0]

Usage example:

(-> ':1.!> 'sS#<=.cns2.++[0])[8 6 9 9 7 2 3 8 1 3]

Explanation

Ungolfed version:

(map get 1).(fltr sS <=).(cns 2).(++ [0])

Prepend 0, get list of consecutive pairs, keep list items where first number <= second number, get second number of each pair.

|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 20 bytes

#&@@@Split[#,##>0&]&
(* or *)
Max/@Split[#,##>0&]&

Try it online!

Explanation

Input = {8, 6, 9, 9, 7, 2, 3, 8, 1, 3}

Split[#,##>0&]

Group consecutive elements that are strictly decresasing: {{8, 6}, {9}, {9, 7, 2}, {3}, {8, 1}, {3}}

#&@@@

Take the first element of each: {8, 9, 9, 3, 8, 3}

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ ##>0 is fancy and everything, but it doesn't really save anything over #>#2 here ;) (which would make your program work with arbitrary integers, not that that's required though). \$\endgroup\$ – Martin Ender Mar 25 '18 at 21:49
3
\$\begingroup\$

Python 2, 52 46 45 42 bytes

lambda a:[v for v,w in zip(a,[1]+a)if v/w]

Try it online!

Saved:

  • -3 bytes, thanks to Rod
|improve this answer
\$\endgroup\$
3
\$\begingroup\$

SWI-Prolog, 44 bytes

[A,B|C]-[A|E]:-B<A,[B|C]-[B|E];[B|C]-E. L-L.

Usage: Call "List-X" where List is a bracket-enclosed, comma-separated list e.g. [1,4,5,1,11,6,7].

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to the site! :) \$\endgroup\$ – DJMcMayhem♦ Mar 28 '18 at 12:56
2
\$\begingroup\$

APL+WIN, 14 bytes

Prompts for screen input of a vector of integers.

(1,1>2-/v)/v←⎕
|improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

ĆÁü›_Ï

Try it online!

Explanation

Ć        # append the head of the list
 Á       # rotate right
  ü›     # apply pair-wise greater-than
    _    # logical negate each
     Ï   # keep elements of input that are true in this list
|improve this answer
\$\endgroup\$
2
\$\begingroup\$

Kotlin, 39 bytes

a->a.filterIndexed{i,v->i<1||v>=a[i-1]}

Try it online!

Filter items that are either the first item (index==0, or even shorter index<1) OR the current Value is greater than or equal to the previous item (a[i-1]).

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 11 bytes

{⍵⌿⍨1⍪2≤⌿⍵}

Try it online!

This is actually pretty similar to Graham's answer, but in Dyalog, and independently developed. Also, more symmetric.

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

K4, 10 bytes

Solution:

x_/|&<':x:

Example:

q)k)x_/|&<':x:8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Explanation:

Find indices where element is less than preceding, remove these indices from the input

x_/|&<':x: / the solution
        x: / store input as x
     <':   / less-than each-previous
    &      / indices where true
   |       / reverse
 _/        / drop-over
x          / the input
|improve this answer
\$\endgroup\$
2
\$\begingroup\$

Attache, 24 bytes

{Mask[1'(Delta!_>=0),_]}

Try it online!

Explanation

Mask selects all elements from its second argument which correspond to truthy elements in its first argument. 1'(Delta!_>=0) calculates the indices which correspond to elements that are supposed to be in the final array.

Other attempts

28 bytes (pointfree): ~Mask#(1&`'##Delta#`>=#C[0])

32 bytes: {Mask[1'(&`<= =>Slices[_,2]),_]}

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

C# (.NET Core), 33 + 18 = 51bytes

x=>x.Where((a,n)=>n<1||x[n-1]<=a)

Try it online!

basically the statement is where x is the first int in the array, or is greater than or equal to the previous number, keep it. Else drop it.

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ You can return an IEnumerable. No ToArray() needed. \$\endgroup\$ – Pavel Mar 22 '18 at 17:21
  • \$\begingroup\$ @Pavel I would need to add an extra reference System.Collections, and that would negate all the bytes saved for removing the ToArray(). \$\endgroup\$ – Dennis.Verweij Mar 22 '18 at 22:12
  • \$\begingroup\$ No, since you won't be referencing IEnumerable in the answer, just using it as the return type. \$\endgroup\$ – Pavel Mar 22 '18 at 22:27
  • \$\begingroup\$ @Pavel okay thanks, sometimes I'm a bit unsure when to count the bytes or not... sorry \$\endgroup\$ – Dennis.Verweij Mar 23 '18 at 7:39
1
\$\begingroup\$

Swift 4, 56 55 bytes

{var l=0;print($0.filter{($0>=l,l=$0).0})}as([Int])->()

Try it online!

Explanation

{var l=0;           // Declare variable l
print($0.filter{(   // Print every element e in the input
  $0>=l,            //   where e >= l
  l=$0).0})         //   And set l to e
}as([Int])->()      // Set the input type to integer array
|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 bytes

0;>ƝżµḢÐṂ

Try it online!

This feels pretty bulky, wouldn't be that surprised if there is a better way.

0;>ƝżµḢÐṂ
   Ɲ       For each adjacent pair in the input...
  >        ...is the first element greater than the second? (yields a list of 0/1)
0;         prepend a zero to this list (always keep the first element)
    ż      zip with the input
     µ     new monadic link
       ÐṂ  keep elements of the list with minimal value of... (Ðḟ would have worked here and been slightly more clear but I'll leave it as it is)
      Ḣ    ...their first element
|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Brain-Flak, 136, 120 bytes

((())){{}([{}]({}))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}(({})<>)(())(<>)}{}([][()])}{}{}<>{{}({}<>)<>}<>

Here it is formatted and "readable".

((()))
{
    {}

    ([{}]({}))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    {
        {}(({})<>)(())(<>)
    }

    {}

    ([][()])

}{}{}<>

{
    {}
    ({}<>)<>
}<>

Try it online!

|improve this answer
\$\endgroup\$
1 2

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.