Skip to content
August 18, 2011 / oop123

Project Euler #91 – Java

You can see the problem here: Problem #91.

This problem is pretty easy.

right triangle with both coordinates at the sidetransformation of the first trianglesecond transformation of first triangle

As you can see from the first pictures, if both coordinates are located at the sides of the grid, we can make a right triangle. That right triangle can also be transformed into two other right triangles, as seen from the remaining two triangles. Since there 50 * 50 = 2500 ways to choose those two coordinates, we already know there are at least 2500 * 3 = 7500 right triangles. Now we just need to figure out a way to find the rest of the triangles.

Let’s say we want to find a right triangle with coordinate P = (1, 2). If we draw a line starting from the origin O to P, the line will have a slope of 2. Then if we draw a line with a slope -1/2, the negative reciprocal of 2, it will be perpendicular to OP. Since the other coordinate Q needs to contain integers, we will find Q by moving P 2 blocks to the right and 1 block down (using slope = -1/2 and definition of slope). See the pictures below for a more visual explanation. The red line has a slope of 2 (1 block right, 2 blocks up) and the blue line has a slope of -1/2 (2 blocks right, 1 block down).
a right triangle with coordinate (1, 2) and (3, 1)
The above right triangle can also be reflected along the line y = x to make another right triangle.
right triangle with coordinates (2, 1) and (1, 3), a y = x reflection of above image
Also, we can extend PQ another 2 blocks to the right and 1 block down and make a different right triangle.
right triangle with coordinates (1, 2) and (5, 0)
There is one last thing to note about. Let’s say the P coordinate is (2, 4), the negative reciprocal of its slope would be -2/4. We need to simplify -2/4 to -1/2 before we can use it in the algorithm, or else we can miss some right triangles. Taken all the above points into account, here is the code (surprisingly short for a Project Euler problems):

final int SIZE = 50;
int answer = SIZE * SIZE * 3;

for (int x = 1; x <= SIZE; x++) {
	for (int y = 1; y <= SIZE; y++) {
		int gcf = EulerMath.GCF(x, y); //bunch of small utility methods I kept in EulerMath
		int dx = x / gcf;
		int dy = y / gcf;
		answer += Math.min(y / dx, (SIZE - x) / dy) * 2;
	}
}

System.out.println(answer);

Runs in ~3 milliseconds on my computer. Note that the problem can also be easily brute force due to its small size, oh well. CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: