Peaks and Valleys in 2d Array

[bmw5545]

I have to do a project where a file with 60 rows and 17 columns is stored in an array. The purpose of the project is to find all the "peaks" and "valleys". A peak is considered a number that has a higher value than all 8 of its neighbors, while a valley is a number that has a lower value than all 8 of its neighbors. Here is an example where peaks are bolded and valleys are underlined.

25 58 63 23 21 34 21 50
32 45 43 40 41 32 30 27
34 40 38 39 36 28 30 35
40 45 42 48 32 34 29 32
39 39 40 42 47 49 27 30
31 31 31 32 32 33 44 35


I'm having trouble coming up with the code that will find values that are higher/lower than all 8 of their neighbors. Any suggestions?

[MiiNiPaa]

Why is top-right corner is not a peak and top left is not a valley?

[JLBorges]

> Why is top-right corner is not a peak and top left is not a valley?

Because they don't have eight neighbours: "than all 8 of its neighbours".


> I'm having trouble coming up with the code that will find values that are higher/lower than all 8 of their neighbors.
> Any suggestions?

Count the number of neighbours with lower/higher values?

#include <iostream>
#include <type_traits>

template < std::size_t ROWS, std::size_t COLS > // invariant: ROWS > 2, COLS > 2
std::pair<int,int> counts( const int (&array)[ROWS][COLS], std::size_t row, std::size_t col ) // invariant row in [2...ROWS-2],
{
    // invariant row in [1...ROWS-2], col in [1...COLS-2]
    int cnt_high = 0 ;
    int cnt_low = 0 ;

    for( int i : { -1, 0, 1 } ) for( int j : { -1, 0, 1 } )
    {
        cnt_high += array[row+i][col+j] > array[row][col] ;
        cnt_low += array[row+i][col+j] < array[row][col] ;
    }

    return { cnt_high, cnt_low } ;
}

template < std::size_t ROWS, std::size_t COLS >
void peaks_and_valleys( const int (&array)[ROWS][COLS] )
{
    for( std::size_t row = 1 ; row < (ROWS-1) ; ++row )
        for( std::size_t col = 1 ; col < (COLS-1) ; ++col )
        {
            const auto cnts = counts( array, row, col ) ;
            if( cnts.first == 8 ) // cnt_high
                std::cout << "valley " << array[row][col] << " at " << row << "," << col << '\n' ;
            else if( cnts.second == 8 ) // cnt_low
                std::cout << "peak   " << array[row][col] << " at " << row << "," << col << '\n' ;
        }
}

int main()
{
    const int a[][8] =
    {
        { 25, 58, 63, 23, 21, 34, 21, 50 },
        { 32, 45, 43, 40, 41, 32, 30, 27 },
        { 34, 40, 38, 39, 36, 28, 30, 35 },
        { 40, 45, 42, 48, 32, 34, 29, 32 },
        { 39, 39, 40, 42, 47, 49, 27, 30 },
        { 31, 31, 31, 32, 32, 33, 44, 35 }
    };
    peaks_and_valleys(a) ;
}

http://coliru.stacked-crooked.com/a/e1820900e0ab9442

[newbieCPlusPlus1]

How would you write this without using the type traits library or standards?

[JLBorges]

#include <stdio.h>

typedef struct pair pair ;
struct pair { int high ; int low ; } ;

pair make_pair( int a, int b ) { pair p = { a, b } ; return p ; }

#define ROWS 6
#define COLS 8

pair counts( const int array[ROWS][COLS], int row, int col )
{
    // invariant row in [1...ROWS-2], col in [1...COLS-2]
    int cnt_high = 0 ;
    int cnt_low = 0 ;

    for( int i = -1 ; i < 2 ; ++i ) for( int j = -1 ; j < 2 ; ++j )
    {
        cnt_high += array[row+i][col+j] > array[row][col] ? 1 : 0 ;
        cnt_low += array[row+i][col+j] < array[row][col] ? 1 : 0 ;
    }

    return make_pair( cnt_high, cnt_low ) ;
}

void peaks_and_valleys( const int array[ROWS][COLS] )
{
    for( int row = 1 ; row < (ROWS-1) ; ++row )
        for( int col = 1 ; col < (COLS-1) ; ++col )
        {
            const pair cnts = counts( array, row, col ) ;
            if( cnts.high == 8 )
                printf( "valley %d at %u,%u\n", array[row][col], row , col ) ;
            else if( cnts.low == 8 )
                printf( "valley %d at %u,%u\n", array[row][col], row , col ) ;
        }
}

int main()
{
    const int a[ROWS][COLS] =
    {
        { 25, 58, 63, 23, 21, 34, 21, 50 },
        { 32, 45, 43, 40, 41, 32, 30, 27 },
        { 34, 40, 38, 39, 36, 28, 30, 35 },
        { 40, 45, 42, 48, 32, 34, 29, 32 },
        { 39, 39, 40, 42, 47, 49, 27, 30 },
        { 31, 31, 31, 32, 32, 33, 44, 35 }
    };
    peaks_and_valleys(a) ;
}

http://coliru.stacked-crooked.com/a/5839171d1a7d02f0