Another German Yak ... with a suprise (RC #3)

By Bill Graziano on 16 July 2002 | Tags: Reader Challenges

This Reader Challenge #3 solution is quite a bit different from the first solution I posted. And it's chock full of "sqlicious" goodness. And a suprise at the end!

The second solution I received was from Arnold Fribble (Arnold Fribble). And boy is it a doozy. I'll post it here and then walk through it.

CREATE TABLE #n5 (n int PRIMARY KEY)
INSERT INTO #n5 
SELECT 1 UNION ALL 
SELECT 2 UNION ALL 
SELECT 3 UNION ALL 
SELECT 4 UNION ALL 
SELECT 5

SELECT
  CASE WHEN Yak = Dane THEN 'Dane'
       WHEN Yak = English THEN 'English'
       WHEN Yak = German THEN 'German'
       WHEN Yak = Norwegian THEN 'Norwegian'
       WHEN Yak = Swede THEN 'Swede'
  END AS YakOwner
FROM (
    SELECT
      a1.n Dane, a2.n English, a3.n German, a4.n Norwegian, a5.n Swede,
      b1.n Blue, b2.n Green, b3.n  Red, b4.n White, b5.n Yellow,
      c1.n Birds, c2.n Cats, c3.n Dog, c4.n Horse, c5.n Yak,
      d1.n Beer, d2.n Coffee, d3.n Milk, d4.n Tea, d5.n Water,
      e1.n Blend, e2.n BlueMaster, e3.n Dunhill, e4.n PallMall, e5.n Prince
    FROM
      #n5 a1, #n5 a2, #n5 a3, #n5 a4, #n5 a5, -- nationalities
      #n5 b1, #n5 b2, #n5 b3, #n5 b4, #n5 b5, -- house colors
      #n5 c1, #n5 c2, #n5 c3, #n5 c4, #n5 c5, -- pets
      #n5 d1, #n5 d2, #n5 d3, #n5 d4, #n5 d5, -- drinks
      #n5 e1, #n5 e2, #n5 e3, #n5 e4, #n5 e5  -- cigarettes
    WHERE a2.n NOT IN (a1.n) AND a3.n NOT IN (a1.n, a2.n) 
	AND a4.n NOT IN (a1.n, a2.n, a3.n) AND a5.n NOT IN (a1.n, a2.n, a3.n, a4.n)
      AND b2.n NOT IN (b1.n) AND b3.n NOT IN (b1.n, b2.n) 
	AND b4.n NOT IN (b1.n, b2.n, b3.n) AND b5.n NOT IN (b1.n, b2.n, b3.n, b4.n)
      AND c2.n NOT IN (c1.n) AND c3.n NOT IN (c1.n, c2.n) 
	AND c4.n NOT IN (c1.n, c2.n, c3.n) AND c5.n NOT IN (c1.n, c2.n, c3.n, c4.n)
      AND d2.n NOT IN (d1.n) AND d3.n NOT IN (d1.n, d2.n) 
	AND d4.n NOT IN (d1.n, d2.n, d3.n) AND d5.n NOT IN (d1.n, d2.n, d3.n, d4.n)
      AND e2.n NOT IN (e1.n) AND e3.n NOT IN (e1.n, e2.n) 
	AND e4.n NOT IN (e1.n, e2.n, e3.n) AND e5.n NOT IN (e1.n, e2.n, e3.n, e4.n)
  ) AS perms
WHERE English = Red
  AND Swede = Dog
  AND Dane = Tea
  AND Green = White - 1
  --AND Green < White  -- alternate interpretation for previous line
  AND Coffee = Green
  AND PallMall = Birds
  AND Yellow = Dunhill
  AND Milk = 3
  AND Norwegian = 1
  AND ABS(Blend - Cats) = 1
  AND ABS(Horse - Dunhill) = 1
  AND BlueMaster = Beer
  AND German = Prince
  AND ABS(Norwegian - Blue) = 1
  AND ABS(Water - Blend) = 1

DROP TABLE #n5

Yep, that's all there is to it. A temp table and a SELECT statement. So let's start breaking this down. First, he creates a temp table that hold the numbers 1 though 5. This is commonly called a Tally table and we've seen it before.

Then he has a SELECT from a SELECT. I'm going to basically rebuild his query from scratch starting at the inside. The simplest piece looks like this:

SELECT a1.n Dane, a2.n English
FROM #n5 a1, #n5 a2

Note that I'm leaving off the part the generates the temp table and populates it. It generates the following result:

Dane        English     
----------- ----------- 
1           1
2           1
3           1
4           1
5           1
1           2
2           2
3           2
4           2
5           2
1           3
2           3
3           3
4           3
5           3
1           4
2           4
3           4
4           4
5           4
1           5
2           5
3           5
4           5
5           5

Which is 25 rows of possible solutions. He does a cross join of the temp table to itself. This joins each row in the table to every other row in the table -- including itself. If there were nine rows in the table we'd have 81 rows in the result set. His naming of the columns is what maps it back to the problem. In this little sample set we can see every possible permutation of housing for the Dane and the Englishman.

The first piece he adds is a WHERE clause to remove two people living in the same house. Modifying the query we get this:

SELECT a1.n Dane, a2.n English
FROM #n5 a1, #n5 a2
WHERE a2.n NOT IN (a1.n)

The WHERE clause says I want all the possible permutations of this except where the English house (a2.n) is equal to the Danish house (a1.n). This would eliminate all the rows from the above result set where the two numbers are equal.

Let's add a third parameter and see what that looks like.

SELECT a1.n Dane, a2.n English, a3.n German
FROM #n5 a1, #n5 a2, #n5 a3
WHERE a2.n NOT IN (a1.n)
AND a3.n NOT IN (a1.n, a2.n)

which returns the following result set:

Dane        English     German      
----------- ----------- ----------- 
1           3           2
1           4           2
1           5           2
1           2           3
1           4           3
... 55 rows omitted for ease of reading...

Now let's pretend that one of our rules is that the Dane must live next to the Englishman. You might write that like this:

SELECT 	a1.n Dane, a2.n English, a3.n German
FROM 	#n5 a1, #n5 a2, #n5 a3
WHERE 	a2.n NOT IN (a1.n)
AND 	a3.n NOT IN (a1.n, a2.n) 
AND 	ABS(a1.n - a2.n) = 1

And we're left with just the rows where the Dane and the Englishman are side by side.

Dane        English     German      
----------- ----------- ----------- 
1           2           3
1           2           4
1           2           5
2           3           1
2           1           3
... 19 rows omitted

To make the whole thing easier to read he wraps it in a derived table so he can use field names. Rewriting this query to use a derived table gives us

Select *
From (
	SELECT 	a1.n Dane, a2.n English, a3.n German
	FROM 	#n5 a1, #n5 a2, #n5 a3
	WHERE 	a2.n NOT IN (a1.n)
	AND 	a3.n NOT IN (a1.n, a2.n) ) as perm
WHERE 	ABS(Dane - English) = 1

which is much easier to read and returns the same result set as above. All that's really left is to add all the possible combinations and fill out the WHERE clause. At that point you get the query at the top of the page.

And that brings us to the suprise. One of the rules from the challenge was that the "green house is on the left side of the white house." I interpreted this to mean next door on the left. You'll notice the WHERE clause in the full query also makes that assumption. There's a line below it that's commented out that has the more general assumption. Switching to the commented out line gives us SEVEN possible solutions.

Removing the CASE and changing the main query to a SELECT * shows us the complete solutions. I can't display them here because they are too wide. I did pick one at random and test it manually against the rules and it came out just fine.

So that's the second solution. Great job Arnold. None of the others were drastically different than these two. If you'd like others to see your solution, please post it in the forums attached to one of these articles and we can all take a look.