Project Euler 86 - Cuboid Route

Official link: https://projecteuler.net/problem=86

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