Ein "Sortier" -Algorithmus

33

Es gibt einen "Sortieralgorithmus", der manchmal als Stalin-Sortierung bezeichnet wird. Um eine Liste zu sortieren, entfernen Sie einfach Elemente aus der Liste, bis sie in aufsteigender Reihenfolge sortiert sind. Zum Beispiel die Liste

[1, 2, 4, 5, 3, 6, 6]

Wenn "sortiert" mit Stalin sortiert wird

[1, 2, 4, 5, 6, 6]

Die drei wurden entfernt, weil es nicht in Ordnung war.

Nun gibt es offensichtlich viele Möglichkeiten, Elemente zu entfernen, um eine Liste zu sortieren. Zum Beispiel muss jede Liste mit weniger als zwei Elementen sortiert werden, sodass wir immer eine Liste sortieren können, indem Sie einfach genug Elemente blind entfernen. Da dies der Fall ist, kümmern wir uns nur um das längstmögliche Ergebnis einer Stalin-Sorte.

Ihre Aufgabe wird es sein, eine Liste positiver Ganzzahlen zu erstellen und die Länge der am längsten sortierten (aufsteigenden) Liste auszugeben, die durch Entfernen von Elementen aus der ursprünglichen Liste erreicht werden kann. Das ist die Länge der am längsten sortierten (möglicherweise nicht zusammenhängenden) Unterliste.

Sortierte Listen können dasselbe Element mehrmals hintereinander enthalten. Sie müssen die leere Liste nur dann unterstützen, wenn Ihr Programm selbst leer ist.

Wertung

Ihre Antwort wird durch die Länge der eigenen längsten möglichen Stalin-Sorte bewertet. Programme werden als Folge von Bytes und nicht als Zeichen interpretiert, und ihre Reihenfolge ist die natürliche, die sich aus der Interpretation der Bytes als Zahlen ergibt. Niedrigere Werte sind besser.

Dies ist kein

Hier ist ein nützliches Tool, mit dem Sie Ihre Antworten bewerten können.

Testfälle

[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
Weizen-Assistent
quelle
3
Kurz gesagt: Gibt die Länge der längsten (nicht streng) ansteigenden Sequenz aus .
user202729
1
Ich mag die Regel "Sie müssen die leere Liste nur dann unterstützen, wenn Ihr Programm selbst leer ist."
Paŭlo Ebermann
Diese Herausforderung erinnert mich sehr an die Dropsort-Herausforderung: codegolf.stackexchange.com/questions/61808/…
Stefnotch
1
Ich habe einen Checker bei ptpb.pw/SVSt.html erstellt . Immer noch nicht sehr funktional, aber es funktioniert. (TODO: * Balkendiagramm * Unterteilung in am wenigsten abnehmende Sequenzen * Unterstützung für andere Codepages)
user202729
@ user202729 Cool! Ich habe es dem Beitrag hinzugefügt. Sie können bei Bedarf auch neuere Versionen bearbeiten.
Weizen-Assistent

Antworten:

8

Python 2 , Länge 14 12 10 9

M=max;X=exit;i=input();L=[0]*M(i)
for	a	in	i:L[a-1]=M(L[:a])+1
X(M(L))

Die Ausgabe erfolgt über den Exit-Code.

Probieren Sie es online!

Wie es funktioniert

Zu jeder Zeit verfolgt das Array L die längsten sortierten Subarrays, die bisher angetroffen wurden; L[ein-1] ist die Länge der längsten, die mit ein endet .

Anfangs haben wir keine Array-Elemente verarbeitet, daher besteht L vollständig aus Nullen.

ein[L[0],,L[ein-1]]eineineinL[ein-1]

L

Dennis
quelle
Kannst du bitte erklären, warum es funktioniert? Ich habe schwere Zeiten, um es zu verstehen :(
Dead Possum
Ich habe eine Erklärung hinzugefügt.
Dennis
5

Gelee , Länge  4  2

ṢƑƇZLƲ}ŒP

Probieren Sie es online!

Bytes in Jellys Codepage

183 146 144 90 76 169 125 19 80

Wie es funktioniert

ṢƑƇZLƲ}ŒP  Main link. Argument: A (array)

       ŒP  Powerset; yield P, the array of all sub-arrays of A.
     Ʋ     Vier; combine the preceding four links into a monadic chain...
      }    and apply the chain to the right argument (P).
  Ƈ            Comb; only keep arrays for which the link to the left returns 1.
ṢƑ             Sort fixed; yield 1 if sorting doesn't alter the array.
   Z           Zip; read the filtered powerset by columns.
    L          Take the length.
Dennis
quelle
3

Pyth, 3 Punkte 2 ( 7 Bytes)

leSI#y

Dank Anders Kaseorg einen Punkt gespart.
Probieren Sie es hier aus

Erläuterung

leSI#y
     yQ    Take the power set of the (implicit) input (preserving order).
  SI#      Get the ones that are sorted.
 e         Take the last (longest).
l          Get the length.
Gedächtnisstütze
quelle
leSI#yScores 2.
Anders Kaseorg
2

R , Score 15 11, 72 62 Bytes

function(L,M=max,A=1:M(L)*0){for(Y in L)A[Y]=M(A[1:Y])+1;M(A)}

Probieren Sie es online!

Portiert Dennis 'Python-Antwort auf R.

Giuseppe
quelle
Das Ändern von Variablennamen hilft nicht weiter, da, wie Ihr letzter Link zeigt, keiner von ihnen in der (gefundenen) Teilzeichenfolge verwendet wird, die Punktzahl 15 ergibt.
Ørjan Johansen
@ ØrjanJohansen ah, natürlich bin ich eher doof. Ich nehme an, ein anderer Ansatz ist notwendig.
Giuseppe
2

Brachylog , Länge 2 (4 Bytes)

⊇≤₁l

Probieren Sie es online!

Eine Antwort, die sich dadurch auszeichnet, dass sie nicht viel kürzer sortiert ist.

( 08 03 80 6Cin Brachylogs Codepage)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)
Nicht verwandte Zeichenfolge
quelle
Ich habe mir ►LSnmOṖHusk ausgedacht, aber seine Punktzahl (zumindest für seine Länge) ist zu schlecht, um sich die Mühe zu machen, etwas zu posten ...
Saite ohne