# Project Euler 86 - Cuboid Route # Thought Process

Part 1 of the problem is figuring out how to find the shortest route. I drew a little diagram for the problem in the question, essentially I unfolded the box, and I can see that the shortest distance = sqrt(6^2 + (5+3)^2) = sqrt(100) = sqrt(10)

We can generalise this:

We are looking for integer solutions of this equation which brings us to part 2 What I noticed is that we need triangles with integer sides where A^2 + (B+C)^2 = d^2, and we can generate these pythagorean triples using the method from Problem 9, Please read that problem to understand better.

Essentially we generate triangles where d = m^2 + n^2, and A or (B+C) = m^2 - n^2 or 2mn, now for the final part of the problem, we need to figure out all the possible combinations of the triangles.

Case 1: A = m^2 - n^2, B + C = 2mn

Case 2: A = 2mn, B + C = m^2 - n^2

Now we note the following:

1. If 2A < B + C => B or C or both are greater than A this is impossible, so there are 0 combinations of this type

2. If A >= B + C => A >= B, C, we must ensure that B >= C

• We can do a few example such as B+C = 5 => (B,C) = (4,1) or (3,2)

• B+C = 6 => (B,C) = (5,1) or (4,2) or (3,3)

• There will be floor((B+C)/2) combinations

3. If B+C >= A

• You can do a few more examples B+C = 15, A = 8 => (A,B,C) = (8,8,7)

• B+C = 12, A = 9 => (A,B,C) = (9,9,3) or (9,8,4) or (9,7,5) or (9,6,6) 4 possibilities

• What I notice is that if B+C is divisible by 2, we can include the solution where B = C as a solution

• Therefore if B + C is divisble by 2 then there are A - floor((B+C)/2) + 1 combinations

• Otherwise there are A - floor((B+C)/2) combinations

I just wrote a quick functions combinations which does part 3, used my Primitive Pythagorean Triple generator for Part 2, and the problem is easily solved!

# Interactive Code

Input an integer (yourinput)

Code will output the least value M such that the number of solutions > yourinput