23
\$\begingroup\$

Challenge description

A monotonic subsequence is a sequence of numbers [a1, a2, ..., an] such that

a1 <= a2 <= ... <= an or a1 >= a2 >= ... >= an. [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
\$\endgroup\$
  • \$\begingroup\$ To clarify, the subsequences must be contiguous, right? \$\endgroup\$ – Zgarb Nov 14 '16 at 18:48
  • \$\begingroup\$ @Zgarb Yes, they do. \$\endgroup\$ – shooqie Nov 14 '16 at 18:49
  • 3
    \$\begingroup\$ I'd recommend adding a test case where the sequences don't always go in the reverse direction: [4,4,8,8,1,4,5] -> 2 \$\endgroup\$ – Nathan Merrill Nov 14 '16 at 18:53
  • \$\begingroup\$ @NathanMerrill: Good point, added one. \$\endgroup\$ – shooqie Nov 14 '16 at 18:54
  • \$\begingroup\$ When you write that for an empty string, the result is 0 / undefined, it sounds like it should be either 0 or the representation of undefined in our language, but from your comment on Jonathan Allan's Jelly answer, it looks like undefined means anything... Which one is it? In the second case, I would suggest writing anything instead of undefined \$\endgroup\$ – Dada Nov 15 '16 at 19:01
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What is the argument "Z" in the TIO link? (It seems to be part of the program like a command line argument would). \$\endgroup\$ – Jonathan Allan Nov 15 '16 at 10:35
  • \$\begingroup\$ @JonathanAllan This argument is the output. Ideally if we could customize TIO's interface, there would be the Input and the Output and no arguments. The argument is Z because Z is a variable name; so we are saying "call this program with the Output as a variable". You can change Z to any other uppercase letter; it's just a variable name. The reason this argument exists is to allow the possibility of actually setting the output to something, instead of a variable. \$\endgroup\$ – Fatalize Nov 15 '16 at 10:39
  • \$\begingroup\$ (For example if you set the Output to 4 in that example, it will tell you if that is correct or not) \$\endgroup\$ – Fatalize Nov 15 '16 at 10:41
  • 1
    \$\begingroup\$ @JonathanAllan Any Prolog like language is like this: predicates can only succeed or fail and do not return any value. So to get an output one has to have a variable argument to the predicate which will get unified to the result. \$\endgroup\$ – Fatalize Nov 15 '16 at 10:49
  • 1
    \$\begingroup\$ @JonathanAllan It will eventually fail for 3 because it wont find any list of sublists where all are monotonic and of length 3. It just takes a long time because it will try all possible lists of sublists, even those that are actually longer than 3 elements because the length is checked after finding the list. For 5 it says true because there is indeed at least one list of length 5 with monotonic sublists that works. So this program returns the smallest length when the output is a variable and whether there is any list of that length that works if the output is an integer. \$\endgroup\$ – Fatalize Nov 15 '16 at 10:53
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Save 5 bytes by turning ($&<=>$1)*($1<=>$2)||$1==$2 into ($&<=>$1)*($1<=>$2)>=0 \$\endgroup\$ – Gabriel Benamy Nov 15 '16 at 15:06
  • \$\begingroup\$ @GabrielBenamy Indeed, thanks. \$\endgroup\$ – Dada Nov 15 '16 at 16:13
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ d=#2-#&@@#&; also, defining either f or g as the unary operator ± will probably save some bytes. \$\endgroup\$ – Martin Ender Nov 15 '16 at 7:54
2
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ @shooqie - May we return any value for the empty list given the "undefined" comment? This returns 1 (which I actually think makes more sense than 0). \$\endgroup\$ – Jonathan Allan Nov 15 '16 at 4:57
  • 1
    \$\begingroup\$ I mean, that's what undefined means - the result is irrelevant. \$\endgroup\$ – shooqie Nov 15 '16 at 10:34
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You don't need a space between 1 and if (or maybe you do on old perls, but on recent ones you don't). Also you can (probably) replace shift by pop. However, there are some test cases on which your code doesn't work : 6 3 6 3 (you print 3 instead of 2), 4 3 2 1 (you print 2 instead of 1). Using pop instead of shift solve those but create new ones (1 2 3 4 prints 3 instead of 1)... \$\endgroup\$ – Dada Nov 15 '16 at 18:40
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.