9. Re: Need a Challenge?
Irv Mullins wrote:
> I found this puzzle in an example program
> for a language I downloaded. Can you write
> a program (100 lines or less, plz) to solve it?
I've included two versions. The first uses some pruning, so it doesn't take
forever. It's about 125 lines of code. The second works in theory - I
haven't had the patience to run it all the way through. But it's 100 lines
long. 
Basically, it's a brute force approach. 'calc_permutes' pre-calculates all
the combinations of {1..5}. 'main' loops through the entire search space,
looking for a match. 'test' checks to see if a particular combination
matches the criteria. If it does, the program halts. There are some pruning
tests to reduce the search space, so the redundant tests in test() are
commented out. Otherwise, it would be a *long* time to arrive at the answer.
as it is, it takes my P200 about 18 seconds to find the solution. The code
could be a lot more efficient, but it would take more lines, and I think
it's *sort* of explanatory, even without comments.
The answer is:
english red snail sculptor milk third
spanish white dog violinist juice fifth
japanese green zebra painter coffee fourth
italian blue horse doctor tea second
norwegian yellow fox diplomat water first
If you *really* want to speed it up, just change the constants to match the
solution. 
-- David Cuny
-- Version 1
sequence color, job, pet, drink, house, permutes, list
constant
colors = { "red", "green", "yellow", "white", "blue" },
nations = { "english", "spanish", "japanese", "italian", "norwegian" },
jobs = { "painter", "sculptor", "diplomat", "violinist", "doctor" },
pets = { "dog", "snail", "fox", "horse", "zebra" },
drinks = { "tea", "coffee", "milk", "juice", "water" },
houses = { "first", "second", "third", "fourth", "fifth" },
country = { 1, 2, 3, 4, 5 },
Red = 1, Green = 2, Yellow = 3, White = 4, Blue = 5,
English = 1, Spaniard = 2, Japanese = 3, Italian = 4, Norwegian = 5,
Painter = 1, Sculptor = 2, Diplomat = 3, Violinist = 4, Doctor = 5,
Dog = 1, Snail = 2, Fox = 3, Horse = 4, Zebra = 5,
Tea = 1, Coffee = 2, Milk = 3, Juice = 4, Water = 5
procedure calc_permutes( integer i, integer j )
if j = 0 then
-- initialize
permutes = {}
list = repeat( 0, i )
calc_permutes( i, j+1 )
elsif j > i then
permutes = append( permutes, list )
return
else
for k = 1 to i do
if list[k] = 0 then
list[k] = j
calc_permutes( i, j+1 )
list[k] = 0
end if
end for
end if
end procedure
function both( sequence s1, integer i1, sequence s2, integer i2 )
integer at
at = find( i1, s1 )
if at then
return s2[at] = i2
else
return 0
end if
end function
function nextTo( sequence s1, integer i1, sequence s2, integer i2 )
integer at1, at2
at1 = find( i1, s1 )
at2 = find( i2, s2 )
if at1 and at2 then
return ( house[at1] = house[at2]-1 or house[at1] = house[at2]+1 )
else
return 0
end if
end function
function onRight( sequence s1, integer i1, sequence s2, integer i2 )
integer at1, at2
at1 = find( i1, s1 )
at2 = find( i2, s2 )
return ( house[at1] = house[at2]-1 )
end function
procedure test()
if 1
-- and both( country, English, color, Red )
-- and both( country, Spaniard, pet, Dog )
-- and both( country, Japanese, job, Painter )
-- and both( country, Italian, drink, Tea )
-- and both( country, Norwegian, house, 1 )
and both( color, Green, drink, Coffee )
and onRight( color, Green, color, White )
and both( job, Sculptor, pet, Snail )
and both( job, Diplomat, color, Yellow )
and both( drink, Milk, house, 3 )
and nextTo( country, Norwegian, color, Blue )
and both( job, Violinist, drink, Juice )
and nextTo( pet, Fox, job, Doctor )
and nextTo( pet, Horse, job, Diplomat )
then
for i = 1 to 5 do
puts( 1, nations[i] & " " & colors[color[i]] & " " &
pets[pet[i]] & " " & jobs[job[i]] & " " &
drinks[drink[i]] & " " & houses[house[i]] & "\n" )
end for
abort(0)
end if
end procedure
procedure main()
calc_permutes( 5, 0 )
for colors = 1 to length( permutes ) do
color = permutes[colors]
if color[English] = Red then
for pets = 1 to length( permutes ) do
pet = permutes[pets]
if pet[Spaniard] = Dog then
for jobs = 1 to length( permutes ) do
job = permutes[jobs]
if job[Japanese] = Painter then
for drinks = 1 to length( permutes ) do
drink = permutes[drinks]
if drink[Italian] = Tea then
for houses = 1 to length( permutes ) do
house = permutes[houses]
if house[Norwegian] = 1 then
test()
end if
end for
end if
end for
end if
end for
end if
end for
end if
end for
end procedure
main()
-- Version 2: *very* slow
sequence color, job, pet, drink, house, permutes, list, matrix
constant
colors = { "red", "green", "yellow", "white", "blue" },
nations = { "english", "spanish", "japanese", "italian", "norwegian" },
jobs = { "painter", "sculptor", "diplomat", "violinist", "doctor" },
pets = { "dog", "snail", "fox", "horse", "zebra" },
drinks = { "tea", "coffee", "milk", "juice", "water" },
houses = { "first", "second", "third", "fourth", "fifth" },
country = { 1, 2, 3, 4, 5 },
Color = 1, Job = 2, Pet = 3, Drink = 4, House = 5,
Red = 1, Green = 2, Yellow = 3, White = 4, Blue = 5,
English = 1, Spaniard = 2, Japanese = 3, Italian = 4, Norwegian = 5,
Painter = 1, Sculptor = 2, Diplomat = 3, Violinist = 4, Doctor = 5,
Dog = 1, Snail = 2, Fox = 3, Horse = 4, Zebra = 5,
Tea = 1, Coffee = 2, Milk = 3, Juice = 4, Water = 5
procedure calc_permutes( integer i, integer j )
if j > i then
permutes = append( permutes, list )
return
else
for k = 1 to i do
if list[k] = 0 then
list[k] = j
calc_permutes( i, j+1 )
list[k] = 0
end if
end for
end if
end procedure
function both( sequence s1, integer i1, sequence s2, integer i2 )
integer at
at = find( i1, s1 )
if at then
return s2[at] = i2
end if
return 0
end function
function nextTo( sequence s1, integer i1, sequence s2, integer i2 )
integer at1, at2
at1 = find( i1, s1 )
at2 = find( i2, s2 )
if at1 and at2 then
return ( house[at1] = house[at2]-1 or house[at1] = house[at2]+1 )
end if
return 0
end function
function onRight( sequence s1, integer i1, sequence s2, integer i2 )
integer at1, at2
at1 = find( i1, s1 )
at2 = find( i2, s2 )
return ( house[at1] = house[at2]-1 )
end function
procedure test()
if both( country, English, matrix[Color], Red )
and both( country, Spaniard, matrix[Pet], Dog )
and both( country, Japanese, matrix[Job], Painter )
and both( country, Italian, matrix[Drink], Tea )
and both( country, Norwegian, matrix[House], 1 )
and both( matrix[Color], Green, matrix[Drink], Coffee )
and onRight( matrix[Color], Green, matrix[Color], White )
and both( matrix[Job], Sculptor, matrix[Pet], Snail )
and both( matrix[Job], Diplomat, matrix[Color], Yellow )
and both( matrix[Drink], Milk, matrix[House], 3 )
and nextTo( country, Norwegian, matrix[Color], Blue )
and both( matrix[Job], Violinist, matrix[Drink], Juice )
and nextTo( matrix[Pet], Fox, matrix[Job], Doctor )
and nextTo( matrix[Pet], Horse, matrix[Job], Diplomat )
then
for i = 1 to 5 do
puts( 1, nations[i] & " " & colors[matrix[Color][i]] & " " &
pets[matrix[Pet][i]] & " " & jobs[matrix[Job][i]] & " "
&
drinks[matrix[Drink][i]] & " " &
houses[matrix[House][i]] & "\n" )
end for
abort(0)
end if
end procedure
procedure search( integer index, integer max )
for i = 1 to length( permutes ) do
matrix[index] = permutes[i]
if index = max then
test()
else
search( index+1, max )
end if
end for
end procedure
permutes = {}
list = repeat( 0, 5 )
calc_permutes( 5, 1 )
matrix = repeat( {}, House )
search( 1, House )
15. Re: Need a Challenge?
On Thursday 16 August 2001 16:00, David Cuny wrote:
> OK, I ran the second version, and fixed a couple of bugs in it - I had
> forgotten to change house[] to matrix[House][] in some of the tests. It
> took about 1.3 hours to run, but it works correctly now.
Wow. The following pgm runs in about 24 seconds; of course, this
is a compiled language.
MODULE zebra;
CONST N = 5;
English = 1; Spaniard = 2; Japanese = 3; Italian = 4; Norwegian = 5;
Red = 1; Green = 2; White = 3; Yellow = 4; Blue = 5;
Painter = 1; Sculptor = 2; Diplomat = 3; Violinist = 4; Doctor = 5;
Dog = 1; Snails = 2; Fox = 3; Horse = 4; Zebra = 5;
Tea = 1; Coffee = 2; Milk = 3; Juice = 4; Water = 5;
TYPE T = [1..N];
ArrayT = ARRAY [1..N] OF [1..N];
VAR
Nat, (* [English, Spaniard, Japanese, Italian, Norwegian] *)
Color, (* [Red, Green, White, Yellow, Blue] *)
Profession, (* [Painter, Sculptor, Diplomat, Violinist, Doctor] *)
Pet, (* [Dog, Snails, Fox, Horse, Zebra] *)
Drink: (* [Tea, Coffee, Milk, Juice, Water] *)
ArrayT;
PROCEDURE generate(VAR x:ArrayT);
VAR i,j,k: T;
BEGIN
FOR i := 1 TO N DO
SOME j := 1 TO N DO
FOR k := 1 TO i-1 DO j <> x[k] END;
x[i] = j
END
END
END generate;
PROCEDURE zebra(VAR Nat, Color, Profession, Pet, Drink: ArrayT);
BEGIN
Nat[English] = Color[Red]; (* English = Red *)
Nat[Spaniard] = Pet[Dog]; (* Spaniard = Dog *)
Nat[Japanese] = Profession[Painter]; (* Japanese = Painter *)
Nat[Italian] = Drink[Tea]; (* Italian = Tea *)
Nat[Norwegian] = 1; (* Norwegian = 1 *)
Color[Green] = Drink[Coffee]; (* Green = Coffee *)
Color[Green] = Color[White] + 1; (* Green = White + 1 *)
Profession[Sculptor] = Pet[Snails]; (* Sculptor = Snails *)
Profession[Diplomat] = Color[Yellow]; (* Diplomat = Yellow *)
Drink[Milk] = 3; (* Milk = 3 *)
EITHER Nat[Norwegian] - Color[Blue] = 1
ORELSE Nat[Norwegian] - Color[Blue] = -1
END; (* |Norwegian - Blue| = 1 *)
Profession[Violinist] = Drink[Juice]; (* Violinist = Juice *)
EITHER Profession[Doctor] <> N; Pet[Fox] = Profession[Doctor] + 1
ORELSE Profession[Doctor] <> 1; Pet[Fox] = Profession[Doctor] - 1
END; (* |Doctor - Fox| = 1 *)
EITHER Profession[Diplomat] <> N; Pet[Horse] = Profession[Diplomat] + 1
ORELSE Profession[Diplomat] <> 1; Pet[Horse] = Profession[Diplomat] - 1
END (* |Diplomat - Horse| = 1 *)
END zebra;
VAR sol: T;
i: INTEGER;
BEGIN
FORALL
generate(Nat);
generate(Color);
generate(Profession);
zebra(Nat, Color, Profession, Pet, Drink);
generate(Pet);
generate(Drink);
DO
FOR i := 1 TO N DO
IF Profession[i] = Pet[Zebra]
THEN
WRITELN("Person with profession number ", Profession[i], " owns the
zebra.");
END;
IF Profession[i] = Drink[Water]
THEN
WRITELN("Person with profession number ", Profession[i], " drinks
water.");
END;
END
END
END zebra.
Regards,
Irv
25. Re: Need a Challenge?
Ok, I'm guessing that one or more people have already solved this
programming puzzle problem by now, but I'm still trying, and I have (at
least?) one problem:
I don't know how to deal with "relative position" information in my
code/data structure ("The Norwegian lives NEXT DOOR to the blue house.", or
"The green house is on the RIGHT of the white house.
"). I CAN utilize some of that info, minimally (assert: Norwegian CAN'T
live in blue house), but I can't put "+or- 1" in my data structure (for
"next to"), which seems to be throwing away info, which seems bad. And I
haven't figured out ANY way at all how to put "green position = white
position + 1" in my data structure.
What I have done is:
I have a reasonable algorithm for the puzzle, with a reasonable data
structure, I think;
I can choose and enter any info (except for relative position), including
"negative" info
(Norwegian house NOT blue) into the structure;
I can make info in one part of my structure be duplicated in parallel
"reverse" portions of it (eg, have things like "Nationality/Color" array,
AND "Color/Nationality" array, so I can enter all pairs of info; an entry in
one is auto duplicated properly in the "twin");
I can test all elements for "missing only one item", and fill in the missing
one
(ie, if something is: not this, not that, not this and that, etc, then MUST
be: the only remaining possibility); this is, I think, the main key to the
puzzle solution?
and I print out my data, and what is in the "Drink(water)/Nationality" and
"Pet(zebra)/Nationality" arrays.
I *may* have neglected to do that over & over again so newly filled in info
can be used to generate additional conclusions, and there *may* be other
logic tests I have also neglected to generate, and my code is LONG, and not
clear, too :( , but I am trying.
Any suggestions for how to deal with "relative positions"?
Dan Moyer
----- Original Message -----
From: "Irv Mullins" <irvm at ellijay.com>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, August 15, 2001 8:47 AM
Subject: Need a Challenge?
> >
> I found this puzzle in an example program for a language I downloaded.
> Can you write a program (100 lines or less, plz) to solve it?
>
> A small street has five differently colored houses on it. Five men
> of different nationalities live in these five houses. Each man has
> a different profession, each man likes a different drink, and each
> has a different pet animal. We have the following information:
>
> The Englishman lives in the red house.
> The Spaniard has a dog.
> The Japanese is a painter.
> The Italian drinks tea.
> The Norwegian lives in the first house on the left.
> The owner of the green house drinks coffee.
> The green house is on the right of the white house.
> The sculptor breeds snails.
> The diplomat lives in the yellow house.
> They drink milk in the middle house.
> The Norwegian lives next door to the blue house.
> The violinist drinks fruit juice.
> The fox is in the house next to the doctor's.
> The horse is in the house next to the diplomat's.
>
> The question is who has the zebra and who drinks water?
>
> Regards,
> Irv
>
> >
> >
>
>
26. Re: Need a Challenge?
Irv,
Of course, technically, you can't validly assert that *any* of the people
mentioned owns a Zebra, or drinks Water, because the puzzle doesn't mention
either in the information, nor does it say:
"One of the pets is a Zebra, and one of the beverages is Water:
The question is who has the zebra and who drinks water?"
Without an explicit statement that the "missing" pet is a Zebra, and that
the "missing" drink is water, that pet could just as well be an Octopus, and
that drink KoolAid, or they could be anything at all. Since they *could* be
*anything*, it can't be valid to say that they *are* a zebra and water.
Just *saying* "who has the Zebra" doesn't seem sufficient, because it hasn't
been *defined* as being one of the pets. No?
(Setting that "technicality aside, I still haven't solved it.)
Dan Moyer
----- Original Message -----
From: "Irv Mullins" <irvm at ellijay.com>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, August 15, 2001 8:47 AM
Subject: Need a Challenge?
> >
> I found this puzzle in an example program for a language I downloaded.
> Can you write a program (100 lines or less, plz) to solve it?
>
> A small street has five differently colored houses on it. Five men
> of different nationalities live in these five houses. Each man has
> a different profession, each man likes a different drink, and each
> has a different pet animal. We have the following information:
>
> The Englishman lives in the red house.
> The Spaniard has a dog.
> The Japanese is a painter.
> The Italian drinks tea.
> The Norwegian lives in the first house on the left.
> The owner of the green house drinks coffee.
> The green house is on the right of the white house.
> The sculptor breeds snails.
> The diplomat lives in the yellow house.
> They drink milk in the middle house.
> The Norwegian lives next door to the blue house.
> The violinist drinks fruit juice.
> The fox is in the house next to the doctor's.
> The horse is in the house next to the diplomat's.
>
> The question is who has the zebra and who drinks water?
>
> Regards,
> Irv
>
> >
> >
>
>
