24
\$\begingroup\$

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
Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ To clarify, the subsequences must be contiguous, right? \$\endgroup\$ Commented Nov 14, 2016 at 18:48
  • \$\begingroup\$ @Zgarb Yes, they do. \$\endgroup\$ Commented Nov 14, 2016 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\$ Commented Nov 14, 2016 at 18:53
  • \$\begingroup\$ @NathanMerrill: Good point, added one. \$\endgroup\$ Commented Nov 14, 2016 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\$ Commented Nov 15, 2016 at 19:01

9 Answers 9

Reset to default
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.

Improve this answer
\$\endgroup\$
6
  • \$\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\$ Commented Nov 15, 2016 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\$ Commented Nov 15, 2016 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\$ Commented Nov 15, 2016 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\$ Commented Nov 15, 2016 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\$ Commented Nov 15, 2016 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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Save 5 bytes by turning ($&<=>$1)*($1<=>$2)||$1==$2 into ($&<=>$1)*($1<=>$2)>=0 \$\endgroup\$ Commented Nov 15, 2016 at 15:06
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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ d=#2-#&@@#&; also, defining either f or g as the unary operator ± will probably save some bytes. \$\endgroup\$ Commented Nov 15, 2016 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)

Improve this answer
\$\endgroup\$
2
  • \$\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\$ Commented Nov 15, 2016 at 4:57
  • 1
    \$\begingroup\$ I mean, that's what undefined means - the result is irrelevant. \$\endgroup\$ Commented Nov 15, 2016 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

Improve this answer
\$\endgroup\$
1
  • \$\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\$ Commented Nov 15, 2016 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
Improve this answer
\$\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.

Improve this answer
\$\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).

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.