introduction

Supposons que vous vouliez calculer les maxima de queue d'une liste de nombres, c'est-à-dire le maximum de chaque suffixe non vide. Une façon de le faire est de choisir à plusieurs reprises un numéro et de le remplacer par un nombre plus élevé se produisant après, jusqu'à ce que ce ne soit plus possible. Dans ce défi, votre tâche consiste à effectuer une étape de cet algorithme.

La tâche

Votre entrée est une liste d'entiers L , qui peut être vide. Votre sortie sera la liste L où exactement un nombre L _i a été remplacé par un autre L _j , où L _i <L _j et i <j .

En d'autres termes, vous devez remplacer un nombre par un nombre plus élevé qui se produit après.

Vous pouvez choisir i et j librement parmi toutes les paires valides, et le choix peut être non déterministe.

Si ces i et j n'existent pas (c'est-à-dire que L est non croissant), votre sortie doit être L inchangée.

Exemple

Considérez l'entrée L = [3, 1, 4, -1, 2] . Les opérations possibles sont de remplacer 3 par 4 , de remplacer 1 par 4 , de remplacer 1 par 2 ou de remplacer -1 par 2 . Ainsi, les sorties possibles sont:

 [  3 ,   1 ,   4 ,  -1 ,   2 ]
 ------------------------------
 [( 4),   1 ,(  4),  -1 ,   2 ]
 [  3 ,(  4),(  4),  -1 ,   2 ]
 [  3 ,(  2),   4 ,  -1 ,(  2)]
 [  3 ,   1 ,   4 ,(  2),(  2)]

Si vous répétez les temps assez d'opération, le résultat final sera [4,4,4,2,2] , ce qui est précisément la liste des maxima de queue de L .

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Dans ce dernier cas, vous pouvez modifier l'entrée en place au lieu de renvoyer un nouveau tableau, si votre langue le permet. Les formats d'entrée et de sortie sont flexibles dans des limites raisonnables.

Le nombre d'octets le plus bas gagne.

Cas de test

Toutes les sorties possibles sont affichées.

[] -> []
[1] -> [1]
[1,2] -> [2,2]
[2,1] -> [2,1]
[4,4,4,4] -> [4,4,4,4]
[-1,-3,-10] -> [-1,-3,-10]
[1,3,10] -> [3,3,10] [10,3,10] [1,10,10]
[1,1,2,1] -> [2,1,2,1] [1,2,2,1]
[998,64,2,-94,-789] -> [998,64,2,-94,-789]
[998,2,64,-94,-789] -> [998,64,64,-94,-789]
[3,1,4,-1,2] -> [4,1,4,-1,2] [3,4,4,-1,2] [3,2,4,-1,2] [3,1,4,2,2]
[-1,4,0,4,7,2,3] -> [4,4,0,4,7,2,3] [0,4,0,4,7,2,3] [-1,4,4,4,7,2,3] [7,4,0,4,7,2,3] [-1,7,0,4,7,2,3] [-1,4,7,4,7,2,3] [-1,4,0,7,7,2,3] [2,4,0,4,7,2,3] [-1,4,2,4,7,2,3] [3,4,0,4,7,2,3] [-1,4,3,4,7,2,3] [-1,4,0,4,7,3,3]
[3542,-12311,7662,1672,6081] -> [7662,-12311,7662,1672,6081] [3542,7662,7662,1672,6081] [3542,1672,7662,1672,6081] [6081,-12311,7662,1672,6081] [3542,6081,7662,1672,6081] [3542,-12311,7662,6081,6081]

JavaScript (ES6), 41 40 39 38 octets

Un octet enregistré grâce à @Neil, un autre grâce à @ user81655

x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0)

Juste au moment où il semble reduceRightavoir enfin une chance, .mapapparaît à nouveau ...

Mathematica, 37 octets

#/.{a___,b_,c_,d___}/;b<c:>{a,c,c,d}&

Fonction pure prenant même une liste de nombres réels et renvoyant une liste de nombres réels. Recherche la première paire d'entrées consécutives dans le "mauvais" ordre et remplace la première de cette paire par la seconde. Le comportement par défaut de Nice /.signifie qu'il retourne l'entrée inchangée le cas échéant.

Note amusante: si nous remplaçons b<cpar !OrderedQ[{c,b}], alors la fonction fonctionne sur les chaînes (et vraiment n'importe quel type de données une fois que l'ordre approprié est décrit). Par exemple, #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&sur les {"programming", "puzzles", "code", "golf"}retours d' entrée {"puzzles", "puzzles", "code", "golf"}.

JavaScript (ES6), 43 39 38 octets

a=>a[a.some(e=>e<a[++i],i=0)*i-1]=a[i]

Sorties en modifiant le tableau sur place. Edit: 4 octets enregistrés grâce à @ETHproductions. 1 octet enregistré grâce à @ user81655.

Haskell , 36 octets

f(a:r@(b:_))|a<b=b:r|1>0=a:f r
f e=e

Essayez-le en ligne!

Parcourez la liste des éléments consécutifs a,bavec a<bet remplacez-les par b,b.

Amélioré de 37 octets:

f(a:b:t)|a<b=b:b:t
f(a:t)=a:f t
f e=e

Gelée , 13 11 octets

ṫJṀ€ż¹ŒpQ-ị

Remplace le plus à droite de tous les nombres possibles.

Essayez-le en ligne!

Comment ça marche

ṫJṀ€ż¹ŒpQ-ị  Main link. Argument: A (array)

 J           Yield all indices of A, i.e., the array [1, ..., len(A)].
ṫ            Dyadic tail; for index k, take all elements starting with the k-th.
             This constructs the array of suffixes.
  Ṁ€         Maximum each; map the monadic maximum atom over the suffixes.
     ¹       Identity; yield A.
    ż        Zip; construct all pairs of elements of the result to the left and the
             corresponding elements of the result to the right.
      Œp     Cartesian product. Construct all arrays that, for each index, take
             either the left or the right element.
        Q    Unique; deduplicate the resulting arrays.
         -ị  At-index -1; select the second to last result.
             The last result is A itself, the first maxima of suffixes.

MATL , 15 octets

tdt0>0whY>d*0h+

Essayez-le en ligne!

Je ne suis pas un grand fan de cette solution. Cela me semble horriblement inefficace. En particulier les sections whY>d*et 0h+.

Python 2, 139 134 93 bytes

a=input()
for i in range(len(a)):
 for j in a[i+1:]:
    if a[i]<j:a[i]=j;print a;exit()
print a

Terriblement long, mais c'est une première tentative.

-5 octets grâce à TemporalWolf
-41 (!!) octets grâce à Value Ink

MATL , 13 octets

ttd0>fX>Q)2M(

Essayez-le en ligne!

Explication

Les deux conditions suivantes sont équivalentes:

1. Il y a un nombre qui a un nombre plus élevé à sa droite
2. Il y a un nombre qui a un nombre plus élevé immédiatement à sa droite

Le code utilise la condition 2, qui est plus simple. Il calcule les incréments consécutifs et trouve le dernier positif, le cas échéant. Pour les deux entrées impliquées, il écrit la valeur de la deuxième entrée dans la première.

Cette astuce est utilisée pour gérer le cas où aucune substitution ne peut être effectuée. Notez également que l'indexation MATL est 1basée sur.

Prenons l'entrée [3,1,4,-1,2]comme exemple.

tt    % Get input implicitly and duplicate it twice
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [3,1,4,-1,2]
d     % Consecutive differences
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [-2  3 -5  3]
0>    % Are they positive?
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [0 1 0 1]
f     % Find indices of all positive differences. Result may be empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [2 4]
X>    % Maximum index with a positive difference. Empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 4
Q     % Add 1. Since the addition is elementwise, empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 5
)     % Get the entry of the input at that position
      % STACK: [3,1,4,-1,2], 2
2M    % Push maximum index with a positive difference, again
      % STACK: [3,1,4,-1,2], 2, 4
(     % Assign to that position. Implicitly display
      % STACK: [3,1,4,2,2]

Haskell , 34 33 octets

Ceci est basé sur la réponse de xnor , qui m'a suggéré de le poster moi-même.

EDIT: xnor a trouvé un octet à enregistrer.

f(a:r@(b:_))=max(b:r)$a:f r
f e=e

Essayez-le en ligne!

Fondamentalement, j'ai observé que la ramification de la méthode de xnor finit toujours par choisir la plus grande des expressions de branche, car Haskell utilise l'ordre lexicographique pour les listes. (Le cas a==bfonctionne également parce que f r>=r, ce qui peut être prouvé séparément par induction.)

Autrement dit, à chaque fois b:r > a:f r, alors b:rc'est une bonne réponse, et sinon nous pouvons reculer a:f r.

Donc, au lieu de vérifier a<bà l'avance, je calcule simplement les deux expressions et je prends le maximum. Cela pourrait donner une explosion exponentielle, bien que la paresse de Haskell évite cela à moins que aet bsoient égaux.

Python 3, 79 octets

def f(x):
 for i,a in enumerate(x):
  m=max(x[i+1:])
  if m>a:x[i]=m;break

Mute le tableau d'origine (liste) qui lui est donné. Je ne suis pas content que ce ne soit pas un lambda et je suis sûr qu'il y a de meilleures optimisations; J'espère que j'y répondrai plus tard.

Brève explication

Il prend le maximum du tableau au-delà de l'élément actuel (en commençant par le zéro). Il compare ensuite cela à l'élément lui-même: si le max est supérieur, remplacez l'élément actuel par lui et arrêtez, sinon, incrémentez-le de un et continuez d'essayer.

Rubis, 66 61 octets

->a{i=r=-1;a.map{|e|m=a[i+=1,a.size].max;r&&m>e ?(r=!r;m):e}}

Essayez-le en ligne!

C, 47 octets

f(p,n)int*p;{n>1?*p<p[1]?*p=p[1]:f(p+1,n-1):0;}

Implémentation récursive prenant comme entrée un pointeur sur le premier élément d'un tableau et la longueur du tableau. Modifie le tableau en place.

SWI-Prolog, 70 octets

f([H|T],[S|T]):-max_list(T,S),S>H,!.
f([H|T],[H|R]):-f(T,R),!.
f(I,I).

La première clause remplace le premier élément de la liste par la valeur maximale du reste de la liste, mais uniquement si ce max est plus grand. La deuxième clause appelle récursivement le prédicat pour la fin de la liste. Si aucune de ces clauses ne réussit, la troisième clause renvoie simplement l'entrée.

Ce retour n'est qu'une des solutions possibles. Il est trivial de les trouver tous avec un code très similaire, mais le cas où aucun changement n'est possible prend beaucoup plus d'octets à gérer.

Exemple:

?- f([-1,4,0,4,7,2,3], O).
O = [7, 4, 0, 4, 7, 2, 3]

R, 71 octets

a=scan()
l=length(a) 
lapply(1:l,function(x){
  a[x]=max(a[x:l])
  a
})

C, 80 octets

i,j;f(l,n)int*l;{for(i=0;i<n;++i)for(j=i;++j<n;)if(l[i]<l[j]){l[i]=l[j];j=i=n;}}

Appeler avec:

int main()
{
    int a[5]={3,1,4,-1,2};
    f(a,5);
    for(int k=0;k<5;++k)
        printf("%d ", a[k]);
}

Python 2, 89 octets

Essayez-le en ligne -1 octet grâce à @TemporalWolf
-25 octets grâce à @ValueInk
-7 octets grâce à @Cole

Fonction qui mute le tableau d'entrée

def F(A):
 for i in range(len(A)):
    r=[y for y in A[i+1:]if y>A[i]]
    if r:A[i]=r[0];break

S'il n'y avait pas besoin d'arrêter après la première itération, ce serait un peu plus joli

Python 2, 60 octets

f=lambda x:x and[x[:1]+f(x[1:]),[max(x)]+x[1:]][x[0]<max(x)]

Essayez-le en ligne!

Explication: Vérifie récursivement si un élément donné est inférieur à l' maxélément du reste de la liste. Si tel est le cas, renvoie la liste en maxremplaçant le premier élément.

TI-Basic, 72 octets

Prompt L1
If 2≤dim(L1
Then
For(A,1,dim(L1)-1
For(B,A,dim(L1
If L1(A)<L1(B
Then
L1(B→L1(A
Goto E
End
End
End
End
Lbl E
L1

Explication:

Prompt L1          # 4 bytes, input list
If 2≤dim(L1        # 7 bytes, if the list has 2 or 1 element(s), skip this part and return it
Then               # 2 bytes
For(A,1,dim(L1)-1  # 12 bytes, for each element in the list other than the last
For(B,A,dim(L1     # 9 bytes, for each element after that one
If L1(A)<L1(B      # 12 bytes, if the second is larger than the first
Then               # 2 bytes
L1(B→L1(A          # 10 bytes, replace the first with the second
Goto E             # 3 bytes, and exit
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
Lbl E              # 3 bytes
L1                 # 2 bytes, implicitly return L1

sh, 118 octets

Les entiers d'entrée sont passés comme arguments au script.

l=("$@");for i in "$@";{ for j in "$@";{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};shift;x=`expr $x+1`;};echo ${l[@]}

Panne:

l=("$@");                      #copy original list
for i in "$@";{ for j in "$@"; #check all elements j that follow element i in list
{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};   #if i<j, make i=j; print list, done
shift;                         #makes sure that i is compared only to j that occur after it
x=`expr $x+1`;};               #keeps track of i'th position in the list
echo ${l[@]}                   #prints list if it was unchanged

PHP, 88 octets

<?for(;$i+1<$c=count($a=$_GET)&&$a[+$i]>=$a[++$i];);$i>=$c?:$a[$i-1]=$a[$i];print_r($a);

Panne

for(;
$i+1<($c=count($a=$_GET))  # first condition end loop if the item before the last is reach 
&&$a[+$i]>=$a[++$i] # second condition end loop if item is greater then before 
;);
$i>=$c?:$a[$i-1]=$a[$i]; # replace if a greater item is found
print_r($a); #Output

Haskell, 48 octets

f(b:l)|l>[],m<-maximum l,b<m=m:l|1<2=b:f l
f x=x

Exemple d'utilisation: f [1,1,2,1]-> [2,1,2,1]. Essayez-le en ligne! .

Si la liste d'entrée contient au moins un élément, associez-le bau premier élément et lau reste de la liste. Si ln'est pas vide et binférieur au maximum de l, retourne le maximum suivi de l, sinon retour bsuivi d'un appel récursif de f l. Si la liste d'entrée est vide, renvoyez-la.

Raquette 202 octets

(let((g(λ(L i n)(for/list((c(in-naturals))(l L))(if(= c i)n l))))(ol'()))
(for((c(in-naturals))(i L))(for((d(in-range c(length L)))#:when(>(list-ref L d)i))
(set! ol(cons(g L c(list-ref L d))ol))))ol)

Non golfé:

(define (f L)
  (let ((replace (λ (L i n)   ; sub-function to replace i-th item in list L with n;
                   (for/list ((c (in-naturals))
                              (l L))
                     (if (= c i) n l))))
        (ol '()))             ; outlist initially empty; 
    (for ((c (in-naturals))               ; for each item in list
          (i L))
      (for ((d (in-range c (length L)))   ; check each subsequent item in list
            #:when (> (list-ref L d) i))  ; if greater, replace it in list
        (set! ol (cons (replace L c (list-ref L d)) ol)))) ; and add to outlist.
    ol))          ; return outlist.

Essai:

(f '(3 1 4 -1 2))

Sortie:

'((3 1 4 2 2) (3 2 4 -1 2) (3 4 4 -1 2) (4 1 4 -1 2))

C, 67 octets

Exécution unique, 67 octets en direct

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)l[j]=fmax(l[i],l[j]);}

Étape unique, 78 octets en direct

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)if(l[j]<l[i]){l[j]=l[i];return;}}

Tail Maxima, 96 bytes Live

x;i;j;f(l,n)int*l;{do{x=0;for(i=0;i<n;i++)for(j=0;j<i;j++)if(l[j]<l[i])l[j]=l[i],x=1;}while(x);}

Python 3 , 103 102 octets

lambda a:([a[:i]+[max(a[i:])]+a[i+1:]for i in range(len(a))if-~i==len(a)or max(a[i+1:])>a[i]]+[[]])[0]

Essayez-le en ligne!