I need your help once again to understand where I am going wrong. Is it the logic or the implementation.
Actual answer for this puzzle is around 102485, but I am only getting 39. :(
Here is my logic:
- I first start at (0,0) and store is in a map. Then I look for the neighbouring points and check if they are already present in the map. If they do exist in map, then I move ahead, if not then I add it in map. Finally I display the count and the points in map.
But somehow its not considering all the points. I guess some issue with while loop. Please suggest.
Here is the puzzle for C++:
There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?
Input
There is no input for this program.
Output
Print out the how many points can the monkey access. (The number should be printed as an integer whole number eg. if the answer is 10 (its not !!), print out 10, not 10.0 or 10.00 etc)
My C++ code:
#include<stdio.h>
#include <iostream>
#include <map>
#include <utility> // make_pair
#include <string.h>
#include <sstream>
using namespace std;
typedef std::map<int, int> MapType;
class assgnt
{
private:
//MapType my_map;
public:
bool isGoodPoint(int x, int y);
MapType addGoodNeighbours(int x, int y, std::map<int, int> MapType);
bool check_pair(int x, int y, std::map<int, int> MapType);
};
inline bool assgnt::isGoodPoint(int x, int y)
{
string xs, ys;
stringstream xout, yout;
int xsum=0, ysum=0;
xout << abs(x);
yout << abs(y);
xs = xout.str();
ys = yout.str();
for each (char c in xs)
{
xsum = xsum + (c - '0');
}
for each (char c in ys)
{
ysum = ysum + (c - '0');
}
if (xsum+ysum <= 19)
return true;
else
return false;
}
inline bool assgnt::check_pair(int x, int y, MapType my_map)
{
//MapType my_map;
MapType::iterator iter = my_map.begin();
iter = my_map.find(x);
if (iter != my_map.end())
{
int num = iter->second;
if(num == y)
{
//std::cout << "Value is found: " << iter->second << '\n';
return true;
}
else
{
//std::cout << "Value not found: ";
return false;
}
}
/* else
std::cout << "Key is not in my_map" << '\n';*/
return false;
}
inline MapType assgnt::addGoodNeighbours(int x, int y, MapType my_map)
{
//MapType my_map;
if(isGoodPoint(x+1,y))
{
if(!check_pair(x+1, y, my_map))
{
my_map.insert(std::pair<int, int>(x+1, y));
}
}
if(isGoodPoint(x-1,y))
{
if(!check_pair(x-1, y, my_map))
{
my_map.insert(std::pair<int, int>(x-1, y));
}
}
if(isGoodPoint(x, y+1))
{
if(!check_pair(x, y+1, my_map))
{
my_map.insert(std::pair<int, int>(x, y+1));
}
}
if(isGoodPoint(x,y-1))
{
if(!check_pair(x, y-1, my_map))
{
my_map.insert(std::pair<int, int>(x, y-1));
}
}
return my_map;
//std::cout << "Size of my_map: " << my_map.size() << '\n';
}
int main()
{
MapType my_map;
assgnt obj1;
my_map.insert(std::pair<int, int>(0, 0));
int i=0, j=0;
while (i < int(my_map.size()))
{
my_map = obj1.addGoodNeighbours(i, i, my_map);
i=i+1;
}
//for(int i=0; i < int(my_map.size()) ; i++)
//{
// for(int j=0; j < int(my_map.size()) ; j++)
// {
// my_map = obj1.addGoodNeighbours(i, j, my_map);
// }
// //std::cout << "Size of my_map: " << my_map.size() << '\n';
//}
std::cout << "Size of my_map: " << my_map.size() << '\n';
MapType::iterator iter;
for( iter = my_map.begin(); iter != my_map.end(); iter++ ) {
cout << "\n (" << iter->first << ", " << iter->second << ")" << endl;
}
// my_map.clear();
}