23
1
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
To clarify, the subsequences must be contiguous, right? – Zgarb – 2016-11-14T18:48:45.633
@Zgarb Yes, they do. – shooqie – 2016-11-14T18:49:59.670
3I'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
– Nathan Merrill – 2016-11-14T18:53:06.043@NathanMerrill: Good point, added one. – shooqie – 2016-11-14T18:54:50.963
When you write that for an empty string, the result is
0 / undefined
, it sounds like it should be either 0 or the representation ofundefined
in our language, but from your comment on Jonathan Allan's Jelly answer, it looks likeundefined
meansanything
... Which one is it? In the second case, I would suggest writinganything
instead ofundefined
– Dada – 2016-11-15T19:01:37.927@Dada: I'm never good at getting the niceties of challenges right. It's a valid point though, I'll update the description. – shooqie – 2016-11-15T19:30:59.570
@shooqie Ok it's much clearer now. Don't worry, neither am I, so I won't blame you! – Dada – 2016-11-15T19:57:31.397