Grid | Diabolical or Smart

The problem 91 of Project Euler was a bit tricky. It requires one to find the number of right angled triangles in a n X n grid, with one point $(0,0)$ fixed. For example, as shown on the problem page, a 3 X 3 grid contains 14 triangles. The problem required the answer for a 51 X 51 grid.

Well, at first I started with a pencil-paper approach. I listed down all the cases I could think of and checked my calculation for the 3 X 3 grid. Got the answer right. But applied the same to the larger 51 X 51 grid I realized that there were cases I had not enumerated all the cases. I am still not sure if the problem can be solved using just a pencil and a paper.

I did not want to do a brute force way of picking up two arbitrary points and checking if they form a right angled triangle. In my solution I have never tried to determine the actual triangles. As you shall see, all I do is to find the number of possible triangles by using a parameter and bounding it within an interval. The range of the interval is my solution for that particular point.

I went the mathematics way. One of the points is fixed at $(0,0)$ . Select one point as $(a,b)$ . The slope of the line joining these two points is $\frac{b}{a}$ . So the equation of a line perpendicular to this one and passing through the point $(a,b)$ would be :

$y = -\frac{a}{b}(x - a) + b$

Now points which lie on the above line will all form right angled triangles with the points $(0,0)$ and $(a,b)$ . The following conditions need to be satisfied in our particular problem:

The solutions to the above equation are integers.
The points lie within a grid of n X n. So $0 \leq x \leq n$ and $0 \leq y \leq n$ .

There are two cases we need to consider. One where $a$ is a multiple of $b$ and the other where it is not.

Let us first consider the case where $a$ is not a multiple of $b$ . We rewrite the equation as follows:

$y = -\frac{c}{d}(x - fc) + fd$

where $f$ is the gcd of $a$ and $b$ . Now since $y$ is an integer, we can impose the following condition on $x$ :

$x = fc + kd$

where k is some parameter, in which case the value of $y$ becomes:

$y = fd - kc$

And now imposing the second criteria, we can limit the values of the parameter $k$ as thus:

$0 \leq x \leq n$

$\Rightarrow -\frac{fc}{d} \leq k \leq \frac{n - fc}{d}$

Similarly, imposing the same conditions for $y$ , we get

$\frac{fd - n}{c} \leq k \leq \frac{fd}{c}$

The intersection of the two intervals gives us the eligible values for the parameter $k$ as :

$max ( -\frac{fc}{d}, \frac{fd - n}{c} ) \leq k \leq min ( \frac{n - fc}{d}, \frac{fd}{c} )$

For $k = 0$ we get the point $(a,b)$ . For all other values of $k$ we get the points which complete the right angled triangle. So the number of right angled triangles in this case will be the range of k – 1.

Now the other case. Let $a = pb$ . The equation then becomes :

$y = -p (x - a) + b$

Let $q = x - a$ . Then we have

$y = -pq + b$

Once again the applying the boundary conditions we get:

$\frac{b - n}{p} \leq q \leq \frac{b}{p}$

$-a \leq q \leq n - a$

Once again taking the intersection of the intervals gives us:

$max ( \frac{b - n}{p}, -a ) \leq q \leq min ( \frac{b}{p}, n - a )$

Add to this the trivial case of $3n^{2}$ right angled triangles formed when one of the points lie on the axis. It is easy to see these if you sit with a pencil and a paper.

I went ahead to code the above conditions. The code is given below. On my laptop I was able to run this code for a grid of 4000 X 4000 in 1 second.

In the code given below, I have used $(xIdx, yIdx)$ as the point $(a,b)$ . $f$ and $p$ are as described above.

    public int getCount(int n) {
        int count = 0;

        for (int xIdx = 1; xIdx <= n; xIdx++)
            for (int yIdx = xIdx; yIdx <= n; yIdx++) {
                int tempCount = xIdx % yIdx == 0 ? countForXMultipleOfY(xIdx, yIdx, n) : countForXNotMultipleOfY(xIdx,
                        yIdx, n);
                count += xIdx != yIdx ? 2 * tempCount : tempCount;
            }

        return (int) (count + 3 * Math.pow(n, 2));
    }

    private int countForXMultipleOfY(int xIdx, int yIdx, int n) {
        int p = xIdx / yIdx;

        int lowerBoundary = NumberUtil.larger((yIdx - n) / p, xIdx * -1);
        int upperBoundary = NumberUtil.smaller(yIdx / p, n - xIdx);

        return upperBoundary > lowerBoundary ? upperBoundary - lowerBoundary : 0;
    }

    private int countForXNotMultipleOfY(int xIdx, int yIdx, int n) {
        int f = MathUtils.gcd(yIdx, xIdx);

        int lowerLimit = NumberUtil.larger(-1 * xIdx / (yIdx / f), (yIdx - n) / (xIdx / f));
        int upperLimit = NumberUtil.smaller(yIdx / (xIdx / f), (n - xIdx) / (yIdx / f));

        return upperLimit > lowerLimit ? upperLimit - lowerLimit : 0;
    }

Popularity: 15% [?]

I have gone in a very round about way, and my explanation might not be clear. Apparently, this is a very standard combinatorics problem and can be answered at sight. Well, I did not know that, and did a few things which made me realize the combinatorial answer.

The latest problem that I solved was is Problem 15. Given a grid of 20 x 20 squares, the question asked was to find the number of routes from the top left hand corner of the grid to the bottom rightmost corner without ever backtracking.

This was an easy one too. I started out by writing at every meeting point of lines, the number of extra lines that spring out of the point. For example, at the starting point 2 lines start. Select for example the horizontal one. At the first point that it comes across, it forks into 2 lines, which is 1 extra. So I wrote 1 at this point. The same is done at all points except those on the rightmost vertical and the bottommost horizontal which contains the total number of lines passing through it.

Below is a diagram showing the same thing.