CareerCup

int findnumberofpositions()
{
int count = 0;
for(int i =0 ; i<=199 ;i++)
{
for(int j =0 ; j<=199 ;j++)
{
if(getsumofdigit(i)+getsumofdigit(j) <= 19) // getsumofdigit function returns sum of // digit of input number
count++;
}
}
return count*4;
}

int getsumofdigit (int n)
{
int count-0;
while(n>0)
{
count+= n%10;
n=n/10;
}
}

The question needs some clarifications. There are a few questions I would ask the interviewer. For e.g.
1. What count is required? All combinations of movements or the max path that the monkey can take.

Anyways, I "ASSUMED" that the count of all the possible coordinates is expected.

In that case, the answer to this is "87700".
Algorithm:
For each coordinate that the monkey is on, there are four possible routes that he can take. North (y+1), South (y-1), East (x+1) and West (x-1). Recursion seems to be the solution to take. The catch is the base condition that should be applied.
- If the sum of the coordinates is more than the limit, return.
- If this coordinate has already been visited, return.

Where should we store the coordinates that have been visited. I took the liberty of using a HashSet<string> type to store this. A string, because I wanted to make sure that the coordinate 'key' should be unique (There are other ways to get a unique key, but for the ease, I used a string key of the format "{0}:{1}", this arguments are the x and y value).

The rest is self explanatory. If you want to print-out the coordinates, just add another method to print-out all the values in the hashset.

The code is below.

public class MonkeyCoordinates
{
    private HashSet<string> _accessibleCoordinates;
    private int _limitSum;
    public MonkeyCoordinates(int limitSum)
    {
        _limitSum = limitSum;
        _accessibleCoordinates = new HashSet<string>();
    }
    public int GetAccessibleCoordinateCount()
    {
        _accessibleCoordinates.Clear();
        Coordinate start = new Coordinate(0, 1);
        AccessNorthEastQuadrantCoordinates(start);
        return (_accessibleCoordinates.Count * 4);
    }
    private void AccessNorthEastQuadrantCoordinates(Coordinate current)
    {
        if (current.CoordinateSum > _limitSum) { return; }
        if (!_accessibleCoordinates.Add(current.Key)) { return; }
        // We have two directions to move. North and East.
        AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.East));
        AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.North));
    }
}
internal sealed class Coordinate
{
    private const string KEYFORMAT = "{0}:{1}";
    internal enum Direction{North, South, East, West}
    internal Coordinate(int x, int y)
    {
        XValue = x;
        YValue = y;
        Key = string.Format(KEYFORMAT, x, y);
        CoordinateSum = Sum(x) + Sum(y);
    }
    internal int XValue { get; set; }
    internal int YValue { get; set; }
    internal string Key { get; set; }
    internal int CoordinateSum { get; set; }
    internal Coordinate Move(Direction direction)
    {
        int x = XValue;
        int y = YValue;
        switch (direction)
        {
            case Direction.East:
                x += 1;
                break;
            case Direction.West:
                x -= 1;
                break;
            case Direction.North:
                y += 1;
                break;
            case Direction.South:
            default:
                y -= 1;
                break;
        }
        return new Coordinate(x, y);
    }
    private int Sum(int val)
    {
        val = Math.Abs(val);
        int sum = 0;
        while (val > 0)
        {
            sum += val % 10;
            val = val / 10;
        }
        return sum;
    }
}

On some site I found that the confirmed answer is - 102485 and I followed the logic. Below is the C++ code. However I am only getting 39 as the answer.

#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;
 
    // insert elements using insert function
    my_map.insert(std::pair<int, int>(0, 0));

	int i=0;

   while (true)
   {
	    my_map = obj1.addGoodNeighbours(i, i, my_map);
		
		i=i+1;

		if (i >= int(my_map.size()))
			break;
		else
			continue;
   }
 
    std::cout << "Size of my_map: " << my_map.size() << '\n';

//    my_map.clear();

}

i think the answer is 102486

#include<iostream>
#include<conio.h>
using namespace std;
int a[10000][10000]={0};
int val=0;

bool caldigit(int a,int b)
{
     int sum=0,i=a,j=b;
     if(i<0)
     {
            i*=-1;
            //cout<<"the i is "<<a<<endl;
     }
     if(j<0)
     {
            j*=-1;
            //cout<<"the j is "<<b<<endl;
     }
     
     while(i)
     {
             sum=sum+(i%10);
             i/=10;
     }
     while(j)
     {
             sum=sum+(j%10);
             j/=10;
     }
     if(sum<=19)
     {
               //cout<<"S the value is "<<val<<" i "<<a<<" j "<<b<<" the sum is "<<sum<<endl;
               return true;
     }
     else
     {
         //cout<<"F the value is "<<val<<" i "<<a<<" j "<<b<<endl;
         return false;
     }
}
void move(int i,int j)
{
     
     if(i<4999&&j<4999&&i>=-5000&&j>=-5000)
     {
         //cout<<"the value is "<<val<<endl;
         if((a[i+5000][j+1+5000]==0)&&(caldigit(i,j+1)))
         {
                           val++;
                           a[i+5000][j+1+5000]=1;
                           //cout<<" first the i "<<i<<" j "<<j+1<<endl;
                           move(i,j+1);
                           
         }
         if((a[i+1+5000][j+5000]==0)&&(caldigit(i+1,j)))
         {
                           val++;
                           a[i+1+5000][j+5000]=1;
                           //cout<<" second the i "<<i+1<<" j "<<j<<endl;
                           move(i+1,j);
         }
         if((a[i+5000][j-1+5000]==0)&&(caldigit(i,j-1)))
         {
                           val++;
                           a[i+5000][j-1+5000]=1;
                           //cout<<" third the i "<<i<<" j "<<j-1<<endl;
                           move(i,j-1);
         }
         if((a[i-1+5000][j+5000]==0)&&(caldigit(i-1,j)))
         {
                           val++;
                           a[i-1+5000][j+5000]=1;
                           //cout<<" forth the i "<<i-1<<" j "<<j<<endl;
                           move(i-1,j);
         }
     }
     else
     {
         cout<<" the i "<<i<<" j "<<j<<endl;
     }
        //cout<<" function exit  "<<val<<endl;   
}
int main()
{
    int i=0,j=0;
    move(0,0);
    val++;
    cout<<"the value is "<<val<<endl;
    //for(i=4700;i<5300;i++)
//    {
//                       for(j=4700;j<5300;j++)
//                       {
//                        cout<<""<<a[i][j];                  
//                       }
//                       cout<<""<<endl;
//    }
    getch();
}

102485 is the correct answer.

If you want to see how the monkey goes, have a look at this image:

bit.ly/A7j4oE

This problem can be modified as:
1) Monkey can only walk right or up, one step at a time.
2) For the origin(0,0), count it only once.
3) For all the points on x-axis or y-axis, count them twice.
4) For all other points, count them 4 times.

int arr[1024][1024] = {0};
void AccessibleCoordinates(int x, int y, int &count)
{
if(arr[x][y] == 1) return; //already traversed
else arr[x][y] = 1;

if(SumOfDigits(x)+SumOfDigits(y) > 19) {return;}


if(x==0 && y==0) {count += 1;}
else if(x==0 || y==0) {count += 2;}
else {count += 4;}

AccessibleCoordinates(x+1, y, count);
AccessibleCoordinates(x, y+1, count);
}

Answer is 102485

#include<iostream>
#include<set>
#include<cmath>

using namespace std;

int sumDig(int x) {
x = abs(x);
int sum = 0;
while (x) sum += x % 10, x /= 10;
return sum;
}

bool valid(int x, int y) {
return (sumDig(x) + sumDig(y) <= 19);
}

void travel(int x, int y, set<pair<int, int> >& s) {
for (int i = -1; i < 2; ++i) {
for (int j = -1; j < 2; ++j) {
if (abs(i + j ) == 1) {
int x1 = x + i;
int y1 = y + j;
if (valid(x1, y1) && s.find(make_pair(x1,y1)) == s.end()) {
s.insert(make_pair(x1, y1));
travel(x1, y1, s);
}
}
}
}
}

int main() {
set<pair<int,int> > s;
s.insert(make_pair(0,0));
travel(0,0,s);
cout << s.size();
return 0;
}

Answer is 102485

#include<iostream>
#include<set>
#include<cmath>

using namespace std; 

int sumDig(int x) {
  x = abs(x);
  int sum = 0;
  while (x) sum += x % 10, x /= 10;
  return sum;
}

bool valid(int x, int y) {
return  (sumDig(x) + sumDig(y) <= 19);
}

void travel(int x, int y, set<pair<int, int> >& s) {
  for (int i = -1; i < 2; ++i) {
    for (int j = -1; j < 2; ++j) {
      if (abs(i + j ) == 1) {
        int x1 = x + i;
        int y1 = y + j;
	if (valid(x1, y1) && s.find(make_pair(x1,y1)) == s.end()) {
	  s.insert(make_pair(x1, y1));
	  travel(x1, y1, s);
	}
      }
    }
  }
}

int main() {
  set<pair<int,int> > s;
  s.insert(make_pair(0,0));
  travel(0,0,s);
  cout << s.size();
  return 0;
}

I may be wrong, but I think we can answer this without writing code. I was thinking on these lines. Lets consider monkey is on (0,0) and it can move only in quadrant I ( i.e x and y co-ordinates are all +ve ).
So if monkey is on point(0,0) then lets assume he is just moving to right until it hits maximum at (1927,0) since sum of digits is 19. So for now it has travelled 1928 points. It cannot travel up but has to go 1 left position and then 1 up position to (1926,1). Now on that horizontal line it is free to travel left until it hits point (0,1). For that horizontal line it has travelled 1927 points. Using same iteration it will travel up on Y axis until it hits (0,1927). and every level number of points it travels is one less than below line. If we plot points it will become like equilateral triangle with co-ordinates (0,0) , (0,1927) and (1927,0). Or the total number of points in that triangle are summation of points 1,2,3,..1928. i.e n(n+1)/2 formula gives 1928*1929/2= 1859556.
Similarly we can see its replica for rest of 3 quadrants. so total no of points is 7438224. But while doing for all 4 quads we are duplicating the values on the x and y axis so we need to subtract it. hence total points should be 7438224 - 4(1928) = 7430512.
Hope it makes sense.

import java.util.HashSet;
import java.util.Iterator;


public class MonkeyCoordinates {
	private static String KEYFORMAT = "(%d:%d)";
	private HashSet<String> accessCoords;
	private static int commonCoordsCount=0;
	private int maxSum;
	private enum Direction {
		NORTH, SOUTH, EAST, WEST;
	}
	
	public MonkeyCoordinates(int sum) {
		maxSum = sum;
		accessCoords = new HashSet<String>();
	}
	
	public int getAccessCoordsCount() {
		accessCoords.clear();
		Coordinate start = new Coordinate(0, 0);
		accessNorthEastQuadCoords(start);
		accessCoords.remove(start.key);
		Iterator<String> it = accessCoords.iterator();
		while(it.hasNext()) {
			String common = it.next();
			if (common.startsWith("(0:")) {
				commonCoordsCount++;
			}
			//System.out.println(it.next());
		}
		return (1 + (accessCoords.size() - commonCoordsCount) * 4);
	}
	
	private void accessNorthEastQuadCoords(Coordinate current) {
		if (current.coordSum > maxSum) {
			return;
		}
		if (!accessCoords.add(current.key)) {
			return;
		}	
		accessNorthEastQuadCoords(current.move(Direction.EAST));
		accessNorthEastQuadCoords(current.move(Direction.NORTH));
	}
	
	
	private class Coordinate {
		
		private int xValue, yValue;
		String key;
		public int coordSum;
		public int getxValue() {
			return xValue;
		}
		public void setxValue(int xValue) {
			this.xValue = xValue;
		}
		public int getyValue() {
			return yValue;
		}
		public void setyValue(int yValue) {
			this.yValue = yValue;
		}
		public Coordinate(int x, int y) {
			setxValue(x);
			setyValue(y);
			key = String.format(KEYFORMAT, getxValue(), getyValue());
			coordSum = sum(x) + sum(y);
		}
		Coordinate move(Direction direction) {
			int x = getxValue();
			int y = getyValue();
			switch (direction) {
			case EAST:
				x++;
				break;
			case WEST:
				x--;
				break;
			case NORTH:
				y++;
				break;
			case SOUTH:
			default:
				y--;
				break;
			}
			return new Coordinate(x, y);
		}
		
		private int sum(int val) {
			val = Math.abs(val);
			int sum = 0;
			while (val > 0) {
				sum += val % 10;
				val = val / 10;
			}
			return sum;
		}
	}
	
	public static void main(String[] args) {
		MonkeyCoordinates mon = new MonkeyCoordinates(19);
		System.out.println("Coordinates accessible by Monkey is " + mon.getAccessCoordsCount());
	}
}

None of the even numbered responses can be correct. 4*(the quadrant points) + 1 (0,0) in all quadrants or no quadrant you choose.

Here is complete solution.
comment if you disagree.

//
// File: Monkey_points.cpp
//

/*******prints total number of points monkey can access ***************/
/*******print all the points monkey can access in separate points.txt file ******/

/********************************************************************************/

#include "stdafx.h"
#include <fstream>
#include <iostream>
using namespace std;


int coordinates(int x,int y)
{
int totalcount=0;
ofstream the_file;
the_file.open("points.txt");
for ( int i=(-x); i<x; i++)
{
for ( int j=(-y); j <= y; j++)
{
if ( (i + abs(j) ) <= 19)
{
cout<<i<<" "<<j<<endl;
the_file<<i<<" ";
the_file<<j<<endl;
totalcount++;
}
}

}

for ( int i=(-y); i<=y; i++)
{
for ( int j=(-x); j < y; j++)
{
if ( (i + abs(j) ) <= 19)
{
cout<<j<<" "<<i<<endl;
the_file<<j<<" ";
the_file<<i<<endl;
totalcount++;
}

}

}
the_file.close();
return totalcount;

}


int _tmain(int argc, int argv[])
{
int totalcount=0;
cout<<"Printing Monkey Access points"<<endl;

totalcount = coordinates(19,19);

cout<<"total points monkey can access is "<<totalcount<<endl;
getchar();

return 0;
}


>> Output
total points monkey can access is 2261

program :-

#include<iostream.h>
#include<math.h>

class point
{
public:
int xco;
int yco;

point()
{
xco=0;
yco=0;
}

point(int x,int y) : xco(x) , yco(y)
{

}

bool isaccesible()
{
int lxco=abs(xco);
int lyco=abs(yco);
int sum=0;
while(lxco)
{
sum=sum+(lxco%10);
lxco=lxco/10;
}
while(lyco)
{
sum=sum+(lyco%10);
lyco=lyco/10;
}
if(sum<=19)
return true;
else
return false;
}

point operator + (point& p)
{
int lxco=xco+p.xco;
int lyco=yco+p.yco;
return(point(lxco,lyco));
}

void display ()
{
cout << " xco " << xco << " yco " << yco << endl;
}

bool operator ==(point & p)
{
if(xco==p.xco && yco==p.yco)
return true;
else
return false;
}
};

template <class datatype>
class myqueue
{
public:
int count;
datatype arr_of_datatype[500000];


myqueue<datatype> ()
{
count=0;
}

void pop()
{
if(count<1)
cout << " Queue is empty " << endl;
else
{
//delete(arr_of_datatype[0]);
for(int i=0;i<count-1;i++)
{
arr_of_datatype[i]=arr_of_datatype[i+1];
}
count--;
}
}

void push(datatype myqdt)
{
if(count>499999)
cout << " Queue is full " << endl;
else
{
arr_of_datatype[count]=myqdt;
count++;
}
}

datatype front()
{
if(count>0)
return arr_of_datatype[0];
else
cout << " Queue is empty " << endl;
}

datatype* pfront()
{
if(count>0)
return (&arr_of_datatype[0]);
else
cout << " Queue is empty " << endl;
}


datatype operator [](int k)
{
if(count>0 && k<count)
return arr_of_datatype[k];
else
cout << " Queue is empty " << endl;
}

int size()
{
return count;
}

bool empty()
{
if(count==0)
return true;
else
return false;
}
};

int iisnotadded[1000][1000]={1};

int main()
{
for(int i=0;i<1000;i++)
for(int j=0;j<1000;j++)
iisnotadded[i][j]=1;

int tpop=0,count=0,k,validmoves[]={1,0,-1,0,0,1,0,-1};
myqueue<point> myQ;
point start(0,0);

if(start.isaccesible() )
{
myQ.push(start);
iisnotadded[start.xco+500][start.yco+500]=0;
count++;
}

while(myQ.count!=0)
{
cout << " myQ.count " << myQ.count << " current count " << count << " total pop " << tpop << endl;
for(int j=0;j<4;j++)
{
point temp;
temp=myQ.front() + point(validmoves[2*j],validmoves[(2*j)+1]);
if(iisnotadded[temp.xco+500][temp.yco+500])
{
if(temp.isaccesible() )
{
count++;
myQ.push(temp);
iisnotadded[temp.xco+500][temp.yco+500]=0;
temp.display();
}
}
}
delete(myQ.pfront() );
myQ.pop();
tpop++;
}
cout << " final : COUNT " << count << endl;
}

output :- final : COUNT 102485

public static void main(String[] args) {
        System.out.println(getCount());
    }

    public static int getCount() {
        int count = 0;
        int x = 0, y = 0;
        for (int i = 0; i < 199; i++) {
            for (int j = 0; j < 199; j++) {
                if (sum(i) + sum(j) < 19) {
                    System.out.println(" i :" + i + " j :" + j);
                    count++;
                }
            }
        }
        return count;
    }

    private static int sum(int num) {
        int sum = 0;
        num = Math.abs(num);
        while (num > 0) {
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }

Total Count would be 18670.