Re: Whose Fish?
- From: Jordan Marr <jnmarr@xxxxxxxxxxx>
- Date: 24 May 2007 18:20:05 -0700
On May 24, 5:52 pm, Mark Jeffcoat <jeffc...@xxxxxxxxxxxxxxx> wrote:
Jordan Marr <jnm...@xxxxxxxxxxx> 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
.
- Prev by Date: Re: Midget amongst Eagles
- Next by Date: Re: PostgreSQL or MySQL ? - YOU WIN! BEST TOPIC TROLL OF MAY
- Previous by thread: Midget amongst Eagles
- Next by thread: Re: Whose Fish?
- Index(es):
Relevant Pages
|
|
