Wprowadzenie

Załóżmy, że chcesz obliczyć maksima ogonowe listy liczb, czyli maksimum każdego niepustego sufiksu. Jednym ze sposobów jest wielokrotne wybieranie jednej liczby i zastępowanie jej wyższą liczbą występującą po niej, dopóki nie będzie to już możliwe. W tym wyzwaniu Twoim zadaniem jest wykonanie jednego kroku tego algorytmu.

Zadanie

Twoje dane wejściowe to lista liczb całkowitych L , które mogą być puste. Jego wynik będzie lista L gdzie dokładnie jedna liczba L _i został zastąpiony przez inny L _j , gdzie L _i <L _j i i <j .

Innymi słowy, zastąpisz jedną liczbę wyższą liczbą, która pojawi się po niej.

Możesz wybrać i i j swobodnie wśród wszystkich prawidłowych połączeń, a wybór może być niedeterministyczny.

Jeśli takie i i j nie istnieją (tj. L nie rośnie), twój wynik będzie L niezmieniony.

Przykład

Rozważ wejście L = [3, 1, 4, -1, 2] . Możliwe operacje to zamiana 3 na 4 , 1 na 4 , 1 na 2 lub -1 na 2 . Zatem możliwe wyniki to:

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

Jeśli powtórzysz operację wystarczająco dużo razy, wynikiem końcowym będzie [4,4,4,2,2] , czyli dokładnie lista maksymów ogona L .

Zasady i punktacja

Możesz napisać pełny program lub funkcję. W drugim przypadku możesz zmodyfikować wprowadzone dane zamiast zwracać nową tablicę, jeśli Twój język na to pozwala. Formaty wejściowe i wyjściowe są elastyczne w granicach rozsądku.

Wygrywa najniższa liczba bajtów.

Przypadki testowe

Pokazane są wszystkie możliwe wyjścia.

[] -> []
[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 bajtów

Zapisano bajt dzięki @Neil, kolejne dzięki @ user81655

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

Właśnie kiedy wydaje się, że reduceRightmoże w końcu mieć szansę, .mappojawia się ponownie ...

Mathematica, 37 bajtów

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

Czysta funkcja polegająca na pobieraniu nawet liczb rzeczywistych i zwracaniu listy liczb rzeczywistych. Szuka pierwszej pary kolejnych wpisów w „złej” kolejności i zastępuje pierwszą z tej pary drugą. Ładne domyślne zachowanie /.oznacza, że ​​zwraca wejście niezmienione, gdy jest to właściwe.

Zabawne dygresja: jeśli zastąpimy b<cz !OrderedQ[{c,b}], wówczas funkcja działa na smyczki (i naprawdę każdy rodzaj danych, gdy odpowiednia kolejność jest opisany). Na przykład #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&przy {"programming", "puzzles", "code", "golf"}zwrotach wejściowych {"puzzles", "puzzles", "code", "golf"}.

JavaScript (ES6), 43 39 38 bajtów

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

Dane wyjściowe poprzez modyfikację tablicy w miejscu. Edycja: Zapisano 4 bajty dzięki @ETHproductions. Zapisano 1 bajt dzięki @ user81655.

Haskell , 36 bajtów

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

Wypróbuj online!

Przejrzyj listę pod kątem kolejnych elementów a,b z a<bi zmienia je b,b.

Poprawiono z 37 bajtów:

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

Galaretka , 13 11 bajtów

ṫJṀ€ż¹ŒpQ-ị

Zastępuje prawą ze wszystkich możliwych liczb.

Wypróbuj online!

Jak to działa

ṫ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 bajtów

tdt0>0whY>d*0h+

Wypróbuj online!

Nie jestem wielkim fanem tego rozwiązania. Wydaje mi się to okropnie nieefektywne. W szczególności sekcje whY>d*i 0h+.

Python 2, 139 134 93 bajtów

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

Okropnie długo, ale to pierwsza próba.

-5 bajtów dzięki TemporalWolf
-41 (!!) bajtów dzięki Value Ink

MATL , 13 bajtów

ttd0>fX>Q)2M(

Wypróbuj online!

Wyjaśnienie

Następujące dwa warunki są równoważne:

1. Jest liczba, która ma wyższą liczbę po prawej stronie
2. Jest liczba, która ma wyższą liczbę bezpośrednio po jej prawej stronie

Kod wykorzystuje warunek 2, który jest prostszy. Oblicza kolejne przyrosty i znajduje ostatni pozytywny, jeśli taki istnieje. W przypadku dwóch zaangażowanych wpisów zapisuje wartość drugiego wpisu w pierwszym.

Ta sztuczka służy do obsługi przypadku, gdy nie można dokonać zamiany. Zauważ też, że indeksowanie MATL jest 1oparte na.

[3,1,4,-1,2]Jako przykład weźmy dane wejściowe .

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 bajty

Jest to oparte na odpowiedzi Xnora , który zasugerował, żebym sam to opublikował.

EDYCJA: xnor znalazł bajt do zapisania.

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

Wypróbuj online!

Zasadniczo zauważyłem, że rozgałęzienie metody xnor zawsze kończy się wybraniem któregokolwiek z wyrażeń rozgałęzienia, które jest największe, ponieważ Haskell stosuje porządek leksykograficzny dla list. (Przypadek, gdy a==bdziała również, ponieważ f r>=r, co można udowodnić oddzielnie przez indukcję.)

Innymi słowy, gdy b:r > a:f r, wtedy b:rjest poprawna odpowiedź, a poza tym możemy się recursea:f r .

Zamiast sprawdzać a<bz wyprzedzeniem, po prostu obliczam oba wyrażenia i biorę maksimum. To może dać wykładniczy blowup, choć lenistwo Haskell'a unika że chyba ai bsą równe.

Python 3, 79 bajtów

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

Mutuje oryginalną tablicę (listę), która została mu podana. Jestem niezadowolony, że to nie jest lambda i jestem pewien, że istnieją lepsze optymalizacje; Mam nadzieję, że zajmę się nimi później.

Krótkie wyjaśnienie

Zajmuje maksimum tablicy obok bieżącego elementu (zaczynając od zera). Następnie porównuje to z samym elementem: jeśli maksimum jest większe, zastąp go bieżącym elementem i zatrzymaj, w przeciwnym razie, przyrost o jeden i próbuj tego.

Rubin, 66 61 bajtów

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

Wypróbuj online!

C, 47 bajtów

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

Implementacja rekurencyjna przyjmująca za swój wskaźnik wskaźnik do pierwszego elementu tablicy i długość tablicy. Zmienia tablicę na miejscu.

SWI-Prolog, 70 bajtów

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

Pierwsza klauzula zastępuje pierwszy element listy maksymalną wartością reszty listy, ale tylko wtedy, gdy to maksimum jest większe. Druga klauzula rekurencyjnie wywołuje predykat dla końca listy. Jeśli żadna z tych klauzul się nie powiedzie, trzecia klauzula po prostu zwraca dane wejściowe.

Ten zwrot to tylko jedno z możliwych rozwiązań. Znalezienie wszystkich z bardzo podobnym kodem jest banalne, ale wtedy przypadek, w którym zmiana nie jest możliwa, zajmuje znacznie więcej bajtów.

Przykład:

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

R, 71 bajtów

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

C, 80 bajtów

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

Zadzwoń z:

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 bajtów

Wypróbuj online -1 bajt dzięki @TemporalWolf
-25 bajtów dzięki @ValueInk
-7 bajtów dzięki @Cole

Funkcja, która mutuje tablicę wejściową

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

Gdyby nie było potrzeby zatrzymywania się po pierwszej iteracji, byłoby to trochę ładniejsze

Python 2, 60 bajtów

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

Wypróbuj online!

Objaśnienie: Rekurencyjnie sprawdza, czy dany element jest mniejszy niż maxelement z pozostałej części listy. Jeśli tak, zwraca listę z maxzastąpieniem pierwszego elementu.

TI-Basic, 72 bajty

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

Wyjaśnienie:

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 bajtów

Wejściowe liczby całkowite są przekazywane do skryptu jako argumenty.

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

Awaria:

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 bajtów

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

Awaria

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 bajtów

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

Przykład użycia: f [1,1,2,1]-> [2,1,2,1].Wypróbuj online! .

Jeśli lista wejściowa zawiera co najmniej jeden element, powiąż bz pierwszym elementem i lresztą listy. Jeśli lnie jest puste i bmniejsze niż maksimum l, zwróć maksimum, a następnie l, w przeciwnym razie return, ba następnie rekurencyjne wywołanie f l. Jeśli lista wejściowa jest pusta, zwróć ją.

Rakieta 202 bajtów

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

Nie golfowany:

(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.

Testowanie:

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

Wydajność:

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

C, 67 bajtów

Single Run, 67 bajtów na żywo

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

Pojedynczy krok, 78 bajtów na żywo

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 bajtów na żywo

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 bajtów

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]

Wypróbuj online!