Powinienem posortować listę liczb, ale jestem bardzo leniwy. Naprawdę trudno jest wymyślić, jak zamieniać wszystkie liczby, dopóki wszystkie nie będą rosły w porządku, więc wymyśliłem własny algorytm, który zagwarantuje, że nowa lista zostanie posortowana¹. Oto jak to działa:

Aby uzyskać listę rozmiarów N , potrzebujemy iteracji N-1 . Przy każdej iteracji

• Sprawdź, czy N-ty numer jest mniejszy niż N + 1-ty numer. Jeśli tak, to te dwie liczby są już posortowane i możemy pominąć tę iterację.

• Jeśli nie są, musisz ciągle zmniejszać pierwsze N liczb, aż te dwie liczby będą w porządku.

Weźmy konkretny przykład. Powiedzmy, że dane wejściowe były

10 5 7 6 1

Przy pierwszej iteracji porównamy 10 i 5. 10 jest większe niż 5, więc zmniejszamy go, aż będzie mniejszy:

4 5 7 6 1

Teraz porównujemy 5 i 7. 5 jest mniejsze niż 7, więc nie musimy nic robić w tej iteracji. Przechodzimy więc do następnego i porównujemy 7 i 6. 7 jest większe niż 6, więc zmniejszamy pierwsze trzy liczby, aż będą mniejsze niż 6, i otrzymujemy:

2 3 5 6 1

Teraz porównujemy 6 i 1. Ponownie, 6 jest większe niż 1, więc zmniejszamy pierwsze cztery liczby, aż będą mniejsze niż 1, i otrzymujemy:

-4 -3 -1 0 1

I skończone! Teraz nasza lista jest w idealnym porządku posortowanym. A żeby było jeszcze lepiej, musieliśmy tylko iterować listę N-1 razy, więc ten algorytm sortuje listy w czasie O (N-1) , co, jestem pewien, jest najszybszym dostępnym algorytmem.

Twoim dzisiejszym wyzwaniem jest wdrożenie tego Lazy Sort. Twój program lub funkcja otrzyma tablicę liczb całkowitych w dowolnym standardowym formacie, który ci się podoba, i musisz wykonać to leniwe sortowanie i zwrócić nową listę „posortowaną” . Tablica nigdy nie będzie pusta ani nie będzie zawierać liczb całkowitych.

Oto kilka przykładów:

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

Jak zawsze jest to golf kodowy , więc napisz najkrótszy program, jaki możesz!

¹ To nie znaczy, jak to brzmi, ale jest technicznie prawdą

² Żartuję całkowicie, proszę, nie nienawidź mnie

Galaretka ,  14 12 11  9 bajtów

-2 bajty dzięki produktom ETH (użyj minimalnej dyady «)

I’«0Ṛ+\Ṛ+

Monadyczny link pobierający i zwracający listy liczb całkowitych.

Wypróbuj online! lub zobacz pakiet testowy .

Naprawdę nie sądzę, że to wystarczy Lazy ™!

W jaki sposób?

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]

Haskell , 40 bajtów

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

Wypróbuj online!

JavaScript (ES6), 61 bajtów

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

Przypadki testowe

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

Galaretka , 12 bajtów

I»1U
0ị;Ç_\U

Wypróbuj online!

Jak to działa

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.

Podstawowa idea w grze jest następująca: jeśli odwrócisz tablice wejściowe i wyjściowe, dane wyjściowe to po prostu dane wejściowe z każdą deltą 0 lub większą zastąpioną przez -1. Na przykład:

[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

k, 20 bajtów

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

Wypróbuj online.

Wyjaśnienie:

{                  } /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

Haskell, 56 bajtów

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

Wypróbuj online!

Zachowaj pierwszą część listy w parametrze a. Na każdym kroku dodaj następny element xna końcu ai zwiększ wszystkie elementy o minimum o (y-x-1)i 0.

Python , 54 bajty

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

Wypróbuj online!

Pobiera dane wejściowe jak f(1,2,3). Wyświetla listę. Wykorzystuje czas wykładniczy.

C #, 76 bajtów

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;}

To modyfikuje listę na miejscu. Przewija listę do tyłu i zachowuje bieżącą sumę delty, aby zastosować ją do każdej liczby.

JavaScript (ES6), 59 bajtów

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]

Brain-Flak , 153 bajty

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

Wypróbuj online!

Dotyczy to +1również -rflagi.

#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
{}
([]){{}({}<>)<>([])}<>

R, 56 bajtów

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

JavaScript (ES6), 68 bajtów

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

Wejście i wyjście to tablica liczb całkowitych.

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>

JavaScript (ES6), 50 bajtów

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

Wyjaśnienie:

Jest to rozwiązanie rekurencyjne, które najpierw klonuje tablicę, a następnie zmniejsza wszystkie wartości, aż element będzie większy lub równy następnemu elementowi w tablicy.

Funkcja wywołuje się, dopóki dowolne elementy nie działają. Kiedy elementy zostaną ostatecznie posortowane, klon jest zwracany. (Nie możemy zwrócić samej tablicy, ponieważ some()metoda obniżyłaby wszystkie jej elementy, powodując ich wyłączenie o -1).

Przypadki testowe:

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])+'');

SWI-Prolog, 194 bajty

:-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]).

Może być w stanie spróbować online tutaj: http://swish.swi-prolog.org/p/LazySort.pl

Pytasz, l(L, [10,5,7,6,1]).co mówi „rozwiąż dla L, gdzie L jest leniwą posortowaną wersją tej listy”.

Dwie funkcje to:

• lazysorted (A, B) - stwierdza, że ​​A jest leniwą wersją B, jeśli oba są pustymi listami, lub jeśli A można uzyskać poprzez odwrócenie B, wywołanie funkcji pomocnika, aby przejść listę i wykonać odejmowanie za pomocą akumulatora popychając każdą wartość niższą niż poprzednia i odwracając jej wynik z powrotem na właściwy sposób.
• fpomocnik dopasowuje dwie listy, wartość poprzedniego numeru na liście i akumulator różnicy ruchomej, i rozwiązuje dla nowej wartości bieżącej pozycji listy wartość oryginalną minus akumulator różnicowy, opcjonalnie minus nową wartość wymaganą do wymuszenia tego wartość poniżej poprzedniego numeru na liście i fmusi rozwiązać rekurencyjnie dla końca listy z akumulatorem o teraz zwiększonej różnicy.

Zrzut ekranu przypadków testowych na Swish:

JavaScript (ES6), 61 bajtów

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

Nie jest to najkrótsze rozwiązanie, ale nie mogłem pominąć okazji do użycia reduceRight.

C # (.NET Core) , 89 88 86 79 bajtów

• Zapisano zaledwie 1 bajt z nieco innym podejściem.
• Zapisano kolejne 2 bajty z uproszczeniem fors.
• Oszczędność 7 bajtów dzięki niesamowitym umiejętnościom golfowym 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;}

Wypróbuj online!

Najpierw foriteruje przez tablicę, następnie oblicza zmniejszenie, a na koniec drugie forzmniejsza elementy, jeśli to konieczne, aż do ipozycji th.

Czy wystarczy zmodyfikować oryginalną tablicę zamiast zwracać nową (wciąż przyzwyczajając się do reguł)?