Najmniejsza liczba ciągłych monotonicznych podsekwencji

23

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
shooqie
źródło
Aby wyjaśnić, podsekwencje muszą być ciągłe, prawda?
Zgarb
@Zgarb Tak, robią.
shooqie
3
Polecam dodanie przypadku testowego, w którym sekwencje nie zawsze idą w odwrotnym kierunku: [4,4,8,8,1,4,5] -> 2
Nathan Merrill
@NathanMerrill: Dobrze, dodałem jeden.
shooqie
Kiedy piszesz, że na pustym ciągiem znaków, wynik jest 0 / undefined, to brzmi jak powinno być 0 lub reprezentacja undefinedw naszym języku, ale z Twojego komentarza na Jonathana Allana Jelly odpowiedzi, wygląda na to undefinedśrodków anything... Który to ? W drugim przypadku sugerowałbym pisanie anythingzamiastundefined
Dada

Odpowiedzi:

6

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.

Fatalizować
źródło
Jaki jest argument „Z” w łączu TIO? (Wygląda na to, że jest częścią programu, tak jak argument linii poleceń).
Jonathan Allan
@JonathanAllan Ten argument jest wynikiem. Idealnie byłoby, gdybyśmy mogli dostosować interfejs TIO, byłoby Wejście i Wyjście i żadnych argumentów. Argument jest taki, Zponieważ Zjest nazwą zmiennej; więc mówimy „wywołaj ten program z wyjściem jako zmienną”. Można zmienić Zna jakikolwiek inny pisania wielkimi literami ; to tylko nazwa zmiennej. Przyczyną tego argumentu jest umożliwienie faktycznego ustawienia wyjścia na coś zamiast zmiennej.
Fatalize
(Na przykład, jeśli ustawisz Wyjście na 4w tym przykładzie, powie ci, czy to jest poprawne, czy nie )
Fatalizuj
1
@JonathanAllan Dowolny język podobny do Prologu jest taki: predykaty mogą tylko odnieść sukces lub porażkę i nie zwracają żadnej wartości. Aby uzyskać wynik, trzeba mieć zmienny argument predykatu, który zostanie zunifikowany do wyniku.
Fatalize
1
@JonathanAllan Ostatecznie się nie powiedzie, 3ponieważ nie znajdzie żadnej listy podlist, w których wszystkie są monotoniczne i długiej 3. 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. Na 5to mówi true, bo jest rzeczywiście co najmniej jeden wykaz długości 5z 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ą.
Fatalize
4

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.

Dada
źródło
Zaoszczędź 5 bajtów, zamieniając się ($&<=>$1)*($1<=>$2)||$1==$2w($&<=>$1)*($1<=>$2)>=0
Gabriel Benamy
@GabrielBenamy Rzeczywiście, dzięki.
Dada,
2

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
Greg Martin
źródło
d=#2-#&@@#&;zdefiniowanie jednego flub jednego goperatora ±prawdopodobnie spowoduje zapisanie niektórych bajtów.
Martin Ender
2

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)

Jonathan Allan
źródło
@shooqie - Czy możemy zwrócić dowolną wartość dla pustej listy z uwagi na „niezdefiniowany” komentarz? Zwraca 1(co wydaje mi się bardziej sensowne niż 0).
Jonathan Allan
1
To znaczy, to undefinedznaczy - wynik nie ma znaczenia.
shooqie,
2

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

Gabriel Benamy
źródło
Nie potrzebujesz odstępu między 1i if(a może robisz to na starych perlach, ale na ostatnich nie.). Również można (prawdopodobnie) zastąpić shiftprzez pop. 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żywaj popzamiast je shiftrozwiązywać, ale twórz nowe ( 1 2 3 4drukuje 3 zamiast 1) ...
Dada
1

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
Link nr
źródło
1

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

Neil
źródło
0

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

NikoNyrh
źródło