Opis wyzwania

Monotoniczny podciągiem jest ciągiem liczb [a1, a2, ..., an]takie, że

a1 <= a2 <= ... <= anlub 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ę, Ntak aby sekwencję tych liczb całkowitych można podzielić na Nsekwencje 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

Brachylog , 12 bajtów

~c:{<=|>=}al

Wypróbuj online!

Zwraca false.pustą listę [].

Wyjaśnienie

(?)~c                 Take a list of sublists which when concatenated result in the Input
     :{<=|>=}a        Each sublist must be either increasing or decreasing
              l(.)    Output is the length of that list

Zwróci to najmniejszą, ponieważ ~cwygeneruje punkty wyboru od najmniejszej liczby podlist do największych.

Perl, 65 bajtów

62 bajty kodu + 3 bajty na -nflagę.

monot_seq.pl:

#!perl -n
s/\S+ /($_<=>$&)*($&<=>$')-$g>=0?$g=1:$.++;$g--;$_=$&/ge,$_=$.

Podaj dane wejściowe bez ostatniej nowej linii, z liczbami oddzielonymi spacjami:

$ echo -n "1 3 2 -1 6 9 10 2 1 -12" | perl -M5.010 monot_seq.pl
4

-5 bajtów dzięki @Gabriel Benamy.

Mathematica, 111 bajtów

d=#[[2]]-#[[1]]&;r=Rest;f@{n_}:=1;f@k__:=If[d@k==0,f@r@k,g[k Sign@d@k]];g@{n_}:=1;g@k__:=If[d@k>0,g@r@k,1+f@r@k]

Nazwana funkcja fprzyjmują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:

d = #[[2]] - #[[1]] &;         function: difference of the first two elements
r = Rest;                      function: a list with its first element dropped
f@{n_} := 1;                   f of a length-1 list equals 1
f@k__ := If[d@k == 0, f@r@k,   if the first two elements are equal, drop one
                                 element and call f again ...
            g[k Sign@d@k]];  ... otherwise call the helper function g on the
                                 list, multiplying by -1 if necessary to ensure
                                 that the list starts with an increase
g@{n_} := 1;                   g of a length-1 list equals 1
g@k__ := If[d@k > 0, g@r@k,    if the list starts with an increase, drop one
                                 element and call g again ...
            1 + f@r@k];        ... otherwise drop one element, call f on the
                                 resulting list, and add 1

Galaretka , 19 bajtów

IṠḟ0E
ŒṖÇ€€0e$Ðḟḅ1Ṃ

TryItOnline! lub uruchom wszystkie testy (wyniki pustej listy w1)

W jaki sposób?

IṠḟ0E - Link 1, test for monotonicity: a sublist
I     - incremental differences
 Ṡ    - sign {fall:-1; same:0; rise:1}
  ḟ0  - filter out the zeros
    E - all equal?

ŒṖÇ€€0e$Ðḟḅ1Ṃ - Main link
ŒṖ            - all partitions of the input list
  Ç€€         - call last link (1) as a monad for €ach for €ach
        Ðḟ    - filter out results:
       $      -    last two links as a monad
     0e       -        contains zero?
          ḅ1  - convert from unary (vectorises)
            Ṃ - minimum

(Nie jestem jednak przekonany, że jest to najbardziej odpowiednia metoda minimalizacji liczby bajtów)

Perl, 98 97 96 79 bajtów

($a,$b)=($a<=>$b)*($b<=>$c)<0?($c,shift,$d++):($b,$c)while$c=shift;say$d+1 if$a

Dane wejściowe są dostarczane jako lista liczb oddzielonych spacjami, podawana w czasie wykonywania, np

perl -M5.010 monotonic.pl 1 3 2 -1 6 9 10 2 1 -12
4

(4 to wynik)

Czytelny:

($a,$b)=($a<=>$b)*($b<=>$c)<0
    ?($c,shift,$d++)
    :($b,$c)
  while$c=shift;
say$d+1
  if$a

„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<=>$cto 1, a drugi jest -1 - co się dzieje, gdy tylko ich produkt jest -1. Jeśli którykolwiek $a==$blub $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,$bktó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

C # 6, 297 209 bajtów

using System.Linq;int G(int[] a)=>a.Any()?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()?G(a.Select(x=>-x).ToArray()):G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1:0;

Nie obeznany z wyjaśnieniami

int G(int[] a)=>
    a.Any()
        ?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()   // If a begins by decreasing (including whole a decreasing)...
            ?G(a.Select(x=>-x).ToArray())   // ... Then flip sign to make a begins by increasing
            :G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1   // ... Else skip the increasing part, recursively find the remaining part number, then add 1
        :0;   // Return 0 if a is empty

JavaScript (ES6), 69 bajtów

f=(d,c,b,...a)=>1/b?(d>c)*(b>c)+(d<c)*(b<c)?1+f(b,...a):f(d,b,...a):1

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

Clojure, 97 bajtów

#((reduce(fn[[C i]s](let[S(conj C s)](if(or(apply <= S)(apply >= S))[S i][[s](inc i)])))[[]1]%)1)

reduceśledzi bieżącą podsekwencję i oblicza, ile razy <=i >=warunki zawodzą. Ostatni 1bierze drugi element z wyniku (jest licznikiem i).