SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Site Related Forums
 Article Discussion
 Article: Another German Yak ... with a suprise (RC #3)
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

AskSQLTeam
Ask SQLTeam Question

USA
0 Posts

Posted - 07/16/2002 :  01:12:58  Show Profile  Visit AskSQLTeam's Homepage  Reply with Quote
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!

Article Link.

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 07/16/2002 :  05:33:51  Show Profile  Reply with Quote
Thanks Graz, nice summary!

If you're interested in getting a prettier output from this method, then it's quite easy to cross-join another table into the query to represent a row in the result and select the value in each category according to the house number.

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 row AS "House Number",
CASE row
WHEN Dane THEN 'Dane'
WHEN English THEN 'English'
WHEN German THEN 'German'
WHEN Norwegian THEN 'Norwegian'
WHEN Swede THEN 'Swede'
END AS Nationality,
CASE row
WHEN Blue THEN 'Blue'
WHEN Green THEN 'Green'
WHEN Red THEN 'Red'
WHEN White THEN 'White'
WHEN Yellow THEN 'Yellow'
END AS "House Color",
CASE row
WHEN Birds THEN 'Birds'
WHEN Cats THEN 'Cats'
WHEN Dog THEN 'Dog'
WHEN Horse THEN 'Horse'
WHEN Yak THEN 'Yak'
END AS Pet,
CASE row
WHEN Beer THEN 'Beer'
WHEN Coffee THEN 'Coffee'
WHEN Milk THEN 'Milk'
WHEN Tea THEN 'Tea'
WHEN Water THEN 'Water'
END AS Drink,
CASE row
WHEN Blend THEN 'Blend'
WHEN BlueMaster THEN 'Blue Master'
WHEN Dunhill THEN 'Dunhill'
WHEN PallMall THEN 'Pall Mall'
WHEN Prince THEN 'Prince'
END AS Smoke
FROM (
SELECT row.n row,
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 row,
#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
NOT(a2.n IN (a1.n) OR a3.n IN (a1.n, a2.n)
OR a4.n IN (a1.n, a2.n, a3.n) OR a5.n IN (a1.n, a2.n, a3.n, a4.n)
OR b2.n IN (b1.n) OR b3.n IN (b1.n, b2.n)
OR b4.n IN (b1.n, b2.n, b3.n) OR b5.n IN (b1.n, b2.n, b3.n, b4.n)
OR c2.n IN (c1.n) OR c3.n IN (c1.n, c2.n)
OR c4.n IN (c1.n, c2.n, c3.n) OR c5.n IN (c1.n, c2.n, c3.n, c4.n)
OR d2.n IN (d1.n) OR d3.n IN (d1.n, d2.n)
OR d4.n IN (d1.n, d2.n, d3.n) OR d5.n IN (d1.n, d2.n, d3.n, d4.n)
OR e2.n IN (e1.n) OR e3.n IN (e1.n, e2.n)
OR e4.n IN (e1.n, e2.n, e3.n) OR e5.n 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
ORDER BY row

DROP TABLE #n5

 
(note application of de Morgan to the uniqueness constraint -- this just makes things a little shorter)

This gets difficult to use if there is more than one possible answer: it produces all the rows but they won't be in a useful order. One solution is to order the rows on all 26 columns. Another is to construct a composite value and order on that: this has the advantage of making it easier to feed the result into a reporting tool for prettification.


SELECT solution,
row AS "House Number",
[...]
FROM (
SELECT row.n row,
CAST(a1.n*1000 + a2.n*100 + a3.n*10 + a4.n AS char(4))+
CAST(b1.n*1000 + b2.n*100 + b3.n*10 + b4.n AS char(4))+
CAST(c1.n*1000 + c2.n*100 + c3.n*10 + c4.n AS char(4))+
CAST(d1.n*1000 + d2.n*100 + d3.n*10 + d4.n AS char(4))+
CAST(e1.n*1000 + e2.n*100 + e3.n*10 + e4.n AS char(4)) AS solution,
[...]
ORDER BY solution, row

 
This uses a character string, but there is enough room in a numeric(18,0) or bigint. I didn't include a5.n - e5.n in this because they are uniquely constrained by the other vaues.

In fact, we can use this last fact to cut down the number of cross-joined tables generating the solution space. The inner subquery perms becomes:


SELECT row.n row,
a1.n Dane, a2.n English, a3.n German, a4.n Norwegian,
15 - a1.n - a2.n - a3.n - a4.n Swede,
b1.n Blue, b2.n Green, b3.n Red, b4.n White,
15 - b1.n - b2.n - b3.n - b4.n Yellow,
c1.n Birds, c2.n Cats, c3.n Dog, c4.n Horse,
15 - c1.n - c2.n - c3.n - c4.n Yak,
d1.n Beer, d2.n Coffee, d3.n Milk, d4.n Tea,
15 - d1.n - d2.n - d3.n - d4.n Water,
e1.n Blend, e2.n BlueMaster, e3.n Dunhill, e4.n PallMall,
15 - e1.n - e2.n - e3.n - e4.n Prince
FROM
#n5 row,
#n5 a1, #n5 a2, #n5 a3, #n5 a4, -- nationalities
#n5 b1, #n5 b2, #n5 b3, #n5 b4, -- house colors
#n5 c1, #n5 c2, #n5 c3, #n5 c4, -- pets
#n5 d1, #n5 d2, #n5 d3, #n5 d4, -- drinks
#n5 e1, #n5 e2, #n5 e3, #n5 e4 -- cigarettes
WHERE
NOT(a2.n IN (a1.n) OR a3.n IN (a1.n, a2.n) OR a4.n IN (a1.n, a2.n, a3.n)
OR b2.n IN (b1.n) OR b3.n IN (b1.n, b2.n) OR b4.n IN (b1.n, b2.n, b3.n)
OR c2.n IN (c1.n) OR c3.n IN (c1.n, c2.n) OR c4.n IN (c1.n, c2.n, c3.n)
OR d2.n IN (d1.n) OR d3.n IN (d1.n, d2.n) OR d4.n IN (d1.n, d2.n, d3.n)
OR e2.n IN (e1.n) OR e3.n IN (e1.n, e2.n) OR e4.n IN (e1.n, e2.n, e3.n))

 
(For brevity, I've left out the 'solution' column introduced above)

To be honest, it doesn't make much difference either way, you trade a few keystrokes for an arguable loss of clarity and the need to work out that 1+2+3+4+5=15!

Something that Graz didn't mention is that this method relies heavily on the query optimizer. If the optimizer generated an execution plan for the perms subquery in isolation and fed the all resulting rows into the main query it would be a disaster, since the perms query on its own generates (5!)^5 = 24,883,200,000 rows. Rather, the optimizer works globally on the query and 'promotes' the testing of the puzzle constraints to a point much closer to where the values are generated. The optimizer also works hard at ordering the joins to minimize the number of solutions tested -- one thing you may notice is that it takes far longer to find an execution plan than to execute it!
By comparison, the original query (using a SELECT *, a permanent table for the numbers and sprinkled with lot of AS) run on Access 2000 takes my machine about 45 seconds -- which is still better than I expected!

Inspiration for this approach came from a couple of sources. First was an old column by Joe Celko on creating permutations http://www.dbmsmag.com/9806d06.html. Joe's thoughts were that the naive approach could be speeded up by creating a column of 'weights' like this:

i wgt
-------
1 1
2 2
3 4
4 8
5 16
6 32
7 64

 
and then testing that the values made a permutation with a single WHERE adding all the weights and checking that all the bits were set -- in this case, a total weight of 127.
Of course, on SQL Server, this turns out to be a terrible idea, much slower than the naive solution. The 'optimized' version has to generate all possible values while the in 'naive' version all the INs get broken up and each pair is tested at the first possible point!

I only discovered what the other source had been after submitting my solution! Some while back, I had a play around with Mozart http://www.mozart-oz.org/, an implementation of the OZ programming language. It's a weird language: part functional, part logic-based, part object-oriented with strong support for concurrency and constraint programming. I'd rather bridled at Rob's comment in the challenge that SQL was the best language for solving this puzzle, and resolved to write it in OZ too. Whereupon I found almost exactly the same thing as a worked example in the Finite Domain Constraint Programming tutorial! http://www.mozart-oz.org/documentation/fdt/node23.html#section.elimination.zebra

For what it's worth, here's the Yak puzzle translated from SQL to OZ by my decidedly inexpert hand -- their 'Zebra' solution is a little better abstracted:

declare
proc {Log Root}
Dane English German Norwegian Swede
Blue Green Red White Yellow
Beer Coffee Milk Tea Water
Birds Cats Dog Horse Yak
Blend BlueMaster Dunhill PallMall Prince
in
Root = sol(
dane:Dane english:English german:German
norgwegian:Norwegian swede:Swede
blue:Blue green:Green red:Red white:White yellow:Yellow
beer:Beer coffee:Coffee milk:Milk tea:Tea water:Water
birds:Birds cats:Cats dog:Dog horse:Horse yak:Yak
blend:Blend bluemaster:BlueMaster dunhill:Dunhill
pallmall:PallMall prince:Prince
)
Root ::: 1#5
{FD.distinct [Dane English German Norwegian Swede]}
{FD.distinct [Blue Green Red White Yellow]}
{FD.distinct [Beer Coffee Milk Tea Water]}
{FD.distinct [Birds Cats Dog Horse Yak]}
{FD.distinct [Blend BlueMaster Dunhill PallMall Prince]}
English =: Red
Swede =: Dog
Dane =: Tea
Green =: White - 1
/*Green <: White*/
Coffee =: Green
PallMall =: Birds
Yellow =: Dunhill
Milk =: 3
Norwegian =: 1
{FD.distance Blend Cats '=:' 1}
{FD.distance Horse Dunhill '=:' 1}
BlueMaster =: Beer
German =: Prince
{FD.distance Norwegian Blue '=:' 1}
{FD.distance Water Blend '=:' 1}
{FD.distribute ff Root}
end

{ExploreAll Log}

 
The execution of this takes very little time indeed, since Mozart is able to find a unique solution just by applying its constraint 'propagators' with no need for 'distribution' -- if you were doing this puzzle on paper, that's like getting the answer without even having to say to yourself "let's suppose that the Horse is in house number 3" and seeing if it leads to a solution or not.


Edited by - Arnold Fribble on 07/16/2002 05:36:25
Go to Top of Page

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 07/16/2002 :  09:41:51  Show Profile  Reply with Quote
quote:

By comparison, the original query (using a SELECT *, a permanent table for the numbers and sprinkled with lot of AS) run on Access 2000 takes my machine about 45 seconds


I tried this in Access 95, just on a whim and it takes 5 seconds on the same machine.
Weird!


Go to Top of Page

graz
Chief SQLTeam Crack Dealer

USA
4137 Posts

Posted - 07/16/2002 :  09:44:43  Show Profile  Visit graz's Homepage  Reply with Quote
Nice post Arnold! I should have let you write my article. It would have saved me a lot of time. So when are you going to write an article for the site?

===============================================
Creating tomorrow's legacy systems today.
One crisis at a time.
Go to Top of Page

juggler
Starting Member

9 Posts

Posted - 07/18/2002 :  12:37:02  Show Profile  Reply with Quote
Wow! And Wow again!

What a great solution in so many ways.

Very impressive... and humbling. I thought my solution was slick because it only uses one create, one insert, and one select, but mine has four times as much code and is about as elegant as yak poop compared to Arnold's.

Thanks Rob for a great excuse to stretch my brain, and thanks Arnold for taking the time to show the rest of us how it's done.

According to the original article:
quote:
The winner will receive a custom SQL Team title, either their own choice or a special one created by the SQL Teamers! Any suggestions for a custom title can also be emailed.
Did this part happen?
Go to Top of Page

graz
Chief SQLTeam Crack Dealer

USA
4137 Posts

Posted - 07/18/2002 :  14:07:47  Show Profile  Visit graz's Homepage  Reply with Quote
Not yet. setbased and Arnold are both due a title. They can request something or we'll dream something up for them here pretty soon.

===============================================
Creating tomorrow's legacy systems today.
One crisis at a time.
Go to Top of Page

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 07/18/2002 :  14:32:16  Show Profile  Reply with Quote
"Yak-finder General" would have been my preferred designation, were it not for the fact that we already have "Fiendish Yak Riding Post Master General". And that Matthew Hopkins wasn't a very nice man.



Go to Top of Page

Page47
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 07/18/2002 :  15:13:54  Show Profile  Reply with Quote
Every other post by frib sends me to google to search for one thing or another. Matthew Hopkins.... Somebody has to keep us wipper-snappers honest, I guess...

<O>
Go to Top of Page

graz
Chief SQLTeam Crack Dealer

USA
4137 Posts

Posted - 07/18/2002 :  18:44:38  Show Profile  Visit graz's Homepage  Reply with Quote
quote:

"Yak-finder General" would have been my preferred designation, were it not for the fact that we already have "Fiendish Yak Riding Post Master General". And that Matthew Hopkins wasn't a very nice man.



Done. And actually the Post Master General title is gone. There's a new one if anyone else gets to 1,000 posts.

===============================================
Creating tomorrow's legacy systems today.
One crisis at a time.
Go to Top of Page

AjarnMark
SQL Slashing Gunting Master

USA
3246 Posts

Posted - 07/19/2002 :  17:27:32  Show Profile  Visit AjarnMark's Homepage  Reply with Quote
What about a nickname for Arnold? Something like SQL Brain-stretcher.

Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.16 seconds. Powered By: Snitz Forums 2000