Post date: Jul 03, 2014 1:15:13 AM
"If you build a 1001 x 1001 grid of numbers, by starting at the center and then, with each number, spiralling out and clockwise, what is the sum of the numbers along the diagonals crossing the center?"
To do this one quickly, don't look at every number. Skip everything but numbers on the the diagonals. Just notice that there is a pattern, with the numbers always increasing by either 2*4, 2*8, etc, (2 times a sequence increasing from 4), 2*2, 2*6, etc (same thing, with an offset of -2), etc, depending on if you are going up left, up right, or whatever.
CREATE TABLE #Integers (i INT NOT NULL PRIMARY KEY)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 1000
)
INSERT INTO #Integers
SELECT i
FROM Integers
OPTION (MAXRECURSION 1000)
; WITH Progression (i) AS
(
SELECT 4 * i
FROM #Integers
),
UR (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * i
FROM Progression
),
DR (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (1 + i)
FROM Progression
),
DL (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (i + 2)
FROM Progression
),
UL (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (3 + i)
FROM Progression
),
Nums (i) AS
(
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) FROM UR
UNION ALL
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) FROM DR
UNION ALL
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) FROM DL
UNION ALL
SELECT SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) FROM UL
)
SELECT SUM(i) + 1
FROM Nums
WHERE i <= (1001 * 1001)
AND i > 1
DROP TABLE #Integers
And here's the slower method for older versions of SQL Server. This will probably the last time I do a dual version comparison for the ROWS BETWEEN thing, but I wanted to demonstrate how to do a running total the old way. Previously, I think I just left it as an exercise for the student.
CREATE TABLE #Integers (i INT NOT NULL PRIMARY KEY)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 1000
)
INSERT INTO #Integers
SELECT i
FROM Integers
OPTION (MAXRECURSION 1000)
; WITH Progression (i) AS
(
SELECT 4 * i
FROM #Integers
),
UR (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * i
FROM Progression
),
DR (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (1 + i)
FROM Progression
),
DL (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (i + 2)
FROM Progression
),
UL (i) AS
(
SELECT 1
UNION ALL
SELECT 2 * (3 + i)
FROM Progression
),
Nums (i) AS
(
SELECT SUM(t1.i)
FROM UR t1
INNER JOIN UR t2 ON t1.i < t2.i
GROUP BY t2.i
UNION ALL
SELECT SUM(t1.i)
FROM UL t1
INNER JOIN UL t2 ON t1.i < t2.i
GROUP BY t2.i
UNION ALL
SELECT SUM(t1.i)
FROM DL t1
INNER JOIN DL t2 ON t1.i < t2.i
GROUP BY t2.i
UNION ALL
SELECT SUM(t1.i)
FROM DR t1
INNER JOIN DR t2 ON t1.i < t2.i
GROUP BY t2.i
)
SELECT SUM(i) + 1
FROM Nums
WHERE i <= (1001 * 1001)
AND i > 1
DROP TABLE #Integers