peak finder

[SECMoG1T]

Hello, av got a question a friend of mine gave me to solve, where you've a map represented as a two dimension array with random integer values, the goal is to locate any peak within the map using recursion.

A peak is any value within the map that is greater than all it's neighbours in the {-x,-y,+x and +y} directions

av got it working but today i wrote yet another code to debug a stack overflow exemption that i got for the first time , i noted that am getting some unnecessary recursive calls where the same coordinates {x,y} are evaluated on multiple instances, am not sure you got that clearly but when you run this code you'll be requested to view the recursion log , from the log you will understand my concerns fully " the log is well documented",

1. handle the overflow

2. my current aim is to slice down the extra recursive call to a maximum of limit=array size {limit*limit} but the logic i applied lately didn't work out so i threw it away.

3. i would also like to have evaluated coordinates in the map in case there is no peak present by the time {limit*limit} recursions are reached so that i can issue a message that no peak was found.

please give me some pointers on what i need to change to achieve my aims or at-least the solve the first one.


the current map contains only one peak "90" , you can also add your peaks randomly it will work fine, when you change this current peak to 9 which still qualifies as a peak , a stack overflow exemption will be thrown but av used some code to take care of that, if you get lucky for the peak '9' to be located you'll realize that some coordinates have been evaluated for about hundred or so times.

see below
or open this link
http://pastebin.com/tVEtTVv7

Thanks in advance,
Andy.

[mutexe]

please give me some pointers

1. if you want to represent a 2-dimensional array then use a 2 dimensional array. not sure why you'd want to use a map to complicate things.
2. Hard to tell without any code but i'm guessing a recursive function is not needed. Just keep a track of the maximum value so far encountered.

[SECMoG1T]

main.cpp

#include <iostream>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <cassert>

#define NDEBUG
//#undef NDEBUG

///array limit
constexpr std::size_t limit=25;

template<std::size_t N,std::size_t M>
void print_peak_finder(int(&)[N][M]);

/********************for MAP objects*******************************/
struct MyMap
{
  int Map[limit][limit]
    {
     {4,4,4,2,5,2,2,2,7,6,6,9,9,2,2,2,9,7,7,7,6,4,2,2,5},
     {6,4,2,2,5,4,2,5,7,5,6,6,5,4,4,4,9,5,6,6,7,9,2,2,6},
     {7,9,2,2,6,6,0,5,4,5,3,3,0,0,7,6,2,5,0,3,6,7,3,2,3},
     {0,9,1,4,1,7,0,2,0,4,0,3,3,8,7,6,2,7,9,9,4,3,1,3,1},
     {1,8,1,6,3,9,0,0,0,8,0,0,0,9,0,0,5,4,5,0,3,3,3,3,2},
     {0,6,0,7,5,9,0,3,1,9,7,1,0,9,9,0,6,0,5,0,4,3,1,3,1},
     {7,7,1,9,3,7,1,3,1,9,0,1,4,4,9,3,6,1,0,0,4,3,3,7,0},
     {9,9,0,9,9,3,3,8,5,8,6,5,0,7,8,4,9,6,4,0,7,0,1,7,4},
     {7,0,1,7,4,0,4,8,0,8,1,6,0,1,0,6,9,1,2,0,7,9,0,7,3},
     {7,0,0,9,3,7,7,9,1,2,3,8,9,1,2,5,7,0,2,9,4,4,0,5,0},
     {3,7,0,9,0,8,0,9,0,3,1,7,9,0,3,6,0,1,2,6,5,8,4,6,0},
     {6,7,3,4,3,8,2,7,1,6,0,7,8,2,3,7,1,0,3,6,1,8,1,6,9},
     {5,8,4,6,0,3,3,0,7,9,0,0,0,7,0,8,0,1,0,5,9,9,0,9,9},
     {7,9,6,7,1,3,5,2,6,9,6,1,3,9,8,8,0,3,0,5,7,7,1,9,3},
     {7,9,0,7,0,0,7,0,0,1,8,0,0,9,4,0,5,6,0,0,7,0,0,9,3},
     {7,2,4,8,1,1,8,3,6,0,8,8,6,9,4,0,2,7,3,5,0,7,1,4,4},
     {0,3,3,9,0,3,9,0,7,1,4,0,6,2,1,1,1,8,3,7,3,7,0,9,0},
     {3,3,3,9,2,2,9,3,7,9,7,2,7,0,9,6,7,8,3,7,7,0,0,9,3},
     {4,4,0,5,0,5,0,2,6,9,3,2,8,7,9,6,3,4,3,7,4,4,4,2,3},
     {4,3,1,3,1,5,0,3,3,2,2,2,8,7,4,2,5,5,3,3,7,2,4,8,3},
     {7,7,0,7,0,0,7,0,0,1,8,0,0,9,4,0,5,6,0,0,7,0,0,90,3},
     {7,2,4,8,1,1,8,3,6,0,8,8,6,9,4,0,2,7,3,5,0,9,1,4,1},
     {0,3,3,9,0,3,9,0,7,1,4,0,6,2,1,1,1,8,3,7,3,7,0,9,0},
     {3,3,3,9,2,2,9,3,7,9,7,2,7,0,9,6,7,8,3,7,7,0,0,9,3},
     {4,4,0,5,0,5,0,2,6,9,3,2,8,7,9,6,3,4,3,7,4,4,4,2,5},
    };
};

class peak_finder
{
    template<std::size_t N,std::size_t M>
    friend void print_peak_finder(int(&)[N][M]);
  private:
    MyMap peakMap;
    std::map<std::pair<std::size_t,std::size_t>,std::size_t> coord_data;  /*******for DEBUG*******/
    void print_coord_track() const;                                       /*******for DEBUG*******/
    std::size_t recursive_call_stacks=0;                                  /*******for DEBUG*******/

    std::size_t Xindex=rand()%limit,Yindex=rand()%limit;
    std::size_t locate_next_XCORD() const;
    std::size_t locate_next_YCORD() const;
    std::pair<std::size_t,std::size_t> next_indices();
    bool peak_found() const;
  public:
    void locate_peak();
};

int main()
{
   srand(time(nullptr));

   peak_finder peak;
   peak.locate_peak();
}

/**scan horizontally across the current row and locate the*
 **largest value , return the x- coord of the value       */
std::size_t peak_finder::locate_next_XCORD() const
{
   std::size_t x=0,value=peakMap.Map[0][Yindex];
     for(std::size_t loc=0;loc<limit;loc++)
     {
        if(value<peakMap.Map[loc][Yindex])
         {value=peakMap.Map[loc][Yindex]; x=loc;}
     }

     if(x==Xindex){x=rand()%(limit);}

     return x;
}

/**the value returned from above is immediately set as the current*
 **X coord i.e the member Xindex, this object have new coordinates*
 **on the current position scan vertically(y-direction) and locate*
 **the largest value and return its y coordinate                  */
std::size_t peak_finder::locate_next_YCORD() const
{
   std::size_t y=0,value=peakMap.Map[Xindex][0];
   for(std::size_t loc=0;loc<limit;loc++)
   {
       if(value<peakMap.Map[Xindex][loc])
       {value=peakMap.Map[Xindex][loc]; y=loc;}
   }

   if(y==Yindex){y=rand()%(limit);}
   return y;
}

/**wrapper for the above functions returns a pair of new {x,y}*
 **coordinates */
std::pair<std::size_t,std::size_t> peak_finder::next_indices()
{
   auto x=locate_next_XCORD(); Xindex=x;
   auto y=locate_next_YCORD();
   return {x,y};
}

/**checks if this object current coordinates {Xindex,Yindex} are a true peak*/
bool peak_finder::peak_found() const
{
   std::size_t value=peakMap.Map[Xindex][Yindex];

   ///check if all four neighbour{+X,+Y,-X,-Y: directions} values are less than current co-ordinate values on the map
   if((Xindex>0&&Yindex>0)&&(Xindex<(limit-1)&&Yindex<(limit-1)))
   {
     if(value>peakMap.Map[Xindex][Yindex-1]&&value>peakMap.Map[Xindex][Yindex+1]&&value>peakMap.Map[Xindex-1][Yindex]&&value>peakMap.Map[Xindex+1][Yindex])
        return true;
     else
        return false;
   }

   ///check for three neighbours on the left edge
   else if(Xindex==0&&Yindex>0&&Yindex<(limit-1))
   {
      if(value>peakMap.Map[Xindex+1][Yindex]&&value>peakMap.Map[Xindex][Yindex-1]&&value>peakMap.Map[Xindex][Yindex+1])
        return true;
      else
        return false;
   }

   ///check for three neighbours on the right edge
   else if(Xindex==(limit-1)&&Yindex>0&&Yindex<(limit-1))
   {
      if(value>peakMap.Map[Xindex-1][Yindex]&&value>peakMap.Map[Xindex][Yindex-1]&&value>peakMap.Map[Xindex][Yindex+1])
        return true;
      else
        return false;
   }

   ///check for three neighbours on the top edge
   else if(Yindex==0&&Xindex>0&&Xindex<(limit-1))
   {
      if(value>peakMap.Map[Xindex-1][Yindex]&&value>peakMap.Map[Xindex+1][Yindex]&&value>peakMap.Map[Xindex][Yindex+1])
        return true;
      else return false;
   }

    ///check for three neighbours on the bottom edge
   else if(Yindex==(limit-1)&&Xindex>0&&Xindex<(limit-1))
   {
       if(value>peakMap.Map[Xindex-1][Yindex]&&value>peakMap.Map[Xindex+1][Yindex]&&value>peakMap.Map[Xindex][Yindex-1])
        return true;
       else return false;
   }

   ///check for two neighbours at the top left corner
   else if(Xindex==0&&Yindex==0)
   {
      if(value>peakMap.Map[Xindex+1][Yindex]&&value>peakMap.Map[Xindex][Yindex+1])
        return true;
      else
        return false;
   }

    ///check for two neighbours at the bottom left corner
   else if(Xindex==0&&Yindex==(limit-1))
   {
      if(value>peakMap.Map[Xindex+1][Yindex]&&value>peakMap.Map[Xindex][Yindex-1])
        return true;
      else
        return false;
   }

    ///check for two neighbours at the top right corner
   else if(Xindex==(limit-1)&&Yindex==0)
   {
       if(value>peakMap.Map[Xindex-1][Yindex]&&value>peakMap.Map[Xindex][Yindex+1])
        return true;
       else
        return false;
   }

    ///check for two neighbours at the bottom right corner
   else if(Xindex==(limit-1)&&Yindex==(limit-1))
   {
       if(value>peakMap.Map[Xindex][Yindex-1]&&value>peakMap.Map[Xindex-1][Yindex])
        return true;
       else return false;
   }

}

[keskiverto]

Why recursion?

[SECMoG1T]

continuation.... main.cpp

/**Public recursive function*/
void peak_finder::locate_peak()
{
  if(recursive_call_stacks>7200)
    {std::cout<<"FAILED MAXIMUM STACK LIMIT REACHED\nEXITED TO AVOID STACK OVERFLOW\n";}

  else if(peak_found())
  {
     print_peak_finder(peakMap.Map);
     std::cout<<"\n\nPeak Found on location MAP["<<Yindex<<"]["<<Xindex<<"]   :   Value = "<<peakMap.Map[Xindex][Yindex]<<std::endl<<std::endl;

     /*******************************************NDEBUG************************************************/
     #ifdef NDEBUG
     char c;
     std::cout<<"\n\n\n\tDo you want to view your coordinates log {Y/N} :"; std::cin.get(c); c=toupper(c);
     if(c=='Y')
       print_coord_track();
     #endif // NDEBUG
     /*******************************************NDEBUG************************************************/
  }

  else
  {
      /*******************************************NDEBUG-collect debug data*****************************/
      #ifdef NDEBUG
      if(coord_data.find({Yindex,Xindex})==coord_data.end())
        coord_data.insert({{Yindex,Xindex},1});
      else
        ++((coord_data.find({Yindex,Xindex}))->second);
      #endif // NDEBUG
      /*******************************************NDEBUG************************************************/

      auto newcord=next_indices();
      Xindex=newcord.first;
      Yindex=newcord.second;
      ++recursive_call_stacks;

      locate_peak();
  }
}

/*******************************************NDEBUG************************************************/
#ifdef NDEBUG
void peak_finder::print_coord_track() const
{
    std::size_t no_of_checks=0;
    std::cout<<"\n\t X coord \t Y coord \t No of checks done\n\n"; std::ios::left;
    for(const auto& curr_pair : coord_data)
    {
        auto cord=curr_pair.first;
        std::cout<<std::setw(13)<<cord.first<<std::setw(17)<<cord.second<<std::setw(20)<<curr_pair.second<<std::endl;
        no_of_checks+=curr_pair.second;
    }
     std::cout<<"\t  "<<std::string(44,'=')<<std::endl;
     std::cout<<std::setw(49)<<"Total checks:   "<<no_of_checks<<std::endl;

}
#endif // NDEBUG
/********************************************NDEBUG***********************************************/


/**print map*/
template<std::size_t N,std::size_t M>
void print_peak_finder(int(&ar)[N][M])
{
   int y=0;
   std::cout<<"\n\n\n\n  X ";
   for(int x=0;x<limit;x++)
    ((x<10)? std::cout<<x<<"  ":std::cout<<x<<" ");

   std::cout<<"\n Y  "<<std::string(74,'-')<<std::endl;
   //std::cout<<"Y";
   for(const auto& frstD : ar)
   {   std::cout<<std::setw(2)<<y++<<"| ";
       for(const auto& secndD : frstD)
       {
           if(secndD<10)
            std::cout<<secndD<<" ";
           else
            std::cout<<secndD;
            std::cout<<" ";
       }
       std::cout<<std::endl;
   }
   std::cout<<"\n\n";
}

[mutexe]

Why recursion?

my point as well.

also. have you compiled that code you posted..? :

std::cout<" \n\n\nFailed check\n";///debug

[SECMoG1T]

@mutexe @keskiverto , my pal told me recursion would be the rule of the game hehe,

have you compiled that code you posted..? :

yea but note that the code is posted in two sections you should join them before you compile or you can follow the link to get the whole paste, the reason i did that is because last time i gave a link to a paste nobody bothered check the paste.

also std::cout<" \n\n\nFailed check\n";///debug
i used this to check if something totally impossible "according to the function logic" would occur, the truth is that, the fuction control would never get to that point in real sense.

[mutexe]

But that line would cause the whole program to not compile.. Doesn't matter if the code path reaches it or not..

[JLBorges]

Brute force: http://www.cplusplus.com/forum/general/148294/#msg777548
("than all 8 of its neighbours"; modify appropriately for "than all of its neighbours".)

[SECMoG1T]

whole program to not compile.. i just don't know why it would fail , my compiler have all available flags and warnings turned on, i did recompile but found no error nor a warning, VS 13 failed because of the in class inti of the struct MAP array, but i would appreciate if you would also tell me why that would fail.

However i removed that section because it doesn't make any sense anyway hehe, thanks.

[SECMoG1T]

Thanks @JLBorges you got quite an interesting loop wow
for( int i = -1 ; i < 2 ; ++i ) for( int j = -1 ; j < 2 ; ++j ) is it the same as

 for( int i = -1 ; i < 2 ; ++i ){
 for( int j = -1 ; j < 2 ; ++j )
/////
}

?

how would i make sure that i dont get out of range if my current coordinates are on my map edges?

I would do away with my peak_found(); function, thanks.

[keskiverto]

my pal told me recursion would be the rule of the game

Ok. Could you explain the logic of the recursion that you use?

[JLBorges]

> for( int i = -1 ; i < 2 ; ++i ) for( int j = -1 ; j < 2 ; ++j )
> is it the same as

> for( int i = -1 ; i < 2 ; ++i ){
>        for( int j = -1 ; j < 2 ; ++j )
> }

Yes.

> how would i make sure that i dont get out of range if my current coordinates are on my map edges?

The function knows the number of rows and cols; const int (&array)[ROWS][COLS]
So the invariant for array[row][col] is: row in [0,ROWS) && col in [0,COLS)

[SECMoG1T]

Could you explain the logic of the recursion that you use? @keskiverto
this is how my recursion works

1. on creation the peakfinder object coordinates Xindex and Yindex will be initialized with
random values.
2. on each call the value of these coordinates {Xindex and Yindex} from the map is checked
to find if it is a peak by the function peak_found() which returns true if
the value is a peak i.e. larger that its 4 neighbours in x and y direction

 i'll change it later to larger than 8 

else false, if true the recursion ends
a print of the map is availed the value of the peak and it's location on the map,

3. If the function returned false before the next recursive call is made , the program changes
it's coordinates {Xindex and Yindex} to a different value that must be within the limits
of the map:- according to my logic the program will

i. first of all scan across the current row i.e
x-AXIS to find if there is any value that is larger than the current
value by calling locate_next_XCORD() which returns the x
coordinate of that value only, if the value returned is the same as Xindex
meaning that all values are less than the current value, the program changes
the current value by assigning it a random number before returning it

i did that because if a row had only on large value then it's x-coord will 
              always be returned and the program will always be caught up on that returning 
              that x infinitely     

ii.. The value returned is immediately used to change the
current value of the Xindex, Then another function
locate_next_YCORD() is called that will scan the current y-AXIS
{verticaly} to find a larger value than the current value if non is found then i
return a random value to avoid the previous, however returning a random value
from this function can be done away with.

iii.. Both functions are wrapped within another function next_indices()
that calls them and returns a pair of nu {x,y} coordinates, that are assigned to
Xindex and Yindex;

Then the function locate_peak() is called recursively.

[SECMoG1T]

Thanks @JLBorges for the insight, well i'll try fix mine with that .

[SECMoG1T]

What about this pals? What do i need to do?

aim is to slice down the extra recursive call to a maximum of limit=array size {limit*limit}

And this too..

 i would also like to have evaluated coordinates in the map in case there is no peak present 
by the time {limit*limit} recursions are reached so that i can issue a message that no peak 
was found.