dcsimg
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

A Numbers Game to Test Your SQL Skills : Page 3

Programming is not only remembering classes or utilities. Developing logical programming skills is just as important. See how you can hone your SQL skills by solving an abstract numbers problem.


advertisement

What About Tripartite or Quadripartite Numbers?

Another interesting task not directly related to the bipartite number problem is finding tripartite or quadripartite numbers. Well, you can handle that easily by using a table with the replicated numbers (table t3) and applying the same idea as you did for bipartite numbers (see Listing 3):

Listing 3. How to Find Tripartite Numbers

SELECT (t3.sequence + t4.sequence + t5.sequence) AS [Tripartite Numbers]
   FROM t3 CROSS JOIN t3 AS t4 CROSS JOIN t3 AS t5
   WHERE LEFT(t3.sequence + t4.sequence + t5.sequence, 1) <> '0'
   AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)
   AND LEFT(t3.sequence, 1) <> LEFT(t5.sequence, 1)
   AND LEFT(t4.sequence, 1) <> LEFT(t5.sequence, 1)
 ORDER BY 1

Result:

Tripartite Numbers
------------------------------------------
10000000002
100000000022
1000000000222
10000000002222
100000000022222
1000000000222222
10000000002222222
100000000022222222
1000000000222222222
10000000003
100000000033
1000000000333
10000000003333
. . . . . . . . . . .
. . . . . . . . . . .

99999999988888888866
999999999888888888666
9999999998888888886666
99999999988888888866666
999999999888888888666666
9999999998888888886666666
99999999988888888866666666
999999999888888888666666666
9999999998888888887
99999999988888888877
999999999888888888777
9999999998888888887777
99999999988888888877777
999999999888888888777777
9999999998888888887777777
99999999988888888877777777
999999999888888888777777777

(472392 row(s) affected)

Be careful, however, if you want to run a query for quadripartite numbers as in Listing 4:


Listing 4. How to Find Quadripartite Numbers

SELECT (t3.sequence + t4.sequence + t5.sequence + t6.sequence) AS [Quadripartite Numbers]
   FROM t3 CROSS JOIN t3 AS t4 CROSS JOIN t3 AS t5 CROSS JOIN t3 AS t6
   WHERE LEFT(t3.sequence + t4.sequence + t5.sequence + t6.sequence, 1) <> '0'
   AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)
   AND LEFT(t3.sequence, 1) <> LEFT(t5.sequence, 1)
   AND LEFT(t3.sequence, 1) <> LEFT(t6.sequence, 1)
   AND LEFT(t4.sequence, 1) <> LEFT(t5.sequence, 1)
   AND LEFT(t4.sequence, 1) <> LEFT(t6.sequence, 1)
   AND LEFT(t5.sequence, 1) <> LEFT(t6.sequence, 1)
 ORDER BY 1

This query is very heavy. If you want to test it anyway, you better decrease the number of rows in table t1. Run Listing 1 one more time, and insert numbers from 1 to 5 into the table t1.

Different SQL Server Version, Different Result

The quadripartite query from Listing 4 works fine for the five rows in table t1. It generates 2,835,000 quadripartite numbers but only in SQL Server 2000. In SQL Server 2005, the same query for the same five rows in table t1 generates 2,196,003 quadripartite numbers and then fails with the following error:
"An error occurred while executing batch. Error message is: Couldn't replace text."

You can easily find the solution by going back to the original problem (see Listing 5):


Listing 5. Final Solution

-- sample input
DECLARE @input int
SET @input = 2005
 
-- min bipartite number, corresponding to the sample input
SELECT MIN(CAST(BipartiteNum as bigint)) AS minBipartiteNum
   FROM
   (SELECT (t3.sequence + t4.sequence) AS BipartiteNum
      FROM t3 CROSS JOIN t3 AS t4
      WHERE LEFT(t3.sequence + t4.sequence, 1) <> '0'
      AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)) T5
   WHERE CAST(bipartiteNum AS bigint) % @input = 0

-- all bipartite numbers, corresponding to the sample input
SELECT CAST(BipartiteNum as bigint) BipartiteNum
   FROM
   (SELECT (t3.sequence + t4.sequence) AS BipartiteNum
      FROM t3 CROSS JOIN t3 AS t4
      WHERE LEFT(t3.sequence + t4.sequence, 1) <> '0'
      AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)) T5
   WHERE CAST(bipartiteNum AS bigint) % @input = 0

Result:

minBipartiteNum
--------------------
222555

BipartiteNum
--------------------
222555
855555555
2222222555555555

Problem-Solving Outside the Box

Even though the ACM-ICPC 2006 World Finals contestants could use only Java, C/C++, or Pascal, it was very instructive to solve the problem in SQL—just one more example of how useful it is to see a problem from another point of view and use logical programming skills to solve it.



Alex Kozak is a senior DBA/analyst working for SAP Canada. He has more than 15 years of database and programming experience. Microsoft has included some of his articles in the MSDN Library.
Thanks for your registration, follow us on our social networks to keep up-to-date