Das Yak ist Deutsch (RC #3)

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

Which is probably one of the oddest titled articles on the site. And after working on a solution myself and reviewing the ones submitted I know why Rob didn't want to write these articles. We have some devious, creative SQL coders out there.

Rob started this Reader Challenge in late March 2002. We got our answers back a week later. We had 8 T-SQL solutions submitted and one Prolog solution. Thanks to Jonathon Boott (setbasedisthetruepath), Arnold Fribble (Arnold Fribble), David Greene, Jason White (Page47), Jason, Shawn Brant, Alexander Netrebchenko and Peter de Boer. Peter, you get the bonus points for "originality & innovation" but lose them right back for submitting a Prolog solution. And yes, there is a SQL solution that's that easy. But that will be a follow up article.

In this article I'm going to cover the first of two sample solutions. The first is what I'd call a traditional approach. The second is a little more complex and a lot more "sqlicious". I'll cover it in the next article.

Jonathon Boott (setbasedisthetruepath) submitted the first solution that solved the problem. You can download the full script if you'd like to run it. I'm only going to highlight parts. He started by creating a temporary table that looked like this:

create table #temp
(
	ancestry varchar(50),
	pet varchar(50),
	drink varchar(50),
	housecolor varchar(50),
	houseposition varchar(50),
	smoke varchar(50)
)

Next he populated it with every possible solution using a bunch of unions and cross-joins:

insert #temp ( ancestry, pet, drink, housecolor, houseposition, smoke )
	select ancestry, pet, drink, housecolor, houseposition, smoke
	from (
		select 'English' as ancestry union
		select 'German' union
		select 'Swede' union
		select 'Dane' union
		select 'Norwegian') as a
		cross join (
			select 'Cat' as pet union
			select 'Dog' union
			select 'Horse' union
			select 'Bird' union
			select 'Yak!!'
			) as b
		cross join (
			select 'Tea' as drink union
			select 'Milk' union
			select 'Coffee' union
			select 'Water' union
			select 'Beer' ) as c
		cross join (
			select 'Red' as housecolor union
			select 'Green' union
			select 'White' union
			select 'Yellow' union
			select 'Blue' ) as d
		cross join (
			select '1' as houseposition union
			select '2' union
			select '3' union
			select '4' union
			select '5' ) as e
		cross join (
			select 'Pall Mall' as smoke union
			select 'Prince' union
			select 'Blue Master' union
			select 'Blend' union
			select 'Dunhill') as f

This created a table with 15,625 possible solutions. Then he began to work through the rules. The first rule was the English man lives in the red house. He deleted every row where the English man wasn't in a red house:

delete #temp where ancestry = 'english' and housecolor != 'red'
delete #temp where ancestry != 'english' and housecolor = 'red'

Each of these delete statements removed 2,500 rows. He went through all the easy rules this way until he got to the Norwegian living next to the blue house. Now his solution will have to take two rows into account. He solved that by using this bit of SQL:

delete #temp 
where housecolor = 'blue' 
and abs( cast(houseposition as int) 
	- cast( ( select distinct houseposition
		  from #temp 
		  where ancestry = 'norwegian' ) as int) ) != 1

delete #temp 
where housecolor != 'blue' 
and abs( cast(houseposition as int)
	- cast( ( select distinct houseposition 
		  from #temp 
		  where ancestry = 'norwegian' ) as int) ) = 1

One question I've been asking myself is whether he could have used an integer for house position. We'll leave that to the forums and the author of the script. The first statement deleted all the blue/Norwegian combinations that weren't next to each other. The second statement deletes all the houses next to the Norwegian that aren't blue.

This statement is a little tricky. Earlier there was a rule that said the Norwegian lived in the first house. Thus the author knew that his query in the WHERE clause would only return one value. If it returns two values, the query fails. This is a problem I wrestled with when I worked on my solution.

Next, the author handles the remaining "next to" rules. The first is that they drink water next to where they smoke blends. He actually puts all these rules inside a WHILE loop. The loop runs until there are only five records left. Here's a simplified version of it:

while ( select count(*) from #temp ) != 5
begin
	delete #temp
	from #temp t
	where t.smoke = 'blend' 
	and not exists (
		select 1
		from #temp
		where smoke != 'blend' 
		and drink = 'water' 
		and abs( cast(houseposition as int) - 
                    cast(t.houseposition as int) ) = 1 )

        -- delete statements for other "next to" rules go here

end

Why does this run inside a WHILE loop? The first time this loop runs, the blend smoker could be in any house so we can't eliminate anything. Let's say that another rule in this loop eliminated blend from the fifth house. When this rule runs again, it will eliminate possibilities that have water in the fourth house.

There is also a second type of DELETE that runs inside the loop. It looks like this:

delete #temp
from #temp t
	inner join (
		select houseposition, max(drink) as drink
		from #temp
		group by houseposition
		having count(distinct drink) = 1 ) as d 
        on t.drink = d.drink
where t.houseposition != d.houseposition

And this is a darn neat piece of SQL. The inner SELECT returns every drink that we know the position for. If I modify it a little and run this:

select houseposition, max(drink) as drink, count(*)
from #temp
group by houseposition
having count(distinct drink) = 1

it returns this the first time through the loop:

houseposition             drink                                
------------------------- ------------------------ ----------- 
1                         Water                    2
3                         Milk                     3

We see that the only remaining values of drink for houseposition = 1 are water (ignore the milk for now). There happen to be two possible scenarios where water is drunk in the first house. But this select tells us there is no other value besides water that remains for this house therefore, water must be drunk in the first house. So any other houseposition that has water in it is incorrect and should be deleted. The same with milk in the third house.

This recordset is used to delete all the records where the drink is equal (i.e. water) and the housepositions aren't equal (i.e. not equal 1). Pretty darn slick if you ask me. There's a query like this for each parameter -- drink, smoke, pet, nationality and color. As more and more rows are removed, these queries will identify more and more rows.

Once the loop completes and there are five rows left we've got our solution:

ancestry   pet        drink      housecolor houseposition smoke        
---------- ---------- ---------- ---------- ------------- ------------ 
Dane       Horse      Tea        Blue       2             Blend
Swede      Dog        Beer       White      5             Blue Master
Norwegian  Cat        Water      Yellow     1             Dunhill
English    Bird       Milk       Red        3             Pall Mall
German     Yak!!      Coffee     Green      4             Prince

(5 row(s) affected)

And we see that the German owns the Yak. Thanks for all of you that took the time to submit solutions. I'll highlight another one in the next article.