Smallest number of contiguous monotonic subsequences

Question

A monotonic subsequence is a sequence of numbers \$a_1, a_2, ..., a_n\$ such that

$$a_1 \le a_2 \le ... \le a_n \\ \text{or} \\ a_1 \ge a_2 \ge ... \ge a_n$$

[1, 3, 3, 7, 9, 13, 13, 100] is a monotonic (non-decreasing) subsequence, as well as [9, 4, 4, 3, 0, -10, -12] (this one is non-increasing), but [1, 3, 6, 9, 8] is not. Given a list of integers (in any reasonable format), output the smallest number N such that the sequence of these integers can be split into N monotonic sequences.

Examples

[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

Answer 1

Brachylog, 12 bytes

~c:{<=|>=}al

Try it online!

This returns false. for the empty list [].

Explanation

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

This will return the smallest one because ~c will generate choice points from the smallest number of sublists to the biggest.

Answer 2

Perl, 65 bytes

62 bytes of code + 3 bytes for -n flag.

monot_seq.pl :

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

Give the input without final newline, with the numbers separated by spaces :

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

-5 bytes thanks to @Gabriel Benamy.

Answer 3

Mathematica, 111 bytes

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]

Named function f taking a nonempty list of numbers (integers or even reals). Works from front to back, discarding the first element repeatedly and keeping track of how many subsequences are needed. More verbose:

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

Answer 4

Jelly, 19 bytes

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

TryItOnline! or run all tests (empty list results in 1)

How?

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

(I'm not convinced that this is the most suitable method to minimise byte count though)

Answer 5

Perl, 98 97 96 79 bytes

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

Input is provided as a list of numbers, separated by spaces, provided at runtime, e.g.

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

(the 4 is the output)

Readable:

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

The 'spaceship operator' <=> returns -1 if LHS < RHS, 0 if LHS = RHS, and +1 if LHS > RHS. When comparing three sequential elements $a,$b,$c to determine if they're monotonic, it's only necessary to determine that it's not the case that exactly one of $a<=>$b,$b<=>$c is 1 and the other is -1 -- which only happens when their product is -1. If either $a==$b or $b==$c, then the sequence is monotonic, and the product is 0. If $a < $b < $c, then both result in -1, and -1 * -1 = 1. If $a > $b > $c, then they both result in 1, and 1 * 1 = 1. In either case, the sequence is monotonic, and we wish to continue.

If the product is less than 0, we know that the sequence is not monotonic, and we discard the values of $a,$b we're currently holding, and increment our subsequence counter. Otherwise, we move forward one number.

Returns nothing if the input is empty, otherwise returns the smallest number of contiguous monotonic subsequences

Answer 6

C#6, 297 209 bytes

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;

Ungolfed with explanations

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

Answer 7

JavaScript (ES6), 69 bytes

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

Takes input as multiple parameters. Works by recursively comparing the first three elements to see whether they are monotonic, if so, removes the middle element as it is useless, if not, removes the first two elements and starts a new sequence.

Answer 8

Clojure, 97 bytes

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

reduce keeps track of the current subsequence and calculates how many times <= and >= conditions fail. Last 1 takes 2nd element from the result (being the counter i).

Answer 9

Jelly, 11 bytes

ŒṖỤ€IṠƑƊƇẈṂ

Try it online!

Empty list yields 1

How it works

ŒṖỤ€IṠƑƊƇẈṂ - Main link. Takes an array A on the left
ŒṖ          - Yield all partitions of A
       ƊƇ   - Keep those partitions for which the following is true:
   €        -   Over each sublist in the partition:
  Ụ         -     Grade up; Sort its indices by its values
    I       -   Increments
      Ƒ     -   Is this invariant under:
     Ṡ      -     Convert to sign

                This (ṠƑ) is a trick that returns 1 if the list contains only
                -1, 1 and 0s. As we're working with the indices, not the values,
                we will never have duplicate elements, and so no 0. The increments
                will either be all 1 or -1 iff the ordered indices are in directly
                ascending or descending order, i.e. the values are sorted in
                either ascending or descending order

         Ẉ  - Get the lengths of each kept partition
          Ṃ - Get the minimum