Question: There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant 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 x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?

Answer:

If we look at the question carefully ant can move only in the increasing fashion of x and y. Because if it tries to reduce initial x or y (1000,1000) in both cases the sum of digits will become more than 25. e.g 1000-1=999(9+9+9=27).

So ant can only increase x and y and it can not decrease x and y (1000,1000). the will be only in the positive area of x and y coordinates. In this manner if we increase X coordinate with Y fixed at 1000. we will see that ant can move up to (1698,1000). Now we can follow a staircase pattern from here by decreasing X by 1 and increasing Y by 1. But then we will get a loop hole at (1689, 1009). So we need to set y as 1000 again at X = 1689. Following the staircase pattern, same problem will happen again at (1599, 1090), so we need to set Y as 1000 again at X = 1599. The final graph will be as given below.

Total number of points will be:

600*601/2 + 2*90*91/2 + 2*9*10/2 = 188580**Subscribe** - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

## Ant's travel in a grid

under:
Brain Teasers

## I write about

- Algorithm (31)
- Amazon EC2 (3)
- Amazon Interview (9)
- Amazon S3 (5)
- Amazon SimpleDB (5)
- Amazon SQS (1)
- Architecture (3)
- Arrays/Strings (32)
- backtracking (1)
- Brain Teasers (8)
- C++ (3)
- Cloud Computing (14)
- Design Pattern (2)
- Dynamic programming (11)
- Facebook Interview (3)
- General (14)
- Git (2)
- Google Interview (6)
- Humour (1)
- Interviews (7)
- Link List (8)
- Mac (2)
- Mathematics (3)
- MIcrosoft Interview (4)
- Miscellany (1)
- python (3)
- queue (1)
- Ruby (9)
- tree (19)
- web development (1)

ColleenI don't think these are exact triangles, as you assume. For example, at point (1680, 1009), if we followed a staircase pattern, the next move would be (1679, 1009), which is invalid. This change would throw off the formula for the area of a triangle.

Akash@Colleen: Can you please elaborate, I actually didn't get you. It will be great if you can send me a diagram.

LiNkI think 220,500 is the correct answer. See code below.

Thoughts?

----------------------------------

$y = 1698;

$x = 1000;

$points;

while($y >= 1000 && $x <= 1698){

$ysum = array_sum(str_split($y));

$xsum = array_sum(str_split($x));

if(($ysum + $xsum) > 25){

}else{

$points = $points + ((1698 - $y) + 1);

}

$y--;

$x++;

}

echo "Total accessible Points: " . $points;

Manish SharmaHey Akash,

Your solution is wrong.

If you take 1001 as Y coordinate then your ant can't move beyond 1598 along X axis.

I hope I am making sense to you. :)