Upuść to tak, jakby było gorące


41

Jak opisano w tym pytaniu :

Dropsort, zaprojektowany przez Davida Morgana-Mar, jest przykładem „algorytmu sortowania” w czasie liniowym, który tworzy listę, która jest faktycznie posortowana, ale zawiera tylko niektóre oryginalne elementy. Każdy element, który nie jest co najmniej tak duży, jak maksymalna liczba elementów poprzedzających, jest po prostu usuwany z listy i odrzucany.

Aby użyć jednego ze swoich przypadków testowych, wejście z {1, 2, 5, 4, 3, 7}wydajnością {1, 2, 5, 7}, jak 4i 3oba spadły za to, że mniejsze niż poprzednio „posortowane” wartości 5.

Nie chcemy algorytmów „sortujących”, chcemy, żeby były prawdziwą okazją. Dlatego chcę, abyś napisał program, który, biorąc pod uwagę listę liczb, wyświetla listę list DropSorted (aby być kompletnym algorytmem sortowania, musielibyśmy scalić te listy, ale wcześniej scalono dwie listy posortowane i prośba o zrobienie tego ponownie to prawie dwa pytania, więc to pytanie jest konkretnie krokiem „podziału” naszego kompletnego DropSortu).

Rozmieszczenie i zawartość naszych list jest jednak kluczowa. Dane wyjściowe programu muszą odpowiadać wynikom DropSort, a następnie DropSort odrzuconych wartości i tak dalej, dopóki nie będzie tylko listy posortowanych łańcuchów. Ponownie, pożyczając istniejący zestaw testów (i dodając dwa kolejne):

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

Możesz założyć, że dane wejściowe nie są puste.

To jest , więc obowiązują standardowe zasady!


Czy możemy produkować jak [5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]?
Pan Xcoder,

5
@ Xcoder, cóż, nie mam nic przeciwko składni, ale nadal musisz posortować drugą listę (i podzielić ją w tym przypadku). Wiedza, kiedy przestać, jest częścią wyzwania;). I Stewie, tak naprawdę nie wiem co ci powiedzieć. Widziałem wyzwanie DropSort i pomyślałem, że to zabrzmi zabawnie. Czy jest jakaś szansa, że ​​wykorzystałeś swój wehikuł czasu, by skoczyć do przodu i zobaczyć to pytanie? Po prostu nie używaj go, aby zobaczyć najlepszą odpowiedź!
Lord Farquaad

Zauważ, że dodanie sortowania resztek usuwa rozwiązania z czasu liniowego.
ikegami,

Czy powinno to {3,4,5,3,4,5,3,4,5}skutkować {{3,4,5,5,5},{3,4,4},{3}}?
QBrute

@QBrute Myślę, że to prawda.
Lord Farquaad

Odpowiedzi:


10

MATL , 15 10 9 bajtów

5 bajtów mniej przy użyciu pomysłu @beaker na łączne maksimum

t"ttY>=&)

Dane wejściowe to numeryczny wektor wiersza w formacie [1, 2, 5, 4, 3, 7](przecinki są opcjonalne). Dane wyjściowe zawierają listy oddzielone znakiem nowej linii, a liczby na każdej liście są oddzielone spacjami.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Biorąc pod uwagę tablicę, kod wybiera z niej każdy wpis, który jest równy skumulowanemu maksimum do tego wpisu.

Na przykład dane

1 2 5 4 3 7

kod wybiera pierwszy, drugi, trzeci i szósty wpis:

1 2 5     7

Następnie proces powtarza się na podtablicy utworzonej przez pozostałe wpisy (w oryginalnej kolejności):

      4 3

Należy to zrobić, dopóki podtablica pozostałych wpisów nie będzie pusta. Górną granicą wymaganej liczby iteracji jest rozmiar wejściowy. Ostatnie iteracje mogą nie być potrzebne. W takim przypadku działają one na pustej tablicy, wytwarzając dodatkowe puste tablice.

Na końcu stos zawiera wymagane tablice i prawdopodobnie kilka pustych tablic, które w ogóle nie są wyświetlane.

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

23

Haskell, 67 59 58 bajtów

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

Objaśnienie: Biorąc pod uwagę listę list (które są już posortowane) i wartość x, !operator umieści xna końcu pierwszej listy, której ostatni element jest mniejszy lub równy x. Jeśli taka lista nie istnieje, lista [x]jest umieszczana na końcu.

Wypróbuj online.


3
To niezwykle sprytne rozwiązanie. Szczerze mówiąc, spodziewałem się, że większość ludzi będzie po prostu DropSort w kółko, dopóki nic nie pozostanie, ale miałem nadzieję, że ktoś wymyśli bardziej kreatywny sposób.
Lord Farquaad

13

Łuska , 10 bajtów

hUmü<¡Ṡ-ü<

Wypróbuj online!

Jest to kombinacja mojej drugiej odpowiedzi Husk i odpowiedzi Xnora Haskella . Duplikat ü<wydaje się niezręczny, ale nie wiem, jak się go pozbyć ...

Wyjaśnienie

Funkcja ü<tłumaczy się nubBy(>)w języku Haskell. Przechodzi przez listę od lewej do prawej, zachowując te elementy, dla których żaden wcześniej przechowywany element nie jest ściśle większy. Innymi słowy, wykonuje droport. Pozostałe elementy uzyskuje się, biorąc różnicę listy oryginalnej listy i wynik ü<.

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]]

10
Najlepsza odpowiedź Outgolfa o 33% „Nie wiem, czuję się niezdarnie”
Lord Farquaad

11

Haskell , 50 bajtów

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

Wypróbuj online!


1
Prawie to miałem, po prostu nie znałem \\ funkcji: (
H.PWiz

2
Och, to rzeczywiście bardzo przydatna funkcja! Bardzo fajne rozwiązanie =)
wada

7

Łuska , 16 bajtów

hUm₁≤¡₁>
ṠfSz⁰G▲

Wypróbuj online!

Wyjaśnienie

Ten pierwszy wiersz jest funkcją główną, a drugi to funkcja pomocnicza wyższego rzędu (przyjmuje funkcję jako argument i zwraca nową funkcję). Jest dostępny przez indeks dolny . Chodzi o to, że ₁≤wykonuje droport i ₁>daje resztki elementów.

Ṡ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].

W głównej funkcji ₁>iterujemy funkcję resztek i stosujemy funkcję droport ₁≤do wyników.

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]]

Łuska jest nową galaretką ...
Erik the Outgolfer

1
@EriktheOutgolfer Beaten by MATL. : /
Zgarb

6

Python 3 , 131 112 103 95 bajtów

Wielkie dzięki @Mr. Xcoder dla oszałamiającej 19 bajtów !!

Wielkie dzięki @ovs za niesamowite 17 bajtów!

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))

Wypróbuj online!

Wyjaśnienie:

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

2
116 bajtów. if-elseMożna opadł [m,d][i<m[-1]]+=[i].
Pan Xcoder,

Woah, wielkie dzięki ... Próbowałem tego [m,d], ale jakoś to nie działało ....
officialaimm

1
113 bajtów . (len(d)>0)jest bool(d), ponieważ puste listy są w Pythonie fałszywe. +1, fajne rozwiązanie!
Pan Xcoder,


2
i,jest po prostu skrótem (i,), który zawiera krotkę a. a,*x = x or [0]to rozszerzone rozpakowywanie python3 . Oto pomocny post SO na ten temat z kilkoma przykładami.
ovs

6

Haskell , 113 107 102 92 bajtów

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=[]

Wypróbuj online!

To jest naprawdę długie.

Wyjaśnienie

!wykonuje sortowanie upuszczone na liście, a jednocześnie #zbiera ozdoby. gnastępnie stosuje się wielokrotnie, #aż lista będzie pusta, zapisując wyniki na liście.


1
Wymiana head az a!!0oszczędza bajt.
tomsmeding

5

APL, 27 bajtów

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

Wyjaśnienie:

  • ⍵≡⍬:⍬: jeśli dane wejściowe są puste, zwróć pustą listę
  • X←⍵≥⌈\⍵: wszystkie liczby większe lub równe bieżącemu maksimum
  • (⊂X/⍵): lista tych liczb,
  • ∇⍵/⍨~X: następuje wynik działania tej funkcji na pozostałych liczbach

Zapisz bajt za pomocą {⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}. Morten martwi się brakiem odpowiedzi na jego e-maile. Wszystko w porządku?
Adám

O jej. Cieszę się, że udało ci się. Do zobaczenia w przyszłym tygodniu.
Adám

4

JavaScript (ES6), 64 bajty

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

Nie golfowany:

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
  ]


1
Przez ułamek sekundy wydawało mi się, że ?!to jakiś wymyślny nowy operator ...
Neil

Ha, tak, powinienem był wyjaśnić. Teraz dodane.
Rick Hitchcock


(i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o]Najwyraźniej wielkie umysły myślą podobnie. Niestety nie mogę się już pozbyć więcej bajtów ... Pamiętaj, że możesz usunąć f=swój kod, a może mój kod może dać ci kilka pomysłów, jak jeszcze bardziej pograć w golfa.
David Archibald

Dzięki, @DavidArchibald. Nie mogę usunąć f=z mojego kodu, ponieważ jest on rekurencyjny. Twoje jest ciekawym podejściem, ale wydaje się, że nie działa w przypadku kilku przypadków testowych. Na przykład zwraca [[5,8],[4],[3],[7],[6]] w przypadku przedostatniej.
Rick Hitchcock,

4

R , 61 bajtów

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

Wypróbuj online!

Funkcja rekurencyjna. sum(x|1)jest skrótem length(x), więc ta rekurencja będzie działać, dopóki nie xbędzie pusta. cummaxprzyjmuje skumulowane maksimum x, które następnie porównuje się xponownie. W ten sposób powstaje wektor boolowski o długości x, w którym wszystkie PRAWDA odpowiadają posortowanym wartościom. Używamy tego, aby wziąć podzbiór xi printto. Funkcja jest następnie wywoływana ponownie w pozostałej części x.


4

Java 8, 182 179 177 bajtów

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 bajty dzięki @Nevay .
-2 bajty przy użyciu Stackzamiast Vector.

Wyjaśnienie:

Wypróbuj tutaj.

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

Czy możesz użyć try{}catch{}zamiast sprawdzać przeciwko, l.size()aby zaoszczędzić trochę?
TheLethalCoder

1
Możesz rozpocząć wewnętrzną pętlę od 0i usunąć nawiasy zewnętrznej pętli for 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 bajty).
Nevay

3

C #, 188 203 bajtów

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

Liczba bajtów obejmuje +18 dla:

using System.Linq;

Wypróbuj online!


@ RickHitchcock Naprawiono kosztem 15 bajtów! Fajne miejsce.
TheLethalCoder

Dobra robota:) +1
Rick Hitchcock

3

C ++ 14, 118 108 bajtów

Wykorzystanie algorytmu z odpowiedzi Haskell w0lf .

Jako nienazwana ogólna lambda. Pierwszy parametr jest pojemnikiem wartości do droportowania (podobnie vector<int>), a drugi parametr wymaga zgodnego pustego pojemnika pojemników (podobnie vector<vector<int>>) dla wartości zwracanej przez odniesienie.

W pierwszej wersji programu była R.clear;()pierwsza instrukcja, dzięki czemu pojemnik z kontenerami nie musiał być pusty. Peter Cordes pomyślał, że to może być zgodne ze specyfikacją, więc do tego doszło 10 bajtów.

[](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:;}}

Wypróbuj online!

Nie golfowany:

[](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:;
 }
}

Prawdopodobnie możesz uniknąć ominięcia R.clear()i wystarczy, że dzwoniący zacznie od pustego kontenera.
Peter Cordes,

@PeterCordes dobry pomysł, mogę uszanować moje inne odpowiedzi w C ++, które zawierały zwrot za pomocą parametru referencyjnego.
Karl Napf,

2

Python 2 , 88 bajtów

-4 bajty dzięki Arnoldowi Palmerowi

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

Wypróbuj online!

Rozwiązanie podobne do haskell @ w0lf [odpowiedź] [1]

Rzadkie zastosowanie do for-elsebudowy

Iteruj przez posortowane listy for l in r(puste na początku).
Jeśli element (z wejścia) ijest większy niż ostatni element listy l[-1], dodaj element do listy l+=[i], przerwij.
Jeśli żadna lista nie została zaakceptowana, dodaj nową listę z tymi elementamir+=[[i]]


1
88 bajtów po prostu wyłączając go z funkcji.
Arnold Palmer,

1

R, Prace w toku (89, ale nieudane)

Trzymam tu trochę pracy, ponieważ cofnąłem się w kąt za pomocą %in%(nie powiela się na zduplikowanych wpisach, w szczególności w ostatnim przypadku testowym), i muszę teraz zrobić inne rzeczy, ale jest to tutaj, jeśli ktoś chce na tym oprzeć:

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

Nie golfowany:

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

prawdopodobnie powinieneś to na razie usunąć, aby nie zanotować negatywnych ocen podczas naprawy.
Giuseppe,

1
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)działa
Giuseppe,

odstęp między ]i cjest znakiem nowej linii (lub średnikiem)
Giuseppe

Nigdy wcześniej nie widziałem "if", ale jestem całkiem nowy w golfie R. Powinieneś napisać jako własną odpowiedź, a ja mogę zdjąć moją. Podoba mi się to, co zrobiłeś z iindeksem, aby obejść ten %in%problem.
Alex Axthelm,

Nie, wykonałeś całą ciężką pracę! Nie mogłem obejść tego problemu, dopóki nie zobaczyłem twojej implementacji - nigdy bym nie pamiętał cummax!
Giuseppe,

1

JavaScript (ES6), 71 70 68 bajtów

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

Całkiem proste, po prostu iteruje tablicę, szuka pierwszej tablicy wewnętrznej, której ostatnią wartością jest <=następna wartość do upuszczenia, jeśli żadna nie istnieje, dołącz nową tablicę wewnętrzną z następną wartością do wyjścia, w przeciwnym razie dołącz następną wartość do pierwszej znaleziono wewnętrzną tablicę pasującą do warunku.

Aktualizacje

Dzięki Neil uratował trzy bajty konwersja (...,o)do ...&&oi ponowne zorganizowanie oddzwanianie do map()być bardziej zwarta.

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}


1
&&ojest bajtem krótszym niż (,o).
Neil

@Neil gah! Świetny połów, dziękuję
Patrick Roberts,

1
Lubię twój [...b].pop(), ale myślę, że (o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)oszczędza ci bajt lub dwa.
Neil,

W tym tempie czuję się zobowiązany do oznaczenia tego jako posta społeczności ... cholera
Patrick Roberts

Tylko z powodu kilku poprawek? Nadal jest to w zasadzie ten sam kod ...
Neil


1

C (gcc) , 176 175 173 bajtów

#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("");}}

Wypróbuj online!

Nieco czytelna wersja:

#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("");
    }
}


Uhh, oczywiście, jakie głupie - dzięki!
Felix Palmen

1

PHP, 91 103 96 85 bajtów

(Edytowano, aby dodać 12 znaków, print_r($r);aby spełnić wymaganie danych wyjściowych)
(Edytowano, aby usunąć 7 bajtów, gdy zezwala się na błędy PHP)
(Edytowano, aby usunąć 11 bajtów, gdy grasz zadanie dalej)

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

Dane wejściowe $adają wynik$r

Ładny:

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

Pseudo-rekurencyjna zewnętrzna pętla inicjuje tablice keep $bi discard, $daby opróżnić, a następnie wykonuje podstawową pętlę sortowania drop, w końcu ustawiając odrzucenia jako nowe dane wejściowe i dodając Keep do wyniku$r


1

PHP , 102 bajty , 98 bajtów

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

Wypróbuj online!

-4 bajty, dzięki @Umbrella

Wyjaśnienie

<?php

Ta funkcja przyjmuje listę wejściową jako tablicę.

function s($i) {

$s, która stanie się ostatecznie zwracaną listą, jest zadeklarowana jako statyczna. To rozszerza jego zakres na wszystkie wywołania tej funkcji, umożliwiając wywoływanie funkcji rekurencyjnie bez konieczności przekazywania tej listy wyników jako argumentu lub jej zwracania.

    static $s;

Pętlę przez każdą wartość na liście.

    foreach ($i as $v)

Czy to mniej niż największy aktualny członek listy?

        $v < max($l) ?

Tak, umieść go na liście w $fcelu dalszego sortowania.

                        $f[] = $v :

Nie, umieść to na liście $l.

                        $l[] = $v;

Wciśnij listę $lna listę list.

    $s[] = $l;

Jeśli jest coś na liście $f, wyślij go ponownie w celu dalszego sortowania.

    !$f ?: s($f);

Zwróć listę list.

    return $s;
}

1
Uwzględniając 31 znaków <?php function d($a){return$r;}, które pominąłem, ponieważ serdecznie mnie zmiażdżyłeś. Poza tym właśnie zdałem sobie sprawę, że oboje zapomnieliśmy wyjść.
Parasol

Grałem w golfa w swoje rozwiązanie, aby spróbować pokonać twoje bez korzystania z twojego i znalazłem sposób na ulepszenie twojego: Myślę, że możesz uratować cztery postacie, zastępując $v<max($l)?$f[]=$v:$l[]=$v;je ${$v<max($l)?f:l}[]=$v;- przynajmniej działa w moich testach.
Parasol

@Umbrella, nie wraca, generowanie ??? I dzięki za te 4 bajty. Nigdy nie myślę o takiej pracy, używaniu kodu do oceny nazwy zmiennej. Muszę pamiętać, aby wziąć pod uwagę, że w przyszłych wyzwaniach… Web
WebSmithery

Okazało się, że konsensus wydaje się akceptować zwracanie jako wynik: codegolf.meta.stackexchange.com/questions/2447/…
Umbrella

0

Szałwia, 102 bajty

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

Bardzo podobny do @Dead Possum za odpowiedź .
Dołącza każdemu członkowi xz wpierwszego wykazu w a{} listy list z xwiększą niż jest to ostatni element.
jeśli nie, dołącza [x]do a.

Naprawdę chciałbym, jeśli existszwrócony a, jeśli nic nie zostało znalezione! Próbuję również zastosować pomysł @ lineaimm w jednym wierszu ...

Pytanie: Gdybym usunął kod z funkcji, musiałbym przypisać wdo wprowadzania danych, prawda? Czy to by oszczędzało bajty?


0

Ocaml , 69 62 bajtów

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

Wyjaśnienie:

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

0

APL, 100 88 83 79 78 57 56 77 76 bajtów

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

-0 bajtów dzięki Kritixi Lithos ...

Wypróbuj online!

Musi istnieć lepszy sposób na zrobienie tego ( jest ). Wszelkie wskazówki są bardzo mile widziane i mile widziane.

W jaki sposób?

(Uwaga, niektóre z tych wyjaśnień mogą być błędne, ponieważ zapomniałem, jak to działa)

{⍵≡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)

{⍬≢⍴⍵}może zostać(⍬≢⍴)
Kritixi Lithos

Zrobiłem to już bez twojego komentarza,
Zacharý,

Jaki jest cel {(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}? Wydaje się, że jest oddzielony od wszystkiego innego
Kritixi Lithos

Bez tego pierwszy przypadek testowy byłby podobny [[1,2,5,7],[4],3]do wymaganego [[1,2,5,7],[4],[3]].
Zacharý

Być może uda ci się skrócić ten dfn do po prostu(,¨)
Kritixi Lithos


0

JavaScript (Node.js) , 125 109 106 bajtów

- 16 18 bajtów z Zacharý

-1, usuwając {i }zmieniając moduł inkrementujący, tak aby zawierał „ustaw jako ostatni na bieżący”

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}

Zasadniczo pyta, czy bieżący element jest większy niż ostatni element, dodaj do pierwszej listy. W przeciwnym razie dodaj do drugiego.

Okazało się podczas tego, że porównanie dowolnej liczby NaNzawsze będzie skutkowało false. Ciekawy!

Wyjaśnienie:

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

Wypróbuj online!


Czy musisz użyć var?
Zacharý

@ Zacharý, pozwól mi sprawdzić!
Stan Strum,

Pareny nie są potrzebne x.
Zacharý
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.