# Project Euler #86: Cuboid route

# Project Euler #86: Cuboid route

beta_projects + 0 comments It may help to review OEIS A143715. The sequence is explained there and will also help check for correct calculations.

LittleFox + 1 comment The "sample output" in the problem description is in wrong order.

vatsalchanana + 1 comment No, it is in the correct order. The number of solutions is 1975 when M=99. The number of solutions is 2060 when M=100.

LittleFox + 0 comments It was fixed silently in the meantime ^^.

ErikTillema + 1 comment Solved this problem in F#. Insights:

- count only really distinct cuboids, for example the cuboids (A,B,C) (3,5,6) and (6,5,3) are considered equal.
- key insight for me was that there are only 1.5 million pythagorean triplets that correspond to a cuboid with max size 400.000
- if you use Euclid's formula (see for example https://en.wikipedia.org/wiki/Pythagorean_triple ) to generate pythagorean triplets and you are only interested in right triangles with maximum right side length M, then you can use 1.1*sqrt(M) as an upper bound for m.

If anybody is interested, I can write down my approach to solve this problem.

kitchent + 1 comment Curious to know how it works to compute million pythagorean triplets within the time limit. I've been using Euclid's formula, but that

`m += 1`

,`n += 2`

is supposedly killing it. It takes almost 5 seconds to generate triplets up to (with most of the time spent on finding the valid primitive triplets), let alone .Perhaps it is because of the upper bound you mentioned? I don't know where that

`1.1*sqrt(M)`

comes from, the bound I used was a while-loop with condition`m**2 - (m-1)**2 <= M`

. When I look closely, this condition is unnecessarily loose, as it does not take into account the fact that either`a >= b`

or`b >= a`

should be true, while and .**EDIT**: I tried using this upper bound, and got WA for Test Cases #3 through #9.**EDIT 2**: Tried with`sqrt(3*M)`

and it works. Even`sqrt(2*M)`

did not work, where it was missing some pairs like`m=917, n=218`

. Maybe the difference is due to the way I handled the triples, as I append whenever`a >= b_plus_c / 2 + b_plus_c % 2`

or`b_plus_c >= a / 2 + a % 2`

.I'm quite sure that this condition would fail again for much larger input. The naming here is quite confusing, as

`b_plus_c >= a / 2 + a % 2`

in fact means`b >= a_plus_c / 2 + a_plus_c % 2`

, but I just handle them all in one place.**EDIT 3**: By the way, I find it interesting that no one mentioned another key insight involved in solving this problem, that is to visualise the unfolding of the 3D box. At the beginning, I was trying to solve the equation and find the derivative of it to look for a minimum, thinking about how this problem is supposed to be 35% difficulty.ErikTillema + 0 comments Yes, the upper bound is crucial in finding all the Pythagorean triplets within the time limit.

Note that the M in my upper bound definition is not the same as the M in the problem statement. Sorry for the confusion about that. This might explain the difference in your findings about the upper bound.

The other insight you mention is crucial as well. I didn't want to spoil too much :-)

I hope this clears some things up.

padeff + 0 comments . Would definitively advise to complete 75, and use roll distribution on the answer of 75. I dont think there is a way to solve it without generating pythagorean triplet correctly.

rishabh_vijay + 1 comment in the diagram given in problem,how the shortest path is 10.

phani_py + 0 comments open the cubiod

Sort 12 Discussions, By:

Please Login in order to post a comment