How many peaks in my mountain range?

A list of positive integers can be visualized as a quantized mountain range where each list entry represents the height of one vertical section of the mountains.

For example, the list

1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3

can become the range

x
x x
xxxxx   xxx   x
xxxxxxxx xxxxxx x
xxxxxxxxxxxxxxxxxx

(Less poetic people might call this a bar chart, but I digress.)

The question in this challenge is: How many peaks are in the mountain range of some arbitrary list? Essentially, how many local maxima are in the list?

A peak is defined as a contiguous section of one or more columns of the mountain range that are all equal in height, where the columns immediately to the left and the right are lower in height.

It's easy to visually tell that the example has four peaks at these parenthesized locations:

1, 2, 2, 3, (4), 3, (5), 3, 2, 1, 2, (3, 3, 3), 2, 2, 1, (3)

Note how the (3, 3, 3) plateau section counts as a peak because it is a contiguous set of columns equal in height, higher than its neighboring columns.

The last (3) counts as a peak as well because, for the purposes of this challenge, we'll define the left neighbor of the leftmost column and the right neighbor of the rightmost column to both be height zero.

This means that a list with only one value, for example 1, 1, 1, can be interpreted as 0, 1, 1, 1, 0, and thus has one peak, not none: 0, (1, 1, 1), 0.

The only list with zero peaks is the empty list.

Challenge

Write a function or program that takes in an arbitrary list of positive integers and prints or returns the number of peaks in the corresponding mountain range.

The shortest code in bytes wins. Tiebreaker is earlier post.

Test Cases

Input List -> Output Peak Count
[empty list] -> 0
1, 1, 1 -> 1
1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3 -> 4
1 -> 1
1, 1 -> 1
2, 2, 2, 2, 2 -> 1
90 -> 1
2, 1, 2 -> 2
5, 2, 5, 2, 5 -> 3
2, 5, 2, 5, 2, 5, 2 -> 3
1, 2, 3, 4 -> 1
1, 2, 3, 4, 1, 2 -> 2
1, 3, 5, 3, 1 -> 1
7, 4, 2, 1, 2, 3, 7 -> 2
7, 4, 2, 1, 2, 1, 2, 3, 7 -> 3
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 -> 10
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1 -> 10
2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 -> 10
1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 3, 1 -> 4
12, 1, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 1, 5, 5, 4, 7, 9 -> 6
87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 909 -> 3
87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 908, 909 -> 4
• So, the plateau can be arbitrary long? Jan 9 '16 at 8:04
• @nicael Yes, it could be Jan 9 '16 at 8:05
• Can we take input as an array, not as string? Jan 9 '16 at 8:26
• @nicael Yes, anything reasonable Jan 9 '16 at 8:28

CJam (32 26 24 21 bytes)

0q~0]e1f=2ew::>2,/,(

Expected input is space-separated numbers.

Online demo ; full test suite (expected output is a 1 per test case).

Thanks to Martin for informing me that the current version of CJam improves one of the operators used, saving 2 chars; and for a further 3-char saving.

Dissection

Two phases: deduplicate, then identify local maxima in each set of three.

0q~0]      e# Put the input in an array wrapped in [0 ... 0]
e1f=      e# Use run-length encoding to deduplicate
2ew::>     e# Map [a b c ...] to [(a>b) (b>c) ...]
2,/        e# Split on [0 1], which since we've deduplicated occurs when (a<b) (b>c)
,(         e# Count the parts and decrement to give the number of [0 1]s

JavaScript (ES6), 54 51 bytes

m=>m.map(n=>{h=n<p?h&&!++r:n>p||h;p=n},r=h=p=0)|r+h

Explanation

Takes an array of numbers

m=>
m.map(n=>{       // for each number n in the mountain range
h=
n<p?       // if the number is less than the previous number:
h&&      // if the previous number was greater than the number before it
!++r     // increment the number of peaks and set h to 0
:n>p||h;   // if the number is greater than the previous number, set h to 1
p=n          // set p to the current number
},
r=             // r = number of peaks
h=             // h = 1 if the previous number was higher than the one before it
p=0            // p = previous number
)|r+h            // return the output (+ 1 if the last number was higher)

Test

var solution = m=>m.map(n=>{h=n<p?h&&!++r:n>p||h;p=n},r=h=p=0)|r+h
Mountain Range (space-separated) = <input type="text" id="input" value="87 356 37673 3676 386 909 909 909 909 454 909 908 909" />
<button onclick="result.textContent=solution(input.value.split(' ').map(n=>+n))">Go</button>
<pre id="result"></pre>

Pyth, 25 23 bytes

L._M-M.:b2s<R0y-y+Z+QZZ

Explanation:

L              y = lambda b:
._M -M .:          signs of subsets
b          of b
2          of length 2. That is, signs of differences.

s <R              number of elements less than
0              0 in
y -            y of ... with zeroes removed
y +          y of
Z        the input with zeroes tacked on both sides
+ Q Z
Z
• Nice. Unusually, a port to CJam is shorter: 0q~0]{2ew::-:g0-}2*1-, for 22. Jan 9 '16 at 20:50

Julia, 66

x->(y=diff([0;x;0]);y=y[y.!=0];sum((y[1:end-1].>0)&(y[2:end].<0)))

Ignore the plateaus: y=y[y.!=0].
Count + to - zero crossings: sum((y[1:end-1].>0)&(y[2:end].<0)).

MATLAB, 29 27 bytes

@(a)nnz(findpeaks([0 a 0]))

Anonymous function which finds the peaks in the data and counts how many there are. 0 is prepended and appended to the data to ensure peaks at the very edges are detected as per the question.

This will also work with Octave. You can try online here. Simply paste the above code into the command line, and then run it with ans([1,2,1,3,4,5,6,1]) (or whatever other input).

As the numbers are always +ve, we can assume they are greater than zero, so can save 2 bytes by using nnz instead of numel.

Python 3, 75 bytes

def m(t):
a=p=d=0
for n in t+[0]:a+=(n<p)&d;d=((n==p)&d)+(n>p);p=n
return a

This is my first codegolf so there may be some places to cut down on it, especially the d=((n==p)&d)+(n>p) part. However it works on all the test cases

• Are those not 78 bytes? Sep 20 '17 at 9:50

Mathematica, 423633 32 bytes

Thanks to Martin Büttner for saving 1 byte.

Tr@PeakDetect[#&@@@Split@#,0,0]&

PeakDetect just does almost everything!

Test cases:

Total@PeakDetect[#&@@@Split@#,0,0]&@{12,1,2,1,2,3,3,3,2,4,4,4,1,5,5,4,7,9}
(* 6 *)
Total@PeakDetect[#&@@@Split@#,0,0]&@{87,356,37673,3676,386,909,909,909,909,454,909,908,909}
(* 4 *)
• I find my answer to be sufficiently different from yours to post another one. Jan 9 '16 at 12:25
• @LegionMammal978 The result of input {1} is 1, as is expected. Jan 9 '16 at 12:41
• I mean {1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3} Jan 9 '16 at 12:42
• @LegionMammal978 That's tricky. I've not find a solution. Jan 9 '16 at 12:54
• My updated solution just flattens "plateaus". Jan 9 '16 at 12:55

CJam, 27 26 bytes

A0q~0A]e1f=3ew{~@e>>}%1e=

Uses the run length coding to remove duplicates. After that we check for every triplet if the middle one is the largest number.

Pyth, 18 bytes

su_>VGtG2eMr++ZQZ8

Based on @PeterTaylor's repeated greater than solution, but with a twist.

++ZQZ: Add zeros on both sides.

eMr ... 8: Remove repeats.

u ... 2 ...: Apply the following twice:

>VGTG: Map each pair of numbers to whether they are in decreasing order.

_: And reverse.

A 1 in the output corresponds to a 1, 0 in prior step, which corresponds to a < b > c in the input due to the reversal.

s: Sum (and print)

MATL, 22 bytes

0ih0hdZS49+c'21*?0'XXn

Uses current version of the language/compiler.

Example

>> matl
> 0ih0hdZS49+c'21*?0'XXn
>
> [1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3]
4

Explanation

0ih0h           % input array. Append and prepend 0
dZS             % sign of difference between consecutive elements. Gives -1, 0, 1
49+c            % convert to a string of '0','1','2'
'21*?0'XX       % use (lazy) regular expression to detect peaks: '20' or '210' or '2110'...
n               % number of matches. Implicity print

Mathematica, 553936 35 bytes

Length@FindPeaks[#&@@@Split@#,0,0]&

Now works on all of the test cases!

• Cool! But FindPeaks[#,0,0,-∞] is needed, otherwise it fails for the last test case. Jan 9 '16 at 12:30
• Last/@ saves a byte. And the last ",0" might be unnecessary? Jan 9 '16 at 13:14
• Same trick for you: Last/@ --> #&@@@ Jan 12 '16 at 10:34

Retina, 33 31 bytes

Thanks to Neil for saving 2 bytes.

\b(1+)(?<!\1,\1)(,\1)*\b(?!,\1)

Try it online!

Takes input as a comma-separated, unary list.

• \b(1+)(?<!\1 \1)( \1)*\b(?! \1) seems to save 2 bytes?
– Neil
Sep 20 '17 at 8:59
• @Neil of course, thanks! :) Sep 20 '17 at 9:12

JavaScript ES6, 96 94 bytes

t=>(a=t.filter((x,i)=>x!=t[i-1])).filter((x,i)=>(x>(b=a[i-1])||!b)&&(x>(c=a[i+1])||!c)).length

Principle: collapse plateaus into single peaks, find the picks which are defined as being higher than both next and previous elements.

Takes input as an array.

Demo:

f=t=>
(a=t.filter((x,i)=>x!=t[i-1]))    //collapse every plateau into the pick
.filter((x,i)=>
(x>(b=a[i-1])||!b)&&(x>(c=a[i+1])||!c)    //leave only those values which are greater than the succeeding and preceding ones
).length

document.write(
f([])+"<br>"+
f([1, 1, 1])+"<br>"+
f([1, 2, 2, 3, 4, 3, 5, 3, 2, 1, 2, 3, 3, 3, 2, 2, 1, 3])+"<br>"+
f([1])+"<br>"+
f([1, 1])+"<br>"+
f([2, 2, 2, 2, 2])+"<br>"+
f([90])+"<br>"+
f([2, 1, 2])+"<br>"+
f([5, 2, 5, 2, 5])+"<br>"+
f([2, 5, 2, 5, 2, 5, 2])+"<br>"+
f([1, 2, 3, 4])+"<br>"+
f([1, 2, 3, 4, 1, 2])+"<br>"+
f([1, 3, 5, 3, 1])+"<br>"+
f([7, 4, 2, 1, 2, 3, 7])+"<br>"+
f([7, 4, 2, 1, 2, 1, 2, 3, 7])+"<br>"+
f([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])+"<br>"+
f([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1])+"<br>"+
f([2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])+"<br>"+
f([1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 3, 1])+"<br>"+
f([12, 1, 2, 1, 2, 3, 3, 3, 2, 4, 4, 4, 1, 5, 5, 4, 7, 9])+"<br>"+
f([87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 909])+"<br>"+
f([87, 356, 37673, 3676, 386, 909, 909, 909, 909, 454, 909, 908, 909])
)

ES6, 50 48 bytes

m=>m.map(h=>{f=h>p?c+=!f:f&&h==p;p=h},p=c=f=0)|c

Saved 2 bytes thanks to @user81655.

Ungolfed:

function peaks(mountains) {
var previous = 0;
var count = 0;
var plateau = false;
for (var height of mountains) {
if (height > previous) {
if (!plateau) count++;
plateau = true;
} else if (height != previous) {
plateau = false;
}
}
return count;
}
• @user81655 Thanks for drawing my attention to that subtlety. (I've not used .map()| before.)
– Neil
Jan 9 '16 at 18:04

MATL, 23

Since we need to use stack based esolangs to be competitive, I reimplemented my Julia solution in MATL.

0i0hhdtg)t5L)0>w6L)0<*s

Push 0, input, 0, concatenate twice. 0i0hh => x = [0, input(''), 0]

Differentiate. d => x = diff(x)

Duplicate t, convert one to boolean and use it to index the other. tg) => x=x(x!=0)

Duplicate again. t

First: [1,G])0> => y1 = x(1:end-1)>0

Exchange. w

Second: [2,0])0< => y2 = x(2:end)<0

Logic and, count the truthy values. *s => sum(y1 & y2)

• Or you could you Pyth, a procedural/functional golfing language! Jan 9 '16 at 18:58
• OK, MATL is MATLAB for golfing, but MATLAB is beating MATL. Jan 9 '16 at 19:10
• Very nice! Some tips: [1,G] --> 5L saves 3 bytes. [2,0] --> 6L saves 3 bytes Jan 10 '16 at 4:54
• @GenericUser Not anymore :-) codegolf.stackexchange.com/a/69050/36398 Jan 10 '16 at 5:08
• @Rainer I'm thinking of removing and (&) from MATL (and same for or). It can always be replaced by *o, and often by just *, as in this case. What do you think? That way the characters & and | could be used for other functions in the future. Jan 10 '16 at 13:10

Japt, 19 bytes

That was easier than I thought, but the beginning is slightly wasteful due to a bug.

Uu0;Up0 ä< ä> f_} l

Try it online!

How it works

Uu0;Up0 ä< ä> f_} l  // Implicit: U = input
Uu0;Up0              // Add 0 to the beginning and end of U. If this isn't done, the algorithm fails on peaks at the end.
ä<           // Compare each pair of items, returning true if the first is less than the second, false otherwise.
// This leaves us with a list e.g. [true, false, false, true, false].
ä>        // Repeat the above process, but with greater-than instead of less-than.
// JS compares true as greater than false, so this returns a list filled with false, with true wherever there is a peak.
f_} l  // Filter out the falsy items and return the length.

Non-competing version, 15 bytes

Uu0 p0 ä< ä> è_

Earlier today, I added the è function, which is like f but returns the number of matches rather than the matches themselves. I also fixed a bug where Array.u would return the length of the array rather than the array itself.

Try it online!

05AB1E, 9 bytes

Ô0.ø¥0‹ÔO

Try it online!

Explanation:

Ô0.ø¥0‹ÔO      Full program
Ô              Uniquify (= remove plateaus)
0.ø           Surround with zeros
¥          Push deltas
0‹        Test each element if lower than 0
--- we now have a list with 0's (= going uphill) and
1's (going downhill). Since we removed plateaus, all
we have to do now is to count the number of ramps
going downhill
Ô       Uniquify (reduce ramps to length 1)
O      Total sum of the list

Jelly, 27 bytes

ṡ2EÐḟFs2ḣ€1S€ṡ3M€Fċ2
0;⁸;0Ç

Try it online!

• Jelly without TIO??? lol Sep 20 '17 at 2:02
• This was a long time ago, before I knew how to link to TIO. I'll leave it like this for posterity. Sep 20 '17 at 11:04
• Screw dat I fix Sep 21 '17 at 2:07
• >_<_>_<_>_<_>_< Sep 22 '17 at 2:35

Japt, 14 bytes

iT òÎmÎä> ò> l

Try it (includes all test cases)

Accommodating the empty array cost 2 bytes.

iT òÎmÎä> ò> l     :Implicit input of array
iT                 :Prepend 0
ò               :Partition between elements where
Î              :  The sign of their difference is truthy (not 0)
m             :Map
Î            :  First element
ä>          :Consecutive pairs reduced by >
ò>       :Partition after elements that are greater than the next
l     :Length

Husk, 11 bytes

#←gẊo±>m←gΘ

Try it online!

#←gẊo±>m←gΘ
#               # how many truthy elements in list of
←              # first element of each sublist of
g             # grouped identical elements of
Ẋ            # apply to each pair in list
o±>         # sign of greater than (1 if greater than, 0 otherwise)
m←       # make list from first element of each sublist of
g      # grouped identical elements of
Θ     # input prepended with zero
• Ah, yes, The mountain range sequence. Oct 29 '20 at 17:14

GolfScript, 35

~0+0\{.@=!},+:a,2-,{a\>3<.\$2=?1=},,

Test online

Basically removes duplicates, adds a 0 to both ends, and checks how many triples have a maximum in the center.

Java 8, 141 bytes

Can probably be golfed by using a different approach, or an array as input instead of List.

Explanation:

Try it here.

l->{                     // Method with ArrayList<Integer> parameter and int return-type
int r=0,               //  Result-integer
i=1,               //  Index-integer
t;                 //  Temp integer
i<l.size()-1;      //  Loop (1) from index 1 through length-1 (0-indexed)
r+=                //    After every iteration, raise the result-integer by:
t>l.get(i-1)    //     If the current item is larger than the previous
&t>l.get(++i)?  //     and larger than the next:
1              //      Increase r by 1
:               //     Else:
0)             //      r` remains the same
for(;(t=l.get(i))==l.get(i+1);
//   Inner loop (2) as long as there are two adjacent equal items
l.remove(i)        //    And remove one of those two equal integers
);                   //   End of inner loop (2)
//  End of loop (1) (implicit / single-line body)
return r;              //  Return the result-integer
}                        // End of method

Python 3, 68 bytes

f=lambda a,*b,p=0:(p<a>[*b,0][0])+(len(b)and f(*b,p=[p,a][a!=b[0]]))

Try it online!