C++

Forum

 
Grid Puzzle

techieZone (1)
Hello All,

I need your help to understand what changes should I make to consider all the points on grid instead to only diagonal points which it is calculating right now. Actual answer for this puzzle is around 102485, but I am only getting 633. :(

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, but not able to make out how should I change it. Please suggest.

Here is the puzzle:

1
2
3
4
5
6
7
8
9
 
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
#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();

}
coder777 (8444)
I'd say that the problem is the map itself.

if you do this

my_map.insert(std::pair<int, int>(x, y+1));

and then

my_map.insert(std::pair<int, int>(x, y-1));

the previous value is overwritten.

with map you cannot have (0, 0) and (0, 1) just the one or the other. Replace map with vector
Topic archived. No new replies allowed.