# 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

pogo001 + 1 comment m not getting the correct answers. for m=100 output=2061, for m=99 output=2053 also for 1,2,3,4,5,6 outputs are 0,0,1,2,2,6 . please help :(

tyler_durden + 0 comments Please post the link to your submission..

dave_shubham_2 + 1 comment I have used DP and normal approach together and my submission is working normally for more than half the range but need to optimize it more as timeouts are occuring. Could someone help me ?

tyler_durden + 1 comment Please post link to your solution.

SalvadorDali + 1 comment Can not get the correct numbers. For N =

`100, 99`

getting`2015`

and`1919`

.Anyone has an idea of what I am doing wrong? Also a couple of answers for m =

`1, 2, 3, 4, 5, 6`

I am getting`0, 0, 3, 3, 3, 8, 8, 10, 17`

dave_shubham_2 + 0 comments Your code is eliminating the possibilities unnecessarily. Check for any logical errors. Answers for 1,2,3,4,5,6 are 0,0,2,3,3,6. Try printing the solutions for those and put it here then, may be anyone of us can help.

andreshp + 1 comment This is a way harder than the project euler one. Solved it in project euler but i can't get more than 30 points here :(

Crafter_Artisan + 0 comments Yeah, I started out using the same approach as the Project Euler version, and timed out on the last 7 test cases. I had to revise my approach.

Don't start with M and try to find what cuboids are possible. Start with the condition that the shortest cuboid route length is integer and use that to see which M's you can "hit"

Sort 12 Discussions, By:

Please Login in order to post a comment