Post date: Mar 18, 2015 12:22:1 AM
(In case you're wondering where problem 67 is, it's back here.)
"If you consider a pentagon with circles at each of the points, and another circle extended out from each of the points, each circle with a different number between 1 and 10 inside it, you get five lines. Each line contains three numbers. Build a string out of each line by concatenating each number from outside to inside. Start with the line where the external point has the lowest number. Build a string by combining each 'line' string in clockwise order. Confused yet?
What is the maximum number formed by a 16-digit string, out of all the possible arrangements of numbers?"
There's really no way to understand this other than to look at the pictures at the Project Euler page.
This is a pretty complicated setup. I am a DBA, so when it comes to how to model the ring, in a way that I can calculate the lines and rotate it clockwise, I naturally think a table. Is that weird? Most people would probably think in terms of the physical structure. I first think of the table when trying to solve the problem. This is one of the ways to solve it.
There is another way. It's faster and doesn't involve tables. But it's good idea to understand how to solve the problem with a table before throwing away the table and doing it the faster way, which is harder to understand.
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Integers VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)
CREATE TABLE #Gon (id tinyint PRIMARY KEY not null, value INT NOT NULL)
CREATE UNIQUE INDEX [IX_GonFreecss] ON #Gon (value)
CREATE TABLE #GonLine (id INT PRIMARY KEY not null, gon1 INT not null, gon2 INT not null, gon3 INT not null)
INSERT INTO #GonLine VALUES
(1, 10, 3, 2),
(2, 9, 2, 1),
(3, 8, 1, 5),
(4, 7, 5, 4),
(5, 6, 4, 3)
CREATE TABLE #Results (r varchar(20) NOT NULL)
DECLARE @o1 INT, @o2 INT, @o3 INT, @o4 INT, @o5 INT, @o6 INT, @o7 INT, @o8 INT, @o9 INT, @o10 INT
-- Loop through each possible arrangement. Each number can only be used once.
DECLARE Euler68 CURSOR STATIC LOCAL FOR
SELECT o1.i, o2.i, o3.i, o4.i, o5.i, o6.i, o7.i, o8.i, o9.i, o10.i
FROM #Integers o1
INNER JOIN #Integers o2
ON o2.i <> o1.i
INNER JOIN #Integers o3
ON o3.i NOT IN (o2.i,o1.i)
INNER JOIN #Integers o4
ON o4.i NOT IN (o3.i,o2.i,o1.i)
INNER JOIN #Integers o5
ON o5.i NOT IN (o4.i,o3.i,o2.i,o1.i)
INNER JOIN #Integers o6
ON o6.i NOT IN (o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN #Integers o7
ON o7.i NOT IN (o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN #Integers o8
ON o8.i NOT IN (o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN #Integers o9
ON o9.i NOT IN (o8.i,o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN #Integers o10
ON o10.i NOT IN (o9.i,o8.i,o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
WHERE
-- The question asks for 16-digit strings, which means the 10 is on the outer ring. If it were not, it would appear twice, adding a digit to two lines.
-- In this data set, the inner ring is in o1 to o5.
-- In addition, we want to avoid doing the same query 5 times, each time the same thing but rotated 20 degrees.
-- If we set o10 to 10, we block both cases.
o10.i = 10
-- This normally produces a lot of different options, most of which don't match.
-- Because we know where these values will go, we can check them before going through the insert phase.
AND o10.i + o3.i + o2.i = o9.i + o2.i + o1.i
AND o10.i + o3.i + o2.i = o8.i + o1.i + o5.i
AND o10.i + o3.i + o2.i = o7.i + o5.i + o4.i
AND o10.i + o3.i + o2.i = o6.i + o4.i + o3.i
OPEN Euler68
WHILE 1 = 1
BEGIN
FETCH NEXT FROM Euler68 INTO @o1, @o2, @o3, @o4, @o5, @o6, @o7, @o8, @o9, @o10
IF @@FETCH_STATUS <> 0 BREAK
TRUNCATE TABLE #Gon
INSERT INTO #Gon VALUES (1, @o1), (2, @o2), (3, @o3), (4, @o4), (5, @o5), (6, @o6), (7, @o7), (8, @o8), (9, @o9), (10, @o10)
; WITH GonRing (id, g1, g2, g3) AS
(
SELECT gl.id, g1.value, g2.value, g3.value
FROM #GonLine gl
INNER JOIN #Gon g1 ON g1.id = gl.gon1
INNER JOIN #Gon g2 ON g2.id = gl.gon2
INNER JOIN #Gon g3 ON g3.id = gl.gon3
)
INSERT INTO #Results
SELECT (SELECT RTRIM(g1) + RTRIM(g2) + RTRIM(g3)
FROM GonRing
ORDER BY CASE WHEN g1 = MIN(g1) OVER (PARTITION BY 1) THEN 0 ELSE 1 END, id
FOR XML PATH(''),TYPE)
.value('text()[1]','nvarchar(max)') -- Concatenate the rows into a single string.
END -- While
CLOSE Euler68
DEALLOCATE Euler68
SELECT TOP 1 r
FROM #Results
ORDER BY r DESC
DROP TABLE #GonLine
DROP TABLE #Gon
DROP TABLE #Integers
DROP TABLE #Results
Here's the one-query, no tables, solution. It's probably pretty confusing. But if you understand the table version, it may make sense, because this is just a translation of the same logic to a single set.
WITH Integers (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 10
)
SELECT TOP 1 solution
FROM Integers o1
INNER JOIN Integers o2
ON o2.i <> o1.i
INNER JOIN Integers o3
ON o3.i NOT IN (o2.i,o1.i)
INNER JOIN Integers o4
ON o4.i NOT IN (o3.i,o2.i,o1.i)
INNER JOIN Integers o5
ON o5.i NOT IN (o4.i,o3.i,o2.i,o1.i)
INNER JOIN Integers o6
ON o6.i NOT IN (o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN Integers o7
ON o7.i NOT IN (o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN Integers o8
ON o8.i NOT IN (o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN Integers o9
ON o9.i NOT IN (o8.i,o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
INNER JOIN Integers o10
ON o10.i NOT IN (o9.i,o8.i,o7.i,o6.i,o5.i,o4.i,o3.i,o2.i,o1.i)
CROSS APPLY
(
-- The tricky part is having to treat each set of 3 as a unit, but still shift them around a starting point which changes from row to row.
-- They still need to be on different rows. That is how you sort objects in SQL. So here I create a fake rowset, sort it, and collapse it into a single row.
SELECT (
SELECT RTRIM(g1) + RTRIM(g2) + RTRIM(g3)
FROM (
SELECT 1, o10.i, o3.i, o2.i
UNION SELECT 2, o9.i, o2.i, o1.i
UNION SELECT 3, o8.i, o1.i, o5.i
UNION SELECT 4, o7.i, o5.i, o4.i
UNION SELECT 5, o6.i, o4.i, o3.i
) AS GonRing(id, g1, g2, g3)
ORDER BY CASE WHEN g1 = MIN(g1) OVER (PARTITION BY 1) THEN 0 ELSE 1 END, id
FOR XML PATH(''),TYPE
).value('text()[1]','nvarchar(max)')
) AS Magic (solution)
WHERE
-- The question asks for 16-digit strings, which means the 10 is on the outer ring.
-- In this data set, the inner ring is in o1 to o5.
-- In addition, we want to avoid doing the same query 5 times, each time the same thing but rotated 20 degrees.
-- If we set o10 to 10, we block both cases.
o10.i = 10
-- This normally produces a lot of different options, most of which don't match.
-- Because we know where these values will go, we can check them before going through the insert phase.
AND o10.i + o3.i + o2.i = o9.i + o2.i + o1.i
AND o10.i + o3.i + o2.i = o8.i + o1.i + o5.i
AND o10.i + o3.i + o2.i = o7.i + o5.i + o4.i
AND o10.i + o3.i + o2.i = o6.i + o4.i + o3.i
ORDER BY solution DESC