Problem 086: Cuboid route
A spider, S, sits in one corner of a cuboid room, measuring
6 by 5 by 3,
and a fly, F, sits in the opposite corner.
By travelling on the surfaces of the room the shortest "straight line"
distance from S to F is 10 and the path is shown on the diagram.
However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.
It can be shown that there are exactly
2060 distinct cuboids, ignoring rotations,
with integer dimensions, up to a maximum size of
M by M by M,
for which the shortest route has integer length when
M = 100.
This is the least value of M for which the number of solutions first exceeds two thousand;
the number of solutions when
M = 99 is
Find the least value of M such that the number of solutions first exceeds one million.
>"}}@"**50p040p0>1+:v>>1-::*70g:*+v vp01g03_^#-g01:_^#- <: g : :
:+ v < >:30p:20 g\/+2/: 30g^* 0>#1v2
71 > >#^ #p #0 2 #<$ v 7gv+</
0* >:88*%"9"`#^_:88+%:9`#v_:2-#v_v 2 :082g8
p2 > > > > # >$>$0>|80/0
0p |!-8_^#-7:_^#-6:_^#-5:_^# -3:< g +p7^<
80 > ^< 0 <^:p010 <^<-! ^10#<
> ^ >^ >:55+%:7-!#^_:3-!#^_2-!#^_:3%2-#^_^>^ $g -
@._^#`g05p04:+g04g08$_^#!: < <>\^
The spider essentially travels on the hypotenuse of a triangle with the sides
For it to be the shortest path the condition
A <= B+C must be true.
The amount of integer-cuboids for a given value M is "All integer-cuboids with
A=M" plus integer-cuboids(M-1).
In our loop we start with
M=1 and increment it in every step.
We also remember the last value (for
M-1) and loop until the value exceeds one million.
For a given value
A = M we go through all possible
BC value (
0 <= BC <= 2*A) and test if
M^2 + BC^2 is an integer-square.
If such a number is found and
BC <= A then this means we have found
BC/2 additional cuboids (there are
B+C = BC combinations where
B <= C)
If, on the other hand
BC > A then we have only found
A - (BC + 1)/2 + 1 additional cuboids (because the condition
A <= BC must be satisfied).
One of the more interesting parts was the
isSquareNumber() function, which test if a number
x has an integer square-root.
To speed this function up (it takes most of the runtime) we can eliminate around 12% of the numbers with a few clever tricks.
For example if the last digit of
2, x is never a perfect square-number. Or equally if the last hex-digit is
In our program we test twelve conditions like that:
x % 16 > 9 x % 64 > 57 x % 16 == 2 x % 16 == 3 x % 16 == 5 x % 16 == 6 x % 16 == 7 x % 16 == 8 x % 10 == 2 x % 10 == 3 x % 10 == 7 x % 3 == 2
If none of this pre-conditions is true we have to manually test the number.
We use the same the same integer-squareroot algorithm as in previous problems.
isqrt(x)^2 == x the we can be sure that x is a perfect square number.
|Interpreter steps:||599 659 030|
|Execution time (BefunExec):||1min 31s (6.53 MHz)|
|Program size:||66 x 10 (fully conform befunge-93)|