Post date: Oct 16, 2016 1:53:9 PM
"Find the rectangular with integer length and width which, if split into a grid of integer 1x1 squares, could contain as close to 2 million unique rectangles along grid lines. Find the area of this enclosing rectangle."
It is difficult to tell from the pictures displayed in the original problem, but basically a sub-rectangle of full length has only 1 possible position, one with full length minus 1 has 2 (it can slide one square up), the next 3, etc. The total is 1 + 2 + 3 + ... + last. The situation is the similar for the width, except multiplied. Take each value calculated for the length and multiply it by 1, by 2, by 3, etc, until you get the one with closest to 2 million sub-rectangles.
Because we don't know beforehand what the width will be (or the length ... either way, sub-rectangles can be rotated 90 degrees), we will assume a width of 1, and calculate all possible lengths. As the width increases, the length will always be less than this maximum.
We use this array of values for both length and width when calculating the ideal area.
CREATE TABLE #Wrecked (side int IDENTITY(1,1) NOT NULL PRIMARY KEY, rectangles bigint NOT NULL)
DECLARE @c int = 1, @r int = 1
WHILE @r < 2000000
BEGIN
INSERT INTO #Wrecked (rectangles)
VALUES (@r)
SET @c = @c + 1
SET @r = @r + @c
END
-- Go one higher, just in case the nearest value is slightly higher than 2 million. They didn't say closest to 2 million without going over, just closest to 2 million.
INSERT INTO #Wrecked (rectangles)
VALUES (@r)
-- Get the one value with the closest # of sub-rectangles.
SELECT TOP 1 s1.side * s2.side
FROM #Wrecked s1
CROSS JOIN #Wrecked s2
ORDER BY ABS(2000000 - s1.rectangles * s2.rectangles)
DROP TABLE #Wrecked