Opis wyzwania
Monotoniczny podciągiem jest ciągiem liczb [a1, a2, ..., an]
takie, że
a1 <= a2 <= ... <= an
lub a1 >= a2 >= ... >= an
. [1, 3, 3, 7, 9, 13, 13, 100]
jest monotonicznym (nie malejącym) podsekwencją, a także [9, 4, 4, 3, 0, -10, -12]
(ten nie jest rosnący), ale [1, 3, 6, 9, 8]
nie jest. Biorąc pod uwagę listę liczb całkowitych (w dowolnym rozsądnym formacie), wypisz najmniejszą liczbę, N
tak aby sekwencję tych liczb całkowitych można podzielić na N
sekwencje monotoniczne.
Przykłady
[1, 3, 7, 5, 4, 2] -> [[1, 3, 7], [5, 4, 2]] -> 2
[1, 2, 3, 4, 5, 6] -> [1, 2, 3, 4, 5, 6] -> 1
[3, 1, 5, 5, 6] -> [[3, 1], [5, 5, 6]] -> 2
[4, 6, 8, 9, 1, 6] -> [[4, 6, 8, 9], [1, 6]] -> 2
[3, 3, 3, 3] -> [[3, 3, 3, 3]] -> 1
[7] -> [[7]] -> 1
[] -> [] -> anything (you don't actually have to handle an empty list case)
[1, 3, 2, -1, 6, 9, 10, 2, 1, -12] -> [[1, 3], [2, -1], [6, 9, 10], [2, 1, -12]] -> 4
[4,4,8,8,1,4,5] -> 2
0 / undefined
, to brzmi jak powinno być 0 lub reprezentacjaundefined
w naszym języku, ale z Twojego komentarza na Jonathana Allana Jelly odpowiedzi, wygląda na toundefined
środkówanything
... Który to ? W drugim przypadku sugerowałbym pisanieanything
zamiastundefined
Odpowiedzi:
Brachylog , 12 bajtów
Wypróbuj online!
Zwraca
false.
pustą listę[]
.Wyjaśnienie
Zwróci to najmniejszą, ponieważ
~c
wygeneruje punkty wyboru od najmniejszej liczby podlist do największych.źródło
Z
ponieważZ
jest nazwą zmiennej; więc mówimy „wywołaj ten program z wyjściem jako zmienną”. Można zmienićZ
na jakikolwiek inny pisania wielkimi literami ; to tylko nazwa zmiennej. Przyczyną tego argumentu jest umożliwienie faktycznego ustawienia wyjścia na coś zamiast zmiennej.4
w tym przykładzie, powie ci, czy to jest poprawne, czy nie )3
ponieważ nie znajdzie żadnej listy podlist, w których wszystkie są monotoniczne i długiej3
. To zajmuje dużo czasu, ponieważ wypróbuje wszystkie możliwe listy podlist, nawet te, które faktycznie są dłuższe niż 3 elementy, ponieważ długość jest sprawdzana po znalezieniu listy. Na5
to mówitrue
, bo jest rzeczywiście co najmniej jeden wykaz długości5
z monotonicznych podlist który działa. Zatem ten program zwraca najmniejszą długość, gdy wyjście jest zmienną i czy istnieje jakaś lista o tej długości, która działa, jeśli wyjście jest liczbą całkowitą.Perl, 65 bajtów
62 bajty kodu + 3 bajty na
-n
flagę.monot_seq.pl:
Podaj dane wejściowe bez ostatniej nowej linii, z liczbami oddzielonymi spacjami:
-5 bajtów dzięki @Gabriel Benamy.
źródło
($&<=>$1)*($1<=>$2)||$1==$2
w($&<=>$1)*($1<=>$2)>=0
Mathematica, 111 bajtów
Nazwana funkcja
f
przyjmująca niepustą listę liczb (liczb całkowitych lub nawet liczb rzeczywistych). Działa od przodu do tyłu, wielokrotnie odrzucając pierwszy element i śledząc, ile podsekwencji jest potrzebnych. Więcej pełnych słów:źródło
d=#2-#&@@#&;
zdefiniowanie jednegof
lub jednegog
operatora±
prawdopodobnie spowoduje zapisanie niektórych bajtów.Galaretka , 19 bajtów
TryItOnline! lub uruchom wszystkie testy (wyniki pustej listy w
1
)W jaki sposób?
(Nie jestem jednak przekonany, że jest to najbardziej odpowiednia metoda minimalizacji liczby bajtów)
źródło
1
(co wydaje mi się bardziej sensowne niż0
).undefined
znaczy - wynik nie ma znaczenia.Perl,
98979679 bajtówDane wejściowe są dostarczane jako lista liczb oddzielonych spacjami, podawana w czasie wykonywania, np
(4 to wynik)
Czytelny:
„Operator statku kosmicznego”
<=>
zwraca -1, jeśli LHS <RHS, 0, jeśli LHS = RHS, i +1, jeśli LHS> RHS. Porównując trzy kolejne elementy$a,$b,$c
, aby ustalić, czy są one monotoniczna, to tylko konieczne, aby stwierdzić, że nie jest to przypadek, że dokładnie jeden$a<=>$b
,$b<=>$c
to 1, a drugi jest -1 - co się dzieje, gdy tylko ich produkt jest -1. Jeśli którykolwiek$a==$b
lub$b==$c
, to sekwencja jest monotoniczna, a iloczyn wynosi 0. Jeśli$a < $b < $c
, więc oba dają w wyniku -1, a -1 * -1 = 1. Jeśli$a > $b > $c
, to oba dają 1, a 1 * 1 = 1. W obu przypadkach sekwencja jest monotoniczna i chcemy kontynuować.Jeśli iloczyn jest mniejszy niż 0, wiemy, że sekwencja nie jest monotoniczna i odrzucamy wartości,
$a,$b
które aktualnie przechowujemy, i zwiększamy licznik podsekwencji. W przeciwnym razie przejdziemy o jeden numer do przodu.Nic nie zwraca, jeśli dane wejściowe są puste, w przeciwnym razie zwraca najmniejszą liczbę ciągłych monotonicznych podsekwencji
źródło
1
iif
(a może robisz to na starych perlach, ale na ostatnich nie.). Również można (prawdopodobnie) zastąpićshift
przezpop
. Istnieją jednak przypadki testowe, w których kod nie działa:6 3 6 3
(drukujesz 3 zamiast 2),4 3 2 1
(drukujesz 2 zamiast 1). Używajpop
zamiast jeshift
rozwiązywać, ale twórz nowe (1 2 3 4
drukuje 3 zamiast 1) ...C # 6,
297209 bajtówNie obeznany z wyjaśnieniami
źródło
JavaScript (ES6), 69 bajtów
Pobiera dane wejściowe jako wiele parametrów. Działa poprzez rekurencyjne porównywanie pierwszych trzech elementów, aby sprawdzić, czy są monotoniczne, jeśli tak, usuwa środkowy element, ponieważ jest bezużyteczny, jeśli nie, usuwa pierwsze dwa elementy i rozpoczyna nową sekwencję.
źródło
Clojure, 97 bajtów
reduce
śledzi bieżącą podsekwencję i oblicza, ile razy<=
i>=
warunki zawodzą. Ostatni1
bierze drugi element z wyniku (jest licznikiemi
).źródło