Project Euler > Problem 143 > Investigating the Torricelli point of a triangle (Java Solution)

Problem:

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XC = q, and XB = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r [≤] 120000 for Torricelli triangles.

Solution:

16695334890

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 43
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */


public final class p043 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p043().run());
	}
	
	
	private static int[] DIVISIBILITY_TESTS = {2, 3, 5, 7, 11, 13, 17};  // First 7 primes
	
	
	public String run() {
		long sum = 0;
		int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
		outer:
		do {
			for (int i = 0; i < DIVISIBILITY_TESTS.length; i++) {
				if (toInteger(digits, i + 1, 3) % DIVISIBILITY_TESTS[i] != 0)
					continue outer;
			}
			sum += toInteger(digits, 0, digits.length);
		} while (Library.nextPermutation(digits));
		return Long.toString(sum);
	}
	
	
	private static long toInteger(int[] digits, int off, int len) {
		long result = 0;
		for (int i = off; i < off + len; i++)
			result = result * 10 + digits[i];
		return result;
	}
	
}