Un algorithme de «tri»

33

Il existe un "algorithme de tri", parfois appelé tri de Staline, dans lequel, pour trier une liste, il suffit de supprimer des éléments de la liste jusqu'à ce qu'elle soit triée par ordre croissant. Par exemple la liste

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

Quand "trié" en utilisant le tri de Staline devient

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

Les trois ont été retirés car ils étaient hors d'usage.

Bien évidemment, il existe de nombreuses façons de supprimer des éléments pour trier une liste. Par exemple, toute liste comportant moins de deux éléments doit être triée. En supprimant simplement assez d'éléments à l'aveuglette, nous pouvons toujours trier une liste. Puisque c'est le cas, nous ne nous soucions que du résultat le plus long possible d'un type de Staline.

Votre tâche consistera à prendre une liste d’entiers positifs et à afficher la longueur de la liste triée (croissante) la plus longue à laquelle on puisse parvenir en supprimant des éléments de la liste originale. C'est trouver la longueur de la plus longue sous-liste triée (éventuellement non contiguë).

Les listes triées peuvent avoir le même élément plusieurs fois de suite. Vous n'avez pas besoin de prendre en charge la liste vide à moins que votre programme lui-même ne soit vide.

Notation

Votre réponse sera notée en fonction de la longueur de son propre tri le plus long possible de Staline. Les programmes seront interprétés comme une séquence d'octets plutôt que de caractères, et leur ordre sera celui naturel qui se produit en interprétant les octets sous forme de nombres. Les scores les plus bas sont meilleurs.

Ce n'est pas du

Voici un outil soigné pour vous aider à noter vos réponses.

Cas de test

[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
Assistant de blé
la source
3
En bref: affiche la longueur de la plus longue séquence croissante (non strictement) .
user202729
1
J'aime la règle "Vous n'avez pas besoin de supporter la liste vide à moins que votre programme lui-même soit vide."
Paŭlo Ebermann
Ce défi me rappelle beaucoup le défi dropsort
Stefnotch
1
J'ai fait un vérificateur à ptpb.pw/SVSt.html . Pas encore très fonctionnel, mais ça marche. (TODO: * histogramme * partitionnement en séquences les moins décroissantes * prise en charge d'autres pages de code)
user202729
@ user202729 Cool! Je l'ai ajouté à l'article. N'hésitez pas à éditer de nouvelles versions si nécessaire.
Wheat Wizard

Réponses:

8

Python 2 , longueur 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))

La sortie s'effectue via le code de sortie.

Essayez-le en ligne!

Comment ça marche

À tout moment, le tableau L garde la trace des sous- tableaux triés les plus longs rencontrés jusqu'à présent; L[une-1] est la longueur du plus long qui se termine par une .

Initialement, nous n’avons pas traité d’éléments de tableau. L est donc entièrement composé de zéros.

une[L[0],,L[une-1]]uneuneuneL[une-1]

L

Dennis
la source
Pouvez-vous s'il vous plaît expliquer, pourquoi cela fonctionne? J'ai du mal à le comprendre :(
Dead Possum
J'ai ajouté une explication.
Dennis
5

Haskell , Score 8 7, 48 octets

(l:k)%d|d>l=k%d|3>2=max(1+k%l)(k%d)
c%b=0
a=(%0)

Essayez-le en ligne!

La plus longue sous-liste triée est

%%%%%%)
Assistant de blé
la source
4

Gelée , longueur  4  2

ṢƑƇZLƲ}ŒP

Essayez-le en ligne!

Octets dans la page de code de Jelly

183 146 144 90 76 169 125 19 80

Comment ça marche

ṢƑƇ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
la source
3

Pyth, score 3 2 ( 7 octets)

leSI#y

A enregistré un point grâce à Anders Kaseorg.
Essayez-le ici

Explication

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.

la source
leSI#yscores 2.
Anders Kaseorg
2

Stax , 4 stales de longueur maximale

S{:^fF%|M

Exécuter et déboguer

Cela fonctionne comme ça.

S       powerset of input
{:^f    filter by non-descending sequences
F%|M    take the maximum length remaining
récursif
la source
2

R , Score 15 11, 72 62 octets

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

Essayez-le en ligne!

Ports Dennis 'Python répondent à R.

Giuseppe
la source
Changer les noms des variables ne changera rien, car, comme l'indique votre dernier lien, aucun d'entre eux n'est utilisé dans la sous-chaîne (trouvée) qui donne le score 15.
Ørjan Johansen
@ ØrjanJohansen ah, bien sûr, je suis plutôt bête. Je suppose qu'une autre approche est nécessaire.
Giuseppe
2

Brachylog , longueur 2 (4 octets)

⊇≤₁l

Essayez-le en ligne!

Une réponse qui permet d’être aussi concise en n’étant pas beaucoup plus courte.

(08 03 80 6C dans la page de code de Brachylog)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)
Chaîne non liée
la source
Je suis venu avec ►LSnmOṖHusk mais son score (pour sa longueur au moins) est trop mauvais pour la peine de poster ...
Unrelated String