I was wondering if there is a programmatic way to determine if an array has the pattern of a perfect mountain, without valleys. (Example in the image)
Edit:
My attempt in C:
#include<stdio.h>
int AscOrDes(int a[], int first, int last)
{
int i;
for(i=first; i<last; i )
{
if(a[i]>a[i 1])
return(1);
else if(a[i]<a[i 1])
return(2);
}
return 0;
}
int main() {
int a[1000],n,i,big=0,r1,r2;
scanf("%d",&n);
for(i=0; i<n; i )
{
scanf("%d",&a[i]);
}
for(i=0; i<n; i )
{
if(a[i]>=a[big])
big=i;
}
r1=AscOrDes(a, 0, big);
r2=AscOrDes(a, big, n);
if(r1==2 && r2==1 && big!=0 && big!=n-1)
printf("True");
else
printf("False");
return 0;
}
The above code doesn't work for the following inputs:
8
1 3 2 5 4 3 2 0
It gives the output:
True
Even though it isn't a perfect mountain array.
What I have done in my program is check which element is the largest (big), and checked if the elements on the left side of the largest element are in ascending order and those on the right side are in descending order (how the mountain should be).
CodePudding user response：
Your AscOrDes function is not working properly: it will always exit at the first iteration:
int AscOrDes(int a[], int first, int last)
{
int i;
printf("Check array from %d to %d\n", first, last);
for(i=first; i<last; i )
{
if(a[i]>a[i 1]) {
printf("a[%d]=%d > a[%d]=%d, so return 1\n", i, a[i], i 1, a[i 1]);
return(1);
}
else if(a[i]<a[i 1]) {
printf("a[%d]=%d < a[%d]=%d, so return 1\n", i, a[i], i 1, a[i 1]);
return(2);
}
}
return 0;
}
However, I think you can probably evaluate the array more efficiently, something like this --
int state = 0; // 0 = waiting for increase, 1 = incr, 2 = decr
for (i = 1; i < n; i ) {
if (a[i-1] == a[i]) {
// Equality is an immediate failure.
printf("False\n"); exit(0);
}
if (a[i-1] < a[i]) {
// We found an increase. This is valid in states 0 or 1.
if (2 == state) {
printf("False\n"); exit(0);
}
state = 1;
} else {
// Found a decrease. This is valid in state 1 or 2.
if (0 == state) {
printf("False\n"); exit(0);
}
state = 2;
}
}
// At the end, we must be in state 2 (decrease after an increase).
if (2 != state) {
printf("False\n"); exit(0);
}
printf("True\n");
CodePudding user response：
Will try this way:
def is_moutain(A):
i = 1
N = len(A)
while i < N and A[i] > A[i-1]: # go on if ascending, and more items existing
i = 1
if i == 1 or i == N:
return False
while N > i and A[i] < A[i-1]: # at the descending point...
i = 1
return i == N
if __name__ == '__main__':
print(is_moutain([0, 2, 3, 4, 5, 3, 1])) # True
print(is_moutain([0, 2, 3, 4, 5, 2, 4])) # False
CodePudding user response：
Here is how I would do it in Python:
array = [3, 4, 5, 6, 9, 10, 11, 19, 6, 3, 2]
def is_strict_mountain(arr: list):
maxim = 0
prev = 0
max_reached = False
for element in array:
if element > maxim:
maxim = element
if element <= prev:
max_reached = True
if element >= prev and max_reached:
return False
prev = element
return True
print(is_strict_mountain(array))
Here is how I would do it in C:
#include <stdio.h>
#define MIN_INT -2147483648
typedef enum {
false, true
} bool;
bool is_strict_mtn(const int *array, int numElements) {
if (array == NULL) {
return false;
}
int max = MIN_INT;
int prev = MIN_INT;
bool max_reached = false;
int count = 0;
while (count < numElements) {
if (*array > max) {
max = *array;
}
if (*array <= prev) {
max_reached = true;
}
if (*array >= prev && max_reached) {
return false;
}
prev = *array ;
}
return true;
}
int main() {
int arr[] = {5, 6, 7, 9, 12, 67, 56, 44, 23, 11, 5, 3, 1};
if (is_strict_mtn(arr, 13)) {
printf("The array is a mountain.\n");
return 0;
}
printf("The array is not a mountain.\n");
return 0;
}
CodePudding user response：
Here's a Python solution using itertools.groupby:
import itertools
def is_mountain(arr):
return [u for u, _ in itertools.groupby(
(b - a for a, b in zip(arr, arr[1:])), # slope as difference
lambda v: v // abs(v) if v else v # slope as unit vector
)] == [1, -1] # strictly increasing, then decreasing
print(is_mountain([0, 2, 3, 4, 5, 2, 1, 0])) # True
print(is_mountain([0, 2, 3, 3, 5, 2, 1, 0])) # False
Given the sample input:
[0, 2, 3, 3, 5, 2, 1, 0]
the first generator (b - a for a, b in zip(...)) subtracts each pair of adjacent elements to produce a sequence of the changes in elevation (the individual slopes):
[2, 1, 0, 2, -3, -1, -1]
The v // abs(v) lambda expression that's used as the key argument to itertools.groupby normalizes those by dividing each by its magnitude, producing a sequence of unit vectors (1 for increasing, -1 for decreasing):
[1, 1, 0, 1, -1, -1, -1]
itertools.groupby combines identical adjacent elements, producing:
[1, 0, 1, -1]
We can then simply define a "mountain" as a list for which going through the above process results in the exact result [1, -1] (all increases followed by all decreases).
CodePudding user response：
you need keep tracking of increments and decrements I used array named delta if there is increment assign delta[i]=1 if there is decrement assign delta[i]=-1 count 1 s if they equal to last-1 then this part has increments count -1 s if they equal to last-1 then this part has increments
#include<stdio.h>
int delta[1000];
int AscOrDes (int a[], int first, int last)
{
int r = 0;
int i;
int c = 0;
for (i = first; i <= last && (i 1) <= last; i )
{
if((a[i 1] - a[i]) > 0){
delta[i]=1;
}
else{
delta[i]=-1;
}
}
for (i = first; i <= last && (i 1) <= last; i )
{
if (delta[i] > 0)
{
c ;
}
else if (delta[i] < 0)
{
c--;
}
}
if (c >= (last - first))
return 1;
if (c*-1 >= (last - first))
return 2;
return 0;
}
int main ()
{
int a[1000], n, i, big = 0, r1, r2;
scanf ("%d", &n);
for (i = 0; i < n; i )
{
scanf ("%d", &a[i]);
}
for (i = 0; i < n; i )
{
if (a[i] >= a[big])
big = i;
}
r1 = AscOrDes (a, 0, big);
r2 = AscOrDes (a, big, n - 1);
if (r1 == 1 && r2 == 2 && big != 0 && big != n - 1)
printf ("True");
else
printf ("False");
return 0;
}