Quartermeter Path

This is a standard dynamic programming problem .

Notice that:

• None of the points outside the circle are reachable.
• There are only is only one way to reach any of the points on the bottom row.
• For any point, you could approach it either from the bottom or the left. So, the number of ways we can reach a given point is the sum of the ways we can reach a point below and to the left of it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

inside = lambda x,y: (x-10)**2 + y**2 <= 100

dp = [[0 for i in xrange(11)] for i in xrange(11)]

for x in xrange(0,11):
    dp[0][x] = 1

for y in xrange(1,11):
    for x in xrange(0,11):
        if not inside(x,y):
            dp[y][x] = 0
        else:
            dp[y][x] = dp[y-1][x] + dp[y][x-1]

print dp[10][10]

Gives 46960

My solution in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int R = 10;
int NPath[][] = new int[R+1][R+1];

for (int x = 0; x <= R; x++) for (int y = 0; x+y <= R; y++)
    if (x == 0 && y == 0) NPath[x][y] = 1;
    else if ((10-x)*(10-x) + y*y > R*R) NPath[x][y] = 0;
    else NPath[x][y] = (x>0 ? NPath[x-1][y] : 0) + (y>0 ? NPath[x][y-1] : 0); 

int N = 0;
for (int x = 0; x <= R; x++) N += NPath[x][R-x] * NPath[x][R-x];
System.out.println(N);

Output:

1

46960

I saved on computation time by calculating the number of paths only for $(x, y)$ with $x+y \leq R$ .

After all, every path from (0,0) to (10,10) will pass through precisely one point on the diagonal $x + y = R$ ; because of symmetry, the number of paths from (0,0) to this point and from this point to (10,10) is the same. Thus the number of paths from (0,0) to $(x,y)$ to (10,10) is equal to the square of this number.

For a small problem like this there is no need for such tricks, and one could go with the boring solution:

1
2
3
4
5
6
7
8
9

int R = 10;
int NPath[][] = new int[R+1][R+1];

for (int x = 0; x <= R; x++) for (int y = 0; y <= R; y++)
    if (x == 0 && y == 0) NPath[x][y] = 1;
    else if ((10-x)*(10-x) + y*y > R*R) NPath[x][y] = 0;
    else NPath[x][y] = (x>0 ? NPath[x-1][y] : 0) + (y>0 ? NPath[x][y-1] : 0); 

System.out.println(NPath[R][R]);

But what fun is that?

Solution in python 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

"Quartermeter Path"

anm_ = {(10, 10):1}

def isin(n, m):
    return n <= 10 and m >=0  and (n -10)*(n -10) + m*m <= 100

def anm(n , m):
    if (n, m) not in anm_:
        anm_[(n, m)] = sum(anm(x, y) for (x,y) in [(n+1, m), (n, m+1)] if isin(x,y))
    return anm_[(n, m)]

print(anm(0,0))

Its a simple enough algorithm where we can solve by recursion, in incremental steps, where in each step he can move to (x+1,y) or (x, y+1). The added constraint is that the distance from point C to any allowed grid point(x,y) is less than equal to 10 units.

I have posted a solution for this in C#.

For those who are familiar with Action and delegate pattern in C# the solution is below. The Move Action-delegate could be written a separate function otherwise too.

        void PointAToBCircular()
        {
            Action<int, int> Move = null;
            int xMax = 10, yMax = 10, xmaxSq = xMax * xMax;
            int NPaths = 0;
            Move = delegate (int x, int y)
            {
                if (x > xMax) return;
                if (y > yMax) return;

                int dSquared = (xMax - x) * (xMax - x) + (y * y);
                if (dSquared > xmaxSq) return;

                if (x == xMax && y == yMax)
                {
                    NPaths ++;
                    return;
                }
                Move(x + 1, y);
                Move(x, y + 1);
            };
            Move(0, 0);

            Console.WriteLine("Number of ways : {0}", NPaths);
        }