Sekwencje przekraczania

Biorąc pod uwagę listę dodatnich liczb całkowitych A, nazwij ją rosnącą sekwencją, jeśli każdy element jest większy lub równy poprzedniemu; i nazwijmy to sekwencją malejącą, jeśli każdy element jest mniejszy lub równy poprzedniemu.

Niektóre rosnące sekwencje:

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

Niektóre malejące sekwencje:

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

Sekwencja przejście to lista, która może być rozłożony na dwie rozłączne podsekwencje jednej rosnącej kolejności, a drugi malejącej kolejności.

Na przykład lista:

[3,5,2,4,1]

jest sekwencją krzyżującą, ponieważ można ją podzielić na:

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

gdzie [3,4]jest rosnąca podsekwencja, a [5,2,1]malejąca podsekwencja. Nazwiemy taką parę (rosnącą, malejącą) podsekwencje rozkładem sekwencji krzyżującej.

Lista:

[4,5,2,1,3]

nie jest sekwencją krzyżującą; nie ma możliwości rozłożenia go na rosnącą i malejącą podsekwencję.

Twoim zadaniem jest napisanie programu / funkcji przyjmującej jako dane wejściowe listę liczb całkowitych dodatnich; a jeśli jest to sekwencja krzyżująca, zwróć dwie listy w jednym z ich rozkładów; lub jakąś spójną wartość „falsey”, jeśli lista nie jest sekwencją krzyżowania.

To jest golf golfowy ; Zwycięża najkrótszy program / funkcja w każdym języku.

Zasady:

• Dane wejściowe są elastyczne.
• Zwykłe luki są zabronione.
• Jeśli istnieje wiele prawidłowych sposobów dekompozycji danych wejściowych, możesz wyprowadzić jeden lub wszystkie z nich.
• Formatowanie wyjściowe dla rozkładu jest elastyczne; ale musi być jednoznaczne w odniesieniu do rozróżnienia między dwoma podsekwencjami.
• Możesz użyć dowolnej spójnej wartości wyjściowej, aby wskazać, że dane wejściowe nie są sekwencją przecięcia; pod warunkiem, że jest to jednoznaczne w porównaniu do wyniku dla dowolnej sekwencji krzyżowania. W odpowiedzi należy podać wartość falsey.

Przypadki testowe:

Używając Falsedo wskazania sekwencji nie przekraczających:

[3, 5, 2, 4, 1] => [3, 4], [5, 2, 1]
[3, 5, 2, 4, 4, 1, 1] => [3, 4, 4], [5, 2, 1, 1]

[7, 9, 8, 8, 6, 11] => [7, 8, 8, 11], [9, 6]
[7, 9, 8, 8, 6, 11] => [7, 9, 11], [8, 8, 6] # also valid
[7, 9, 8, 8, 6, 11] => [7, 8, 11], [9, 8, 6] # also valid

[7, 8, 9, 10, 20, 30] => [7, 8, 9, 20, 30], [10]
[7, 8, 9, 10, 20, 30] => [8, 9, 10, 20, 30], [7] # this is also valid

[5, 5, 5] => [5, 5, 5], []

[4, 5, 2, 1, 3] => False
[3, 4, 3, 4, 5, 2, 4] => False

05AB1E , 15 14 13 bajtów

2.Œ.ΔćRšεü@}W

Wypróbuj online lub sprawdź poprawność wszystkich przypadków testowych .

Wyjaśnienie:

2.Π                   # all partitions of the input in 2 subsequences
   .Δ                  # find the first partition such that the following gives 1
     ćRš               # reverse the first subsequence
        ε  }           # map each subsequence to
         ü@            # pairwise greater-than
            W          # minimum (1 if all 1s, 0 otherwise)

Galaretka , 12 bajtów

ŒPżṚ$ṢNÞƭ€ƑƇ

Wypróbuj online!

JavaScript (ES6),  110 105  104 bajtów

Zwraca znakami [[decreasing], [increasing]]lub jeśli nie ma rozwiązania.$1$

f=(a,n,b=[[],[]])=>a.some((v,i)=>[...x=b[i=n>>i&1]].pop()*(x.push(v),i-=!i)>v*i)?n>>a.length||f(a,-~n):b

Wypróbuj online!

W jaki sposób?

Próbujemy wszystkich wartości maski bitowej od do , gdzie jest długością tablicy wejściowej.$n$$0$$2^L$$L$

W każdej iteracji, podzielić na dwie oryginalnej tablicy podciągów (zmniejszenie) i (zwiększenie), przy każdy bit z wiedzieć, gdzie każda wartość przechodzi.$b[0]$$b[1]$$i$$n$

Gdy do podsekwencji dodawana jest nowa wartość, jednocześnie upewniamy się, że nie jest ona nieważna, porównując ją z ostatnią wartością wyskakującą z kopii podsekwencji. Kierunek nierówności jest zawsze taki sam, ale argumenty są mnożone przez (jeśli ) lub (jeśli ):$1$$i=1$$-1$$i=0$

[...x = b[i = n >> i & 1]].pop() * (x.push(v), i -= !i) > v * i

Zatrzymujemy się i zwracamy gdy tylko wszystkie wartości miną , tj. Jest to fałsz.$b$some()

Haskell, 84 bajty

(([],[])#)
(d,i)#(a:b)=(#b)=<<[(d++[a],i)|all(a<=)d]++[(d,i++[a])|all(a>=)i]
p#_=[p]

Zwraca listę wszystkich prawidłowych (decreasing,increasing)par lub pustą listę, jeśli nie ma takiej pary.

Wypróbuj online!

Python 3 , 109 107 bajtów

def f(l,i=[],d=[]):
 if l:s,*r=l;i and s<i[-1]or f(r,i+[s],d);d and s>d[-1]or f(r,i,d+[s])
 else:print(i,d)

Wypróbuj online!

Funkcja drukuje wszystkie możliwe dekompozycje na standardowe wyjście. Jeśli nie ma możliwych rozkładów, nic nie jest drukowane.

Dzięki @Sriotchilism O'Zaic za sugestie ulepszeń.

Brachylog , 17 bajtów

;Ṣzpᵐz{ℕˢ}ᵐ≤₁ʰ≥₁ᵗ

Wypróbuj online!

Prawdopodobnie jest w tym sporo miejsca na grę w golfa.

Python 2 , 147 bajtów

def f(a):
 for i in range(2**len(a)):
	x=[];y=[]
	for c in a:[x,y][i&1]+=[c];i/=2
	if x==sorted(x)and y[::-1]==sorted(y[::-1]):return x,y
 return 0

Wypróbuj online!