Into how many pieces can you cut this string?
Python, 88 75 73 bytes
lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1
Just a straightforward lambda
Just to show another approach:
Pyth, 28 27 bytes
heSmsmq@S+k(d)1dC,QtQm+b.5Q
This one's roughly equivalent to
lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1
applied to the input list from STDIN. Try it on the online interpreter.
Pyth: 31 30 29 28 24 23 character (Python 68 chars)
heSmsm&<hSkdgeSkdC,tQQQ
Try it here: Pyth Compiler/Executor
It expects a list of integers as input
[-1, 3, 1, -2, 5, 2, 3, 4]
It's a straightforward translation of my Python program:
lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)
Old solution: Pyth 28 char
Just for archiving reasons.
heSmsm<*-dhk-dek0C,tQQm+b.5Q
A corresponding Python code would be:
f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])
APL, 16 14 bytes
1+⌈/+/2≠/∘.≤⍨⎕
Thanks to @ngn for saving 2 bytes.
The ⎕
is actually a box character, not a missing-font error. You can try the program at tryapl.org, but since ⎕
is not fully supported there, you have to replace it by the input value:
1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6
Explanation
The program is best explained with the example input s = ¯1 3 1 ¯2 5 2 3 4
, which is taken from STDIN by ⎕
. First, we compute the ≤
-outer product of s
with itself using ∘.≤⍨
. This results in a Boolean matrix whose i
th row tells which elements of s
are less than or equal to s[i]
:
1 1 1 0 1 1 1 1
0 1 0 0 1 0 1 1
0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1
0 0 0 0 1 0 0 1
The occurrences of 0 1
and 1 0
on row i
mark places where the string passes over the point s[i] + 0.5
. We match on these on every row using 2≠/
, "reduce 2-sublists by ≠
":
0 0 1 1 0 0 0
1 1 0 1 1 1 0
1 0 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
1 1 0 1 0 0 0
1 1 0 1 1 1 0
0 0 0 1 1 0 1
What remains is to take the sums of the rows with +/
2 5 3 0 2 3 5 3
and one plus the maximum of these with 1+⌈/
:
6
The result is automatically printed to STDOUT in most APL implementations.