RightAngledTriangle | 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% [?]

Tag Archive for 'rightAngledTriangle'

Project Euler : Counting The Number Of Right Triangles In A Grid

Amazon Deals!

Popular Posts