Post date: Dec 25, 2016 2:27:43 PM
"If M is the maximum width, length, or height of a cuboid room, what is the smallest value of M having number of cuboids with integer dimensions where the shortest distance from the bottom left back corner of a cuboid room to the upper right forward corner is an integer length is over one million."
This problem contains a picture ... you know how they say a picture is worth a thousand words? For this picture, the words must all be dirty ones. In the picture, the path is a straight line (the shortest distance between two points), except that it shifts 90 degrees vertically when it hits the wall. In a 2-D drawing, you can't tell this. It makes the question even harder to figure out. Merry X-mas.
The problem claims to be a problem about finding cuboids, but it really is a problem about finding triangles. If you knock the wall down and line it up by the floor, so that the path is a literal straight line, you get a right triangle, where one side has length less than or equal to M and one side has length less than or equal to 2M, and is split on an integer boundary. We need to find M so that there are just slightly over 1 million solutions for the static side and the two halves of the split side.
Again we need Pythagorean triples. Euclid's formula generates Pythagorean triples from pairs of integers m and n.
a = m**2 - n**2, b = 2*m*n, c = m**2 + n**2
-- While it is easy to find the number of solutions when you have the max side length, the other way doesn't work (starting with # of solutions and getting the max side length). But we need to pick a size for this table, because we don't have infinite time or space, so we guess.
-- Through trial and error, I found 10000 to be big enough to get a quick answer, while 1000 was too small to get the correct answer.
-- By cutting the number of rows, we limit the max value of both sides when generating non-primitive triples, so there is no point wasting any time going higher than 10k.
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL, s BIGINT NOT NULL)
INSERT INTO #Integers VALUES (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81)
; WITH Integers (i) AS
(
SELECT o.i +
10 * d.i +
100 * h.i +
1000 * k.i
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
)
INSERT INTO #Integers
SELECT i + 1, SQUARE(i + 1)
FROM Integers
WHERE i > 8
DELETE FROM #Integers WHERE i = 0
-- A Pythagorean triple is made up of either 3 even numbers or 2 odd numbers and 1 even number.
-- Number b is even, so the other two must either be both odd or both even. This means that a and c are either both even or both odd.
-- We don't care in this case if it is a primitive triple or not, so we don't need to make sure m and n are coprime like we did in problem 75.
CREATE TABLE #Triangles (a BIGINT NOT NULL, b BIGINT NOT NULL)
; WITH Triangles (a, b) AS
(
SELECT m.s - n.s AS a
, 2 * m.i * n.i AS b
-- , m.s + n.s AS c
FROM #Integers m
INNER JOIN #Integers n
ON m.s > n.s
WHERE (m.s - n.s) % 2 = (m.s + n.s) % 2 -- Both even or both odd
)
INSERT INTO #Triangles (a, b)
SELECT a, b
FROM Triangles
WHERE a <= 10000
AND b < 10000
-- Unfortunately, while Euclid's formula generates Pythagorean triples, it doesn't generate all Pythagorean triples, only all primitive triples (and some that aren't primitive).
-- Because it only generates primitive triples, we throw a multiplier in to fill out the rest. Because the triples aren't primitive, there will be duplicates, which the UNION statement drops.
; WITH Triangles (a, b) as
(
SELECT i.i * t.a, i.i * t.b
FROM #Triangles t
INNER JOIN #Integers i
ON i.i * t.a <= 10000 -- When a is 1, the max is set by i (10k).
AND t.a <= 10000 -- When a is 1, the max is set by i (10k).
AND i.i * t.b <= 10000 -- When b is 1, the max is set by i (10k).
UNION
-- We have to find the case when the lengths are flipped 180 degrees.
-- The UNION will drop duplicates from here as well.
SELECT i.i * t.b, i.i * t.a
FROM #Triangles t
CROSS JOIN #Integers i
WHERE i.i * t.b <= 10000 -- When b is 1, the max is set by i (10k).
AND t.b <= 10000 -- When b is 1, the max is set by i (10k).
AND i.i * t.a <= 20000 -- When a is 1, the max is set by i (10k).
)
INSERT INTO #Triangles (a, b)
SELECT a, b
FROM Triangles
EXCEPT
SELECT a, b
FROM #Triangles
-- Now that we have all the triangles, we have to calculate the ways to split one of the sides.
-- On each triangle, we can cut the one side along each integer division from one of the sides, which is represented by the 'split' table.
-- The length of one half is the length of the split and the other half is the entire side length minus the split length.
; WITH Cuboids (M, a, b) AS
(
SELECT tri.a , split.i, tri.b - split.i
FROM #Triangles tri
INNER JOIN #Integers split
ON split.i < tri.b -- Side b can't be negative or zero.
AND split.i <= tri.a -- To avoid dupes from rotating the cuboid, we make sure that side w is less than side a.
AND tri.b - split.i <= split.i -- To avoid dupes from rotating the cuboid, we make sure that side b is less than side b.
-- Note that these two rules mean that the first column is the max for all 3 columns.
),
Counted (M, c) AS
(
SELECT M, ROW_NUMBER() OVER (ORDER BY M)
FROM Cuboids
)
SELECT M
FROM Counted
WHERE c = 1000000
DROP TABLE #Integers
DROP TABLE #Triangles