<< problem 90 - Cube digit pairs | Square digit chains - problem 92 >> |

# Problem 91: Right triangles with integer coordinates

(see projecteuler.net/problem=91)

The points P(x1,y1) and Q(x2,y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form a triangle \triangle OPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive;

that is, 0 <= x1, y1, x2, y2 <= 2.

Given that 0 <= x1, y1, x2, y2 <= 50, how many right triangles can be formed?

# Algorithm

The location of O was fixed at (0,0) but P and Q can be anywhere (but O!=P!=Q).

To simplify my algorithm I define that the right angle is always at O or P and never at Q.

The size of the grid is 50x50, each side has length size=50.

I identified 4 cases:

1. The right angle is at the origin O. P and Q can be anywhere on the x-/y-axis:

P(0<p_x<=size, 0) and Q(0, 0<q_y<=size) → that's size^2 different triangles.

2. The right angle is on the x-axis at P(0<p_x<=size, 0). Any Q with the same x-value makes a valid triangle:

P(0<p_x<=size, 0) and Q(p_x, 0<q_y<=size) → that's size^2 different triangles.

3. The right angle is on the y-axis at P(0, 0<p_y<=size). Any Q with the same y-value makes a valid triangle:

P(0, 0<p_y<=size) and Q(0<q_x<=size, p_y) → that's size^2 different triangles.

4. The right angle is "inside" the grid at P(0<p_x<=size, 0<p_y<=size).

The fourth case is a more challenging case and will be discussed in detail:

The right angle is enclosed by two vectors \vec{a} = \vec{PO} and \vec{b} = \vec{PQ}.

If they are perpendicular \vec{a} \bot \vec{b}, then their dot product is zero: \vec{a} \cdotp \vec{b} = a_{x}b_x + a_{y}b_y = 0

The task is to find for a given point P(p_x, p_y) each Q(q_x, q_y) such that p_x(q_x - p_x) + p_y(q_y - p_y) = 0.

For example P(2,2) and Q(3,1) create a valid right angle:

p_x(q_x - p_x) + p_y(q_y - p_y) = 2(3-2) + 2(1-2) = 2 - 2 = 0

The dot product can be transformed to

p_x(q_x - p_x) = -p_y(q_y - p_y)

This formula is obivously true for q_x = p_x and q_y = p_y.

Even more, it's also true for q_x = p_x + k \cdot p_y and q_y = p_y - k \cdot p_x (last line was just the special case k=0).

p_x(p_x + k p_y - p_x) = -p_y(p_y - k p_x - p_y)

p_x(k p_y) = -p_y(-k p_x)

kp_{x}p_y = kp_{x}p_y

Two nested `for`

-loops produce all integer combinations of 0 < p_x <= size and 0 < p_y <= size.

We only want integer solutions for q_x and q_y, too.

But if k is an integer, too, then we would miss some valid Q - e.g. for P(2,2) and Q(3,1) it follows that k=frac{1}{2}.

We get all integer solutions if k is a multiple of dfrac{1}{gcd(p_x,p_y)} (the Greatest Common Divisor, see en.wikipedia.org/wiki/Greatest_common_divisor)

For P(2,2) we get dfrac{1}{gcd(2,2)}=dfrac{1}{2}

Enough mathematics, let's dive into the code ... cases 1 to 3 don't need much of an explanation.

Then follows two nested `for`

-loop that analyze each P(p_x,p_y) of case 4.

`factor`

is the `gcd(p_x,p_y)`

such that k_{n+1} = k_n + 1/factor

The point Q is found by repeated adding `p_y/factor`

to `p_x`

and subtracting `p_x/factor`

from `p_y`

(for k > 0)

until any coordinate leaves the grid. The same procedure is done with inverse sign for k < 0.

A simple speed-up was achieved by observing that the number of valid Q is the same for P(p_x, p_y) and P(p_y, p_x).

That means that the two nested loops only need to considered the bottom-right triangle of the grid: P(p_x, p_y<=p_x).

For P(p_x, p_y<p_x) I multiply the number of Qs by 2 - but not when p_x=p_y.

## Alternative Approaches

Most other solutions replace my inner-most `while`

-loops by a closed formula:

`min(y * factor / x, (size - x) * factor / y) * 2`

Noone really explains that formula and surprisingly it isn't faster on my machine for `size <= 2500`

.

The original problem can be solved by brute-force, too (four nested loops for `p_x`

, `p_y`

, `q_x`

, `q_y`

).

## Modifications by HackerRank

Grids can have an edge length of up to 2500.

The brute-force approach fails of course (time-out) while my code finishes in less than 0.22 seconds.

# My code

… was written in C++ and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <algorithm>
// greatest common divisor

unsigned int gcd(unsigned int a, unsigned int b)
{
while (a != 0)
{
unsigned int c = a;
a = b % a;
b = c;
}
return b;
}
int main()
{
unsigned int size = 50;
std::cin >> size;
// triangles where right angle is in the origin
unsigned int result = size*size;
// plus triangles where the right angle is located on the x-axis
result += size*size;
// plus triangles where the right angle is located on the y-axis
result += size*size;
// now all triangles where the right angle at point P(x > 0, y <= x)
// that's the triangle in the bottom-right half, denoted by slashes
// ^ /
// | //
// | ///
// |////
// +--->
for (unsigned int p_x = 1; p_x <= size; p_x++)
for (unsigned int p_y = 1; p_y <= p_x; p_y++)
{
// reduce to a proper fraction
unsigned int factor = gcd(p_x, p_y);
unsigned int deltaX = p_x / factor;
unsigned int deltaY = p_y / factor;
unsigned int found = 0;
// assume Q is "below" P
int q_x = p_x - deltaY;
int q_y = p_y + deltaX;
while (q_x >= 0 && q_y <= (int)size)
{
found++;
q_x -= deltaY;
q_y += deltaX;
}
// assume Q is "above" P
q_x = p_x + deltaY;
q_y = p_y - deltaX;
while (q_y >= 0 && q_x <= (int)size)
{
found++;
q_x += deltaY;
q_y -= deltaX;
}
// mirror along y=x when p_y < p_x
if (p_x != p_y)
found *= 2;
result += found;
}
std::cout << result << std::endl;
return 0;
}

This solution contains 13 empty lines, 15 comments and 2 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo 2 | ./91`

Output:

*Note:* the original problem's input `50`

cannot be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in **less than 0.01** seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

March 15, 2017 submitted solution

May 10, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler091

My code solved **11** out of **11** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **25%** (out of 100%).

Hackerrank describes this problem as **medium**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is never an option.

# Links

projecteuler.net/thread=91 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-91-right-angle-triangles-quadrant/ (written by Kristian Edlund)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p091.java (written by Nayuki)

Scala: github.com/samskivert/euler-scala/blob/master/Euler091.scala (written by Michael Bayne)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are already solved and there wasn't a Hackerrank version of it (at the time I solved it) or I didn't care about it because it differed too much.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

<< problem 90 - Cube digit pairs | Square digit chains - problem 92 >> |