44
\$\begingroup\$

I'm supposed to sort a list of numbers, but I'm super lazy. It's really hard to figure how to swap all the numbers around until all of them are in increasing order, so I came up with my own algorithm that will guarantee that the new list is sorted¹. Here's how it works:

For a list of size N, we'll need N-1 iterations. On each iteration,

  • Check if the N'th number is smaller than the N+1'th number. If it is, then these two numbers are already sorted, and we can skip this iteration.

  • If they are not, then you need to continually decrement the first N numbers until these two numbers are in order.

Let's take a concrete example. Let's say the input was

10 5 7 6 1

On the first iteration, we'll compare 10 and 5. 10 is larger than 5, so we decrement it until it's smaller:

4 5 7 6 1

Now we compare 5 and 7. 5 is smaller than 7, so we don't need to do anything on this iteration. So we go to the next and compare 7 and 6. 7 is larger than 6, so we decrement the first three numbers until it's smaller than 6, and we get this:

2 3 5 6 1

Now we compare 6 and 1. Again, 6 is larger than 1, so we decrement the first four numbers until it's smaller than 1, and we get this:

-4 -3 -1 0 1

And we're done! Now our list is in perfect sorted order. And, to make things even better, we only had to iterate through the list N-1 times, so this algorithm sorts lists in O(N-1) time, which I'm pretty sure is the fastest algorithm there is.²

Your challenge for today is to implement this Lazy Sort. Your program or function will be given an array of integers in whatever standard format you like, and you must perform this lazy sort and return the new "sorted" list. The array will never be empty or contain non-integers.

Here are some examples:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

As always, this is , so write the shortest program you can!


¹ This doesn't mean what it sounds like it means, but it is technically true

² I am completely kidding, please don't hate me

\$\endgroup\$
  • 6
    \$\begingroup\$ I think you are not lazy if you do it in this way \$\endgroup\$ – Jörg Hülsermann Jun 15 '17 at 19:55
  • 4
    \$\begingroup\$ @JörgHülsermann well some integers are too heavy...not exactly in the mood to carry such a weight, better to take off just the top stuff out \$\endgroup\$ – Erik the Outgolfer Jun 15 '17 at 20:25
  • 21
    \$\begingroup\$ <sarcasm>This sorting algorithm actually still clocks in at O(N^2) time complexity because you have to go through all previously-accessed items on the list to decrement them. I recommend going through the list backwards instead and decrement only one number per step as necessary. This will give you true O(N) complexity!</sarcasm> \$\endgroup\$ – Value Ink Jun 15 '17 at 22:04
  • 1
    \$\begingroup\$ @ValueInk O(n^2) in terms of memory accesses, but isn't it O(n) for comparisons? \$\endgroup\$ – Cole Johnson Jun 16 '17 at 2:31
  • 7
    \$\begingroup\$ @ColeJohnson technically yes, but time complexity needs to take all the steps of the algorithm into consideration. You still have to iterate through all previous indices on every iteration, so it still comes out O(N^2). \$\endgroup\$ – Value Ink Jun 16 '17 at 2:38

16 Answers 16

12
\$\begingroup\$

Jelly,  14 12 11  9 bytes

-2 bytes thanks to ETHproductions (use the minimum dyad, «)

I’«0Ṛ+\Ṛ+

A monadic link taking and returning lists of integers.

Try it online! or see the test suite.

I really don't think this is Lazy™ enough!

How?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]
\$\endgroup\$
12
\$\begingroup\$

Haskell, 40 bytes

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Try it online!

\$\endgroup\$
  • 11
    \$\begingroup\$ A lazy language seems appropriate for this challenge \$\endgroup\$ – tomsmeding Jun 16 '17 at 5:26
8
\$\begingroup\$

JavaScript (ES6), 61 bytes

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Test cases

let f =

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

console.log(JSON.stringify(f([10, 5, 7, 6, 1]))) // -4 -3 -1 0 1
console.log(JSON.stringify(f([3, 2, 1]))) // -1 0 1
console.log(JSON.stringify(f([1, 2, 3]))) // 1 2 3
console.log(JSON.stringify(f([19]))) // 19
console.log(JSON.stringify(f([1, 1, 1, 1, 1, 1, 1, 1, 1]))) // -7 -6 -5 -4 -3 -2 -1 0 1
console.log(JSON.stringify(f([5, 7, 11, 6, 16, 2, 9, 16, 6, 16]))) // 27 -25 -21 -20 -10 -9 -2 5 6 16
console.log(JSON.stringify(f([-8, 17, 9, 7]))) // -20 5 6 7

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

Jelly, 12 bytes

I»1U
0ị;Ç_\U

Try it online!

How it works

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

The basic idea at play is this: If you reverse the input and output arrays, the output is simply the input with each delta of 0 or greater replaced with -1. For example:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse
\$\endgroup\$
5
\$\begingroup\$

k, 20 bytes

{x-|+\0,1_0|1+-':|x}

Try it online.

Explanation:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x
\$\endgroup\$
4
\$\begingroup\$

Haskell, 56 bytes

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Try it online!

Keep the first part of the list in parameter a. At each step add the next element x to the end of a and increase all elements of a by the minimum of (y-x-1) and 0.

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

Python, 54 bytes

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Try it online!

Takes input splatted like f(1,2,3). Outputs a list. Uses exponential time.

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

C#, 76 bytes

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

This modifies the list in place. It goes through the list backwards and keep a running total of the delta to apply to each number.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 59 bytes

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]
\$\endgroup\$
  • \$\begingroup\$ Wow. I was about to write a JS solution, but then I saw this. I didn't think to use the spread operator like that in the parameters \$\endgroup\$ – andrewarchi Jun 15 '17 at 22:59
  • \$\begingroup\$ You can leave off f= for JS answers to save two bytes \$\endgroup\$ – andrewarchi Jun 15 '17 at 23:56
  • \$\begingroup\$ @andrewarchi Thanks, but this particular function needs to call itself (f(a)) so it still requires the name. \$\endgroup\$ – ETHproductions Jun 16 '17 at 1:53
  • \$\begingroup\$ I forgot it was recursive \$\endgroup\$ – andrewarchi Jun 16 '17 at 4:44
2
\$\begingroup\$

Brain-Flak, 153 bytes

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

Try it online!

This includes +1 for the -r flag.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>
\$\endgroup\$
2
\$\begingroup\$

R, 56 bytes

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

\$\endgroup\$
  • 1
    \$\begingroup\$ nice use of diff, I was trying to figure out how to get that to work...By the way, you can get rid of the braces around the function body for -2 bytes, but better yet, you can use s=scan() instead of a function definition to save a few more bytes. It'd be great if you'd include a link to Try it online so that other people can verify that this code works for all test cases. \$\endgroup\$ – Giuseppe Jun 16 '17 at 21:03
  • \$\begingroup\$ No worries! we all start somewhere :) \$\endgroup\$ – Giuseppe Jun 16 '17 at 21:09
1
\$\begingroup\$

JavaScript (ES6), 68 bytes

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Input and output is an array of integers.

Test Snippet

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o
<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

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

JavaScript (ES6), 50 bytes

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Explanation:

This is a recursive solution, which first clones the array, then decreases all values up until an element is greater or equal to the next element in the array.

The function calls itself as long as any elements are out of order. When the elements are finally sorted, the clone is returned. (We can't return the array itself, because the some() method would have decremented all its elements, making them all off by -1.)

Test cases:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

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

SWI-Prolog, 194 bytes

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Might be able to try it online here: http://swish.swi-prolog.org/p/LazySort.pl

You ask l(L, [10,5,7,6,1]). which says "solve for L, where L is the lazy sorted version of this list".

The two functions are:

  • lazysorted(A,B) - states that A is the lazysorted version of B, if they're both empty lists, or if A can be obtained by reversing B, calling a helper function to walk the list and do a subtraction with an accumulator pushing each value lower than the previous one, and reversing the result of that back to the right way around.
  • f helper matches two lists, the value of the previous number in the list, and a rolling difference accumulator, and solves for the new value of the current list position being the original value minus the difference accumulator, optionally minus a new value required to force this value below the previous number in the list, and f must solve for the tail of the list recursively with the now increased difference accumulator.

Screenshot of the test cases on Swish:

image showing the test cases running on Swish

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

JavaScript (ES6), 61 bytes

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

Not the shortest solution but I couldn't pass over the opportunity to use reduceRight.

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

C# (.NET Core), 89 88 86 79 bytes

  • Saved just 1 byte with a slightly different approach.
  • Saved another 2 bytes with a simplification of the fors.
  • Saved 7 bytes thanks to the amazing golfing skills of VisualMelon.
a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Try it online!

First for iterates through the array, then it calculates the decrement and finally the second for decrements the elements if necessary until the ith position.

Is it valid to just modify the original array instead of returning a new one (still getting used to the rules)?

\$\endgroup\$
  • \$\begingroup\$ Yes, Modifying the original array is perfectly fine. :) \$\endgroup\$ – DJMcMayhem Jun 15 '17 at 20:50
  • 4
    \$\begingroup\$ @DJMcMayhem thanks, I felt too lazy to create a new one. :) \$\endgroup\$ – Charlie Jun 15 '17 at 20:53

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.