Re: Whose Fish?

#1

Jordan Marr <jnmarr (AT) hotmail (DOT) com> writes:

Quote:

http://www.coudal.com/thefish.php

I was once given this question at a job interview (my boss liked to
stress people out). Although I didn't finish the question during the
interview, I still got the job.

So this weekend I created an OO program that solves the problem within
1 to 29 seconds, depending on what order my attributes are initially
entered.

Mine is totally OO and uses no relation database at all, however, it
seems like a great problem to throw at a relational database, which I
would guess may be able to solve it faster.

Any takers? <ahem> ;^)

I decided to try this, as an SQL exercise. I took
me a couple of hours to get right, and I'm not entirely
happy with my solution, so I'm going to post the entire
thing. Comments are interspersed, especially where I think
I've done something particularly awkward. I'd appreciate
any suggestions you may have on how to make this solution
cleaner, or even on completely different (yet still legal
SQL) approaches.

(Developed and tested against PostgreSQL, though I've tried
to avoid anything non-standard.)

/*
First, I establish the entire space of houses that
we're working in:
*/
-- 1 far left, 5 far right.
CREATE TABLE ordinal AS
VALUES (1), (2), (3), (4), (5);

CREATE TABLE country AS
VALUES ('Britain'), ('Switzerland'), ('Denmark'),
('Norway'), ('Germany');

CREATE TABLE color AS
VALUES ('red'), ('green'), ('yellow'), ('blue'), ('white');

CREATE TABLE drink AS
VALUES ('beer'), ('water'), ('tea'), ('coffee'), ('milk');

CREATE TABLE pet AS
VALUES ('pike'), ('dog'), ('cat'), ('bird'), ('horse');

CREATE TABLE cigar AS
VALUES ('Pall Mall'), ('Dunhill'), ('Prince'),
('Bluemaster'), ('Blend');

ALTER TABLE ordinal ADD PRIMARY KEY (column1);
ALTER TABLE color ADD PRIMARY KEY (column1);
ALTER TABLE country ADD PRIMARY KEY (column1);
ALTER TABLE pet ADD PRIMARY KEY (column1);
ALTER TABLE drink ADD PRIMARY KEY (column1);
ALTER TABLE cigar ADD PRIMARY KEY (column1);

CREATE VIEW conceivable_house (color, country, drink, pet, cigar, position)
AS (SELECT * FROM color CROSS JOIN country CROSS JOIN drink
CROSS JOIN pet CROSS JOIN cigar CROSS JOIN ordinal);

/*
There are 15625 conceivable houses, but many of them
are eliminated by the constraints. In this first step, I
only consider the constraints that apply to one house at
at time:

*/

-- Ends up being 133 rows:
CREATE VIEW constrained_house AS
(SELECT DISTINCT * from conceivable_house
WHERE ((color != 'red' AND country != 'Britain')
OR (color = 'red' AND country = 'Britain'))
AND
((pet != 'dog' AND country != 'Switzerland')
OR (pet = 'dog' AND country = 'Switzerland'))
AND
((country != 'Denmark' AND drink != 'tea')
OR (country = 'Denmark' AND drink = 'tea'))
AND /* Constraint 5: */
((color != 'green' AND drink != 'coffee')
OR (color = 'green' AND drink = 'coffee'))
AND
((cigar != 'Pall Mall' AND pet != 'bird')
OR (cigar = 'Pall Mall' AND pet = 'bird'))
AND
((cigar != 'Dunhill' AND color != 'yellow')
OR (cigar = 'Dunhill' AND color = 'yellow'))
AND
((position != 3 AND drink != 'milk')
OR (position = 3 AND drink = 'milk'))
AND /* 10 */
((position != 1 AND country != 'Norway')
OR (position = 1 AND country = 'Norway'))
AND
((cigar != 'Bluemaster' AND drink != 'beer')
OR (cigar = 'Bluemaster' AND drink = 'beer'))
AND
((country != 'Germany' AND cigar != 'Prince')
OR (country = 'Germany' AND cigar = 'Prince'))
);

/*
Now I apply the constraints that apply to pairs of
houses, and the constraint that distributes colors,
nationalities, etc.
*/
SELECT DISTINCT * FROM constrained_house a
JOIN constrained_house b ON (b.position = 2)
JOIN constrained_house c ON (c.position = 3)
JOIN constrained_house d ON (d.position = 4)
JOIN constrained_house e ON (e.position = 5)
WHERE
a.position = 1
/*
This double array inclusion was the best way I could
find to test for set equality. I couldn't find a way
to avoid re-listing the contents of the color, drink, etc.
tables.
*/
AND (array[a.color, b.color, c.color, d.color, e.color]
@> array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.color, b.color, c.color, d.color, e.color]
<@ array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
@> array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
<@ array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
@> array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
<@ array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
@> array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
<@ array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])

AND
(array[a.country, b.country, c.country, d.country, e.country]
<@ array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])
AND
(array[a.country, b.country, c.country, d.country, e.country]
@> array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])

/*
Here I start the multi-house constraints. Listing every
possible combination seems .. bad, and only doable because
5 is a just-barely-small-enough number, but I can't figure
out any more elegant way to do this:
*/

-- 4. The green house is on the left of the white house.
/* [ I initially interpreted this as "the green house is in any
position to the left of the white house", and came up with
seven distinct solutions. ]
*/
AND (a.color != 'green' OR b.color = 'white')
AND (b.color != 'green' OR c.color = 'white')
AND (c.color != 'green' OR d.color = 'white')
AND (d.color != 'green' OR e.color = 'white')
AND (e.color != 'green')

-- 9. The man who smokes Blends lives next to the one who keeps cats.
AND (a.cigar != 'Blend' OR b.pet = 'cat')
AND (b.cigar != 'Blend' OR (a.pet = 'cat' OR c.pet = 'cat'))
AND (c.cigar != 'Blend' OR (b.pet = 'cat' OR d.pet = 'cat'))
AND (d.cigar != 'Blend' OR (c.pet = 'cat' OR e.pet = 'cat'))
AND (e.cigar != 'Blend' OR d.pet = 'cat')

-- 11. The man who keeps horses lives next to the one who smokes Dunhills.
AND (a.pet != 'horse' OR b.cigar = 'Dunhill')
AND (b.pet != 'horse' OR (a.cigar = 'Dunhill' OR c.cigar = 'Dunhill'))
AND (c.pet != 'horse' OR (b.cigar = 'Dunhill' OR d.cigar = 'Dunhill'))
AND (d.pet != 'horse' OR (c.cigar = 'Dunhill' OR e.cigar = 'Dunhill'))
AND (e.pet != 'horse' OR d.cigar = 'Dunhill')

-- 14 The Norwegian lives next to the blue house.
AND (a.country != 'Norway' OR b.color = 'blue')
AND (b.country != 'Norway' OR (a.color = 'blue' OR c.color = 'blue'))
AND (c.country != 'Norway' OR (b.color = 'blue' OR d.color = 'blue'))
AND (d.country != 'Norway' OR (c.color = 'blue' OR e.color = 'blue'))
AND (e.country != 'Norway' OR d.color = 'blue')

-- 15. The man who smokes Blends has a neighbor who drinks water.

AND (a.cigar != 'Blend' OR b.drink = 'water')
AND (b.cigar != 'Blend' OR (a.drink = 'water' OR c.drink = 'water'))
AND (c.cigar != 'Blend' OR (b.drink = 'water' OR d.drink = 'water'))
AND (d.cigar != 'Blend' OR (c.drink = 'water' OR e.drink = 'water'))
AND (e.cigar != 'Blend' OR d.drink = 'water')
;

--
Mark Jeffcoat
Austin, TX

#2

On May 24, 5:52 pm, Mark Jeffcoat <jeffc... (AT) alumni (DOT) rice.edu> wrote:

Quote:

Jordan Marr <jnm... (AT) hotmail (DOT) com> writes:
http://www.coudal.com/thefish.php

I was once given this question at a job interview (my boss liked to
stress people out). Although I didn't finish the question during the
interview, I still got the job.

So this weekend I created an OO program that solves the problem within
1 to 29 seconds, depending on what order my attributes are initially
entered.

Mine is totally OO and uses no relation database at all, however, it
seems like a great problem to throw at a relational database, which I
would guess may be able to solve it faster.

Any takers? <ahem> ;^)

I decided to try this, as an SQL exercise. I took
me a couple of hours to get right, and I'm not entirely
happy with my solution, so I'm going to post the entire
thing. Comments are interspersed, especially where I think
I've done something particularly awkward. I'd appreciate
any suggestions you may have on how to make this solution
cleaner, or even on completely different (yet still legal
SQL) approaches.

(Developed and tested against PostgreSQL, though I've tried
to avoid anything non-standard.)

/*
First, I establish the entire space of houses that
we're working in:
*/
-- 1 far left, 5 far right.
CREATE TABLE ordinal AS
VALUES (1), (2), (3), (4), (5);

CREATE TABLE country AS
VALUES ('Britain'), ('Switzerland'), ('Denmark'),
('Norway'), ('Germany');

CREATE TABLE color AS
VALUES ('red'), ('green'), ('yellow'), ('blue'), ('white');

CREATE TABLE drink AS
VALUES ('beer'), ('water'), ('tea'), ('coffee'), ('milk');

CREATE TABLE pet AS
VALUES ('pike'), ('dog'), ('cat'), ('bird'), ('horse');

CREATE TABLE cigar AS
VALUES ('Pall Mall'), ('Dunhill'), ('Prince'),
('Bluemaster'), ('Blend');

ALTER TABLE ordinal ADD PRIMARY KEY (column1);
ALTER TABLE color ADD PRIMARY KEY (column1);
ALTER TABLE country ADD PRIMARY KEY (column1);
ALTER TABLE pet ADD PRIMARY KEY (column1);
ALTER TABLE drink ADD PRIMARY KEY (column1);
ALTER TABLE cigar ADD PRIMARY KEY (column1);

CREATE VIEW conceivable_house (color, country, drink, pet, cigar, position)
AS (SELECT * FROM color CROSS JOIN country CROSS JOIN drink
CROSS JOIN pet CROSS JOIN cigar CROSS JOIN ordinal);

/*
There are 15625 conceivable houses, but many of them
are eliminated by the constraints. In this first step, I
only consider the constraints that apply to one house at
at time:

*/

-- Ends up being 133 rows:
CREATE VIEW constrained_house AS
(SELECT DISTINCT * from conceivable_house
WHERE ((color != 'red' AND country != 'Britain')
OR (color = 'red' AND country = 'Britain'))
AND
((pet != 'dog' AND country != 'Switzerland')
OR (pet = 'dog' AND country = 'Switzerland'))
AND
((country != 'Denmark' AND drink != 'tea')
OR (country = 'Denmark' AND drink = 'tea'))
AND /* Constraint 5: */
((color != 'green' AND drink != 'coffee')
OR (color = 'green' AND drink = 'coffee'))
AND
((cigar != 'Pall Mall' AND pet != 'bird')
OR (cigar = 'Pall Mall' AND pet = 'bird'))
AND
((cigar != 'Dunhill' AND color != 'yellow')
OR (cigar = 'Dunhill' AND color = 'yellow'))
AND
((position != 3 AND drink != 'milk')
OR (position = 3 AND drink = 'milk'))
AND /* 10 */
((position != 1 AND country != 'Norway')
OR (position = 1 AND country = 'Norway'))
AND
((cigar != 'Bluemaster' AND drink != 'beer')
OR (cigar = 'Bluemaster' AND drink = 'beer'))
AND
((country != 'Germany' AND cigar != 'Prince')
OR (country = 'Germany' AND cigar = 'Prince'))
);

/*
Now I apply the constraints that apply to pairs of
houses, and the constraint that distributes colors,
nationalities, etc.
*/
SELECT DISTINCT * FROM constrained_house a
JOIN constrained_house b ON (b.position = 2)
JOIN constrained_house c ON (c.position = 3)
JOIN constrained_house d ON (d.position = 4)
JOIN constrained_house e ON (e.position = 5)
WHERE
a.position = 1
/*
This double array inclusion was the best way I could
find to test for set equality. I couldn't find a way
to avoid re-listing the contents of the color, drink, etc.
tables.
*/
AND (array[a.color, b.color, c.color, d.color, e.color]
@> array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.color, b.color, c.color, d.color, e.color]
@ array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
@> array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
@ array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
@> array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
@ array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
@> array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
@ array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])

AND
(array[a.country, b.country, c.country, d.country, e.country]
@ array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])
AND
(array[a.country, b.country, c.country, d.country, e.country]
@> array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])

/*
Here I start the multi-house constraints. Listing every
possible combination seems .. bad, and only doable because
5 is a just-barely-small-enough number, but I can't figure
out any more elegant way to do this:
*/

-- 4. The green house is on the left of the white house.
/* [ I initially interpreted this as "the green house is in any
position to the left of the white house", and came up with
seven distinct solutions. ]
*/
AND (a.color != 'green' OR b.color = 'white')
AND (b.color != 'green' OR c.color = 'white')
AND (c.color != 'green' OR d.color = 'white')
AND (d.color != 'green' OR e.color = 'white')
AND (e.color != 'green')

-- 9. The man who smokes Blends lives next to the one who keeps cats.
AND (a.cigar != 'Blend' OR b.pet = 'cat')
AND (b.cigar != 'Blend' OR (a.pet = 'cat' OR c.pet = 'cat'))
AND (c.cigar != 'Blend' OR (b.pet = 'cat' OR d.pet = 'cat'))
AND (d.cigar != 'Blend' OR (c.pet = 'cat' OR e.pet = 'cat'))
AND (e.cigar != 'Blend' OR d.pet = 'cat')

-- 11. The man who keeps horses lives next to the one who smokes Dunhills.
AND (a.pet != 'horse' OR b.cigar = 'Dunhill')
AND (b.pet != 'horse' OR (a.cigar = 'Dunhill' OR c.cigar = 'Dunhill'))
AND (c.pet != 'horse' OR (b.cigar = 'Dunhill' OR d.cigar = 'Dunhill'))
AND (d.pet != 'horse' OR (c.cigar = 'Dunhill' OR e.cigar = 'Dunhill'))
AND (e.pet != 'horse' OR d.cigar = 'Dunhill')

-- 14 The Norwegian lives next to the blue house.
AND (a.country != 'Norway' OR b.color = 'blue')
AND (b.country != 'Norway' OR (a.color = 'blue' OR c.color = 'blue'))
AND (c.country != 'Norway' OR (b.color = 'blue' OR d.color = 'blue'))
AND (d.country != 'Norway' OR (c.color = 'blue' OR e.color = 'blue'))
AND (e.country != 'Norway' OR d.color = 'blue')

-- 15. The man who smokes Blends has a neighbor who drinks water.

AND (a.cigar != 'Blend' OR b.drink = 'water')
AND (b.cigar != 'Blend' OR (a.drink = 'water' OR c.drink = 'water'))
AND (c.cigar != 'Blend' OR (b.drink = 'water' OR d.drink = 'water'))
AND (d.cigar != 'Blend' OR (c.drink = 'water' OR e.drink = 'water'))
AND (e.cigar != 'Blend' OR d.drink = 'water')
;

--
Mark Jeffcoat
Austin, TX- Hide quoted text -

- Show quoted text -

Cool... You're the man! (I'm assuming this comes up with the correct
answer).
How long does it take to solve?

I will comment tomorrow when I have more time..

Jordan

#3

Quote:

I decided to try this, as an SQL exercise. I took
me a couple of hours to get right, and I'm not entirely
happy with my solution, so I'm going to post the entire
thing. Comments are interspersed, especially where I think
I've done something particularly awkward. I'd appreciate
any suggestions you may have on how to make this solution
cleaner, or even on completely different (yet still legal
SQL) approaches.

Nice job Mark! That is a very creative solution!
How long does it take to process?

Jordan

#4

Jordan Marr <jnmarr (AT) hotmail (DOT) com> writes:

Quote:

I decided to try this, as an SQL exercise. I took
me a couple of hours to get right, and I'm not entirely
happy with my solution, so I'm going to post the entire
thing. Comments are interspersed, especially where I think
I've done something particularly awkward. I'd appreciate
any suggestions you may have on how to make this solution
cleaner, or even on completely different (yet still legal
SQL) approaches.

Nice job Mark! That is a very creative solution!
How long does it take to process?

Thank you. Good fun.

The whole thing takes about 6 seconds; about half
in disk I/O in the (tiny) CREATE TABLEs at the
beginning, and half in the giant SELECT that finds
the answer.

(Measured on an elderly 2.5GHz Celeron machine running
PostgreSQL. Your mileage may vary.)

From looking at the query plan, if I were asked to
optimize the query, my best strategy is to change
my name and move to another country.

--
Mark Jeffcoat
Austin, TX

#5

I've already replied to this post twice, but Google is eating messages
again. So at the very likely risk of duplicate postings, here goes...

Mark, you're the man! Your design is very creative. I am assuming it
yields the correct answer (?).
How long does it take to process?

Jordan

#6

Quote:

http://www.coudal.com/thefish.php

An alternative low-tech method (sudoku style):

Label 25 small post-it notes with specified items. Arrange them in a
5x5 grid where each column correlates to characteristics of a house/
person. First use provided clues to determine position of houses. Then
position notes labeled blend/water/cat in valid columns. Next position
remaining note pairs to determine position of final note labeled pike.
To reduce number of iterations, first solve columns with most number
of knowns. Most iterations quickly lead to invalid scenarios.

#7

Google keeps eating my posts, so I appologize in advance for any
duplicates...

Mark, your solution is very creative! I'm assuming it returns the
correct answer (?).
How long does it take to process?

Jordan

#8

Mark Jeffcoat <jeffcoat (AT) alumni (DOT) rice.edu> wrote:

[snip]

Quote:

From looking at the query plan, if I were asked to
optimize the query, my best strategy is to change
my name and move to another country.

Why optimise a one-shot? It is not as if it was taking minutes
or hours.

I think I am going to play with this some. I did something
similar once with another type of logic problem, but I used xBASE
record-based commands instead of SQL.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.

#9

Very nice. I know this as the Gnu Puzzle or "Einstein problem" and i
never got it right!!

#10

On May 24, 5:52 pm, Mark Jeffcoat <jeffc... (AT) alumni (DOT) rice.edu> wrote:

Quote:

Jordan Marr <jnm... (AT) hotmail (DOT) com> writes:
http://www.coudal.com/thefish.php

I was once given this question at a job interview (my boss liked to
stress people out). Although I didn't finish the question during the
interview, I still got the job.

So this weekend I created an OO program that solves the problem within
1 to 29 seconds, depending on what order my attributes are initially
entered.

Mine is totally OO and uses no relation database at all, however, it
seems like a great problem to throw at a relational database, which I
would guess may be able to solve it faster.

Any takers? <ahem> ;^)

I decided to try this, as an SQL exercise. I took
me a couple of hours to get right, and I'm not entirely
happy with my solution, so I'm going to post the entire
thing. Comments are interspersed, especially where I think
I've done something particularly awkward. I'd appreciate
any suggestions you may have on how to make this solution
cleaner, or even on completely different (yet still legal
SQL) approaches.

(Developed and tested against PostgreSQL, though I've tried
to avoid anything non-standard.)

/*
First, I establish the entire space of houses that
we're working in:
*/
-- 1 far left, 5 far right.
CREATE TABLE ordinal AS
VALUES (1), (2), (3), (4), (5);

CREATE TABLE country AS
VALUES ('Britain'), ('Switzerland'), ('Denmark'),
('Norway'), ('Germany');

CREATE TABLE color AS
VALUES ('red'), ('green'), ('yellow'), ('blue'), ('white');

CREATE TABLE drink AS
VALUES ('beer'), ('water'), ('tea'), ('coffee'), ('milk');

CREATE TABLE pet AS
VALUES ('pike'), ('dog'), ('cat'), ('bird'), ('horse');

CREATE TABLE cigar AS
VALUES ('Pall Mall'), ('Dunhill'), ('Prince'),
('Bluemaster'), ('Blend');

ALTER TABLE ordinal ADD PRIMARY KEY (column1);
ALTER TABLE color ADD PRIMARY KEY (column1);
ALTER TABLE country ADD PRIMARY KEY (column1);
ALTER TABLE pet ADD PRIMARY KEY (column1);
ALTER TABLE drink ADD PRIMARY KEY (column1);
ALTER TABLE cigar ADD PRIMARY KEY (column1);

CREATE VIEW conceivable_house (color, country, drink, pet, cigar, position)
AS (SELECT * FROM color CROSS JOIN country CROSS JOIN drink
CROSS JOIN pet CROSS JOIN cigar CROSS JOIN ordinal);

/*
There are 15625 conceivable houses, but many of them
are eliminated by the constraints. In this first step, I
only consider the constraints that apply to one house at
at time:

*/

-- Ends up being 133 rows:
CREATE VIEW constrained_house AS
(SELECT DISTINCT * from conceivable_house
WHERE ((color != 'red' AND country != 'Britain')
OR (color = 'red' AND country = 'Britain'))
AND
((pet != 'dog' AND country != 'Switzerland')
OR (pet = 'dog' AND country = 'Switzerland'))
AND
((country != 'Denmark' AND drink != 'tea')
OR (country = 'Denmark' AND drink = 'tea'))
AND /* Constraint 5: */
((color != 'green' AND drink != 'coffee')
OR (color = 'green' AND drink = 'coffee'))
AND
((cigar != 'Pall Mall' AND pet != 'bird')
OR (cigar = 'Pall Mall' AND pet = 'bird'))
AND
((cigar != 'Dunhill' AND color != 'yellow')
OR (cigar = 'Dunhill' AND color = 'yellow'))
AND
((position != 3 AND drink != 'milk')
OR (position = 3 AND drink = 'milk'))
AND /* 10 */
((position != 1 AND country != 'Norway')
OR (position = 1 AND country = 'Norway'))
AND
((cigar != 'Bluemaster' AND drink != 'beer')
OR (cigar = 'Bluemaster' AND drink = 'beer'))
AND
((country != 'Germany' AND cigar != 'Prince')
OR (country = 'Germany' AND cigar = 'Prince'))
);

/*
Now I apply the constraints that apply to pairs of
houses, and the constraint that distributes colors,
nationalities, etc.
*/
SELECT DISTINCT * FROM constrained_house a
JOIN constrained_house b ON (b.position = 2)
JOIN constrained_house c ON (c.position = 3)
JOIN constrained_house d ON (d.position = 4)
JOIN constrained_house e ON (e.position = 5)
WHERE
a.position = 1
/*
This double array inclusion was the best way I could
find to test for set equality. I couldn't find a way
to avoid re-listing the contents of the color, drink, etc.
tables.
*/
AND (array[a.color, b.color, c.color, d.color, e.color]
@> array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.color, b.color, c.color, d.color, e.color]
@ array['blue', 'green', 'yellow', 'red', 'white'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
@> array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.drink, b.drink, c.drink, d.drink, e.drink]
@ array['beer', 'water', 'tea', 'coffee', 'milk'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
@> array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.pet, b.pet, c.pet, d.pet, e.pet]
@ array['pike', 'dog', 'cat', 'bird', 'horse'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
@> array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])
AND
(array[a.cigar, b.cigar, c.cigar, d.cigar, e.cigar]
@ array['Pall Mall', 'Dunhill', 'Prince', 'Bluemaster', 'Blend'])

AND
(array[a.country, b.country, c.country, d.country, e.country]
@ array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])
AND
(array[a.country, b.country, c.country, d.country, e.country]
@> array['Britain', 'Switzerland', 'Denmark', 'Norway', 'Germany'])

/*
Here I start the multi-house constraints. Listing every
possible combination seems .. bad, and only doable because
5 is a just-barely-small-enough number, but I can't figure
out any more elegant way to do this:
*/

-- 4. The green house is on the left of the white house.
/* [ I initially interpreted this as "the green house is in any
position to the left of the white house", and came up with
seven distinct solutions. ]
*/
AND (a.color != 'green' OR b.color = 'white')
AND (b.color != 'green' OR c.color = 'white')
AND (c.color != 'green' OR d.color = 'white')
AND (d.color != 'green' OR e.color = 'white')
AND (e.color != 'green')

-- 9. The man who smokes Blends lives next to the one who keeps cats.
AND (a.cigar != 'Blend' OR b.pet = 'cat')
AND (b.cigar != 'Blend' OR (a.pet = 'cat' OR c.pet = 'cat'))
AND (c.cigar != 'Blend' OR (b.pet = 'cat' OR d.pet = 'cat'))
AND (d.cigar != 'Blend' OR (c.pet = 'cat' OR e.pet = 'cat'))
AND (e.cigar != 'Blend' OR d.pet = 'cat')

-- 11. The man who keeps horses lives next to the one who smokes Dunhills.
AND (a.pet != 'horse' OR b.cigar = 'Dunhill')
AND (b.pet != 'horse' OR (a.cigar = 'Dunhill' OR c.cigar = 'Dunhill'))
AND (c.pet != 'horse' OR (b.cigar = 'Dunhill' OR d.cigar = 'Dunhill'))
AND (d.pet != 'horse' OR (c.cigar = 'Dunhill' OR e.cigar = 'Dunhill'))
AND (e.pet != 'horse' OR d.cigar = 'Dunhill')

-- 14 The Norwegian lives next to the blue house.
AND (a.country != 'Norway' OR b.color = 'blue')
AND (b.country != 'Norway' OR (a.color = 'blue' OR c.color = 'blue'))
AND (c.country != 'Norway' OR (b.color = 'blue' OR d.color = 'blue'))
AND (d.country != 'Norway' OR (c.color = 'blue' OR e.color = 'blue'))
AND (e.country != 'Norway' OR d.color = 'blue')

-- 15. The man who smokes Blends has a neighbor who drinks water.

AND (a.cigar != 'Blend' OR b.drink = 'water')
AND (b.cigar != 'Blend' OR (a.drink = 'water' OR c.drink = 'water'))
AND (c.cigar != 'Blend' OR (b.drink = 'water' OR d.drink = 'water'))
AND (d.cigar != 'Blend' OR (c.drink = 'water' OR e.drink = 'water'))
AND (e.cigar != 'Blend' OR d.drink = 'water')
;

--
Mark Jeffcoat
Austin, TX- Hide quoted text -

- Show quoted text -

Mark,

Nice job! Very creative. I'm assuming it returns the correct answer
(?).
How long does it take to process?

Jordan