Courses/CS 460/Fall 2005/Homework/Xuong Tsan/Oct 29
From CSWiki
< Courses | CS 460 | Fall 2005 | Homework | Xuong Tsan
Contents |
[edit] Homework Page
Homework page is: | http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/Homework/Xuong_Tsan
[edit] Feeding Time
Zookeeper George was in charge of feeding all of the animals in the morning. He had a regular schedule that he followed every day. Can you figure it out from the clues?
1. The giraffes were fed before the zebras but after the monkeys.
2. The bears were fed 15 minutes after the monkeys.
3. The lions were fed after the zebras.
% Feeding Time (2nd Solution)
declare
% Every member of Xs has a value from Values.
% Instantiates those that don't.
proc {AllInstantiated Xs Values}
{ForAll Xs proc {$ X} {IsIn X Values} end}
end
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] X Xr in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
% Creates a list of the values for Field in the elements
% of Elts. Assumes Elts is a homgeneous list whose
% members are records with a field named Field.
fun {GetFields Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Returns the first index of X in Xs. X and Xs must be
% instantiated or will suspend until they are.
% Fails if X is not in Xs.
fun {IndexOf X Xs}
fun {IndexOf3 X Xs N}
case Xs of
nil then fail
[] Y | Rest then
if X == Y then N else {IndexOf3 X Rest N+1} end
end
end
in
{IndexOf3 X Xs 1}
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end
%% Constraints
% Generate thread bombs that ensure that all the members
% of List are distinct.
proc {AllDistinct List}
L = {Length List} in
for I in 1; I =< L-1; I+1 do
for J in I+1; J =< L; J+1 do
{NotEqual {Nth List I} {Nth List J}}
end
end
end
% Plant a thread bomb that goes off if X and Y become
% instantiated to the same value.
proc {NotEqual X Y} thread X == Y = false end end
% A thread bomb that ensures that X1 precedes X2 in Xs.
proc {Precedes ?X1 ?X2 Xs}
thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
end
local
Times = ['6:30 AM' '6:45 AM' '7:00 AM' '7:15 AM' '7:30 AM']
proc {Clue1 Elts}
% Giraffes were fed before Zebras but after monkeys
{Precedes Elts.monkeys.time Elts.giraffes.time Times}
{Precedes Elts.monkeys.time Elts.zebras.time Times}
{Precedes Elts.giraffes.time Elts.zebras.time Times}
end
proc {Clue2 Elts}
%The bear were fed 15 minutes after the monkeys
{Precedes Elts.monkeys.time Elts.bears.time Times}
%by implication bears was before giraffes
{Precedes Elts.bears.time Elts.giraffes.time Times}
end
proc {Clue3 Elts}
%The lions were fed after the zebras
{Precedes Elts.zebras.time Elts.lions.time Times}
end
fun {FeedingTime}
Elts = {MakeRecord animals [bears giraffes lions monkeys zebras]}
Ts
Names = {Record.toList Elts}
in
% Create property records for each animal.
{Record.forAll Elts proc {$ S} S = {Record.make properties [time]} end}
% Get the list of time variables.
% Constrain them to be distinct.
Ts = {GetFields time Names}
{AllDistinct Ts}
% Run the clues
{Clue1 Elts}
{Clue2 Elts}
{Clue3 Elts}
% Ensure that every time has a value.
{AllInstantiated Ts Times}
% Return Elts as the answer
Elts
end
in
{Browse {SearchAll FeedingTime}}
end
[edit] Masquerading for the Gentry
Mr. Boddy has invited the lovely (and wealthy) Lady Melon to dine, and now all he has to do is set the stage. It appears that Mr. Boddy has made some very unwise investment decisions and as a result he has had to let his extensive personal staff go. However, after much wheedling and a bit of blackmail, he persuaded five of the six suspects in the game of CLUE to help him out (Col. Mustard could not be reached as he was on Safari in Kenya). Master impersonators, the five suspects - Mr. Green, Miss Scarlet, Mrs. Peacock, Mrs. White, and Prof. Plum, slipped inconspicuously into the roles of butler, chauffeur, cook, downstairs maid, and gardener, with each suspect playing a different role. Each masquerader arrived at the Boddy mansion driving a car of a different color - either blue, green, purple, red, or white, and no suspect drove a car associated with his or her name. Note: Miss Scarlet's name is associated with the color red, Mrs. Peacock with blue, and Prof. Plum with purple.
Can you determine, for each suspect, what color of car he or she drove, and which member of the staff he or she impersonated?
1. Prof. Plum didn't drive the red car.
2. Mr. Green played the part of the cook.
3. Mrs. Peacock, who arrived in the green car, did not masquerade as the gardener.
4. Mrs. White (who didn't drive a purple car) impersonated the chauffeur.
5. The person who arrived in the white car (who wasn't Prof. Plum) played the part of the butler to perfection.
% Masquerading for the Gentry Puzzle (2nd Solution)
declare
% Every member of Xs has a value from Values.
% Instantiates those that don't.
proc {AllInstantiated Xs Values}
{ForAll Xs proc {$ X} {IsIn X Values} end}
end
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] X Xr in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
% Creates a list of the values for Field in the elements
% of Elts. Assumes Elts is a homgeneous list whose
% members are records with a field named Field.
fun {GetFields Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Returns the first index of X in Xs. X and Xs must be
% instantiated or will suspend until they are.
% Fails if X is not in Xs.
fun {IndexOf X Xs}
fun {IndexOf3 X Xs N}
case Xs of
nil then fail
[] Y | Rest then
if X == Y then N else {IndexOf3 X Rest N+1} end
end
end
in
{IndexOf3 X Xs 1}
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end
%% Constraints
% Generate thread bombs that ensure that all the members
% of List are distinct.
proc {AllDistinct List}
L = {Length List} in
for I in 1; I =< L-1; I+1 do
for J in I+1; J =< L; J+1 do
{NotEqual {Nth List I} {Nth List J}}
end
end
end
% Plant a thread bomb that goes off if X and Y become
% instantiated to the same value.
proc {NotEqual X Y} thread X == Y = false end end
% A thread bomb that ensures that X1 precedes X2 in Xs.
proc {Precedes ?X1 ?X2 Xs}
thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
end
local
Colors = [red white blue green purple]
Roles = [cook downstairs_maid chauffeur butler gardener]
proc {Clue1 Elts}
% Prof. Plum didn't dirve the red car
{NotEqual Elts.prof_Plum.car red}
end
proc {Clue2 Elts}
% Mr. Green Played the part of the cook
Elts.mr_Green.impersonated = cook
end
proc {Clue3 Elts}
%Mrs. Peacock drove green car
Elts.mrs_Peacock.car = green
%and not masquerade gardener
{NotEqual Elts.mrs_Peacock.impersonated gardener}
end
proc {Clue4 Elts}
%Mrs. White didn't drive purple car
{NotEqual Elts.mrs_White.car purple}
%Mrs. White impersonated chauffeur
Elts.mrs_White.impersonated = chauffeur
end
proc {Clue5 Elts}
Car
in
%The Person who arrive in the white car wasn't Prof. Plum
{NotEqual Elts.prof_Plum.car white}
%by implication Mrs. Peacock is not butler
{NotEqual Elts.mrs_Peacock.impersonated butler}
%by implication Prof. Plum is not butler
{NotEqual Elts.prof_Plum.impersonated butler}
%Miss Scarlett is butler and dirvie a white car
Elts.miss_Scarlett.car = white
%by elimation Mrs. White dirves red car
Elts.mrs_White.car = red
%by implication Prof. Plum drive blue car
Elts.prof_Plum.car = blue
end
fun {Masquerading}
Elts = {MakeRecord names [mr_Green mrs_Peacock mrs_White miss_Scarlett prof_Plum]}
Cs
Rs
Names = {Record.toList Elts}
in
% Create property records for each person.
{Record.forAll Elts proc {$ S} S = {Record.make properties [car impersonated]} end}
% Get the list of Car's Color and Roles variables.
% Constrain them to be distinct.
Cs = {GetFields car Names}
{AllDistinct Cs}
Rs = {GetFields impersonated Names}
{AllDistinct Rs}
% Run the clues
{Clue1 Elts}
{Clue2 Elts}
{Clue3 Elts}
{Clue4 Elts}
{Clue5 Elts}
% Ensure that every Colors and Roles has a value.
{AllInstantiated Cs Colors}
{AllInstantiated Rs Roles}
% Return Elts as the answer
Elts
end
in
{Browse {SearchAll Masquerading}}
end
This Uses Propagated Utilities
% Masquerading for the Gentry Puzzle (2nd Solution)
declare
% Every member of Xs has a value from Values.
% Instantiates those that don't.
proc {AllInstantiated Xs Values}
{ForAll Xs proc {$ X} {IsIn X Values} end}
end
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] X Xr in
Xs = X | Xr
Zs = X | {Append Xr Ys}
end
end
% Creates a list of the values for Field in the elements
% of Elts. Assumes Elts is a homgeneous list whose
% members are records with a field named Field.
fun {GetFields Field Elts}
{Map Elts fun {$ Elt} Elt.Field end}
end
% Returns the first index of X in Xs. X and Xs must be
% instantiated or will suspend until they are.
% Fails if X is not in Xs.
fun {IndexOf X Xs}
fun {IndexOf3 X Xs N}
case Xs of
nil then fail
[] Y | Rest then
if X == Y then N else {IndexOf3 X Rest N+1} end
end
end
in
{IndexOf3 X Xs 1}
end
proc {IsIn ?X Xs} {Append _ X|_ Xs} end
proc {IsAnElt ?X Elts} {IsIn X {Record.toList Elts}} end
%% Constraints
% Generate thread bombs that ensure that all the members
% of List are distinct.
proc {AllDistinct List}
L = {Length List} in
for I in 1; I =< L-1; I+1 do
for J in I+1; J =< L; J+1 do
{NotEqual {Nth List I} {Nth List J}}
end
end
end
% Plant a thread bomb that goes off if X and Y become
% instantiated to the same value.
proc {NotEqual X Y} thread X == Y = false end end
% A thread bomb that ensures that X1 precedes X2 in Xs.
proc {Precedes ?X1 ?X2 Xs}
thread {IndexOf X1 Xs} < {IndexOf X2 Xs} = true end
end
%% Propagator utilitiess
% If the fields common to R1 and R2 are all instantiated, returns
% true/false depending on whether they are all equal (==).
% Suspends until fields become instantiated.
fun {Match R1 R2}
{Record.all
{Record.zip R1 R2 fun {$ A B} A == B end}
fun {$ X} X == true end}
end
% If {Match Condition R} then {UnifyRecs Result R}.
% Does this in a thread to avoid blocking the main thread.
% Also acts as a constraint in case the unification fails.
proc {Propagate Condition Result R}
thread if {Match Condition R} then {UnifyRecs Result R} end end
end
% Propagates Condition -> Result to all the fields in the record Rec.
% Each field is done in its own thread. See Propagate.
proc {PropagateAll Condition Result Rec}
{Record.forAll Rec proc {$ R} {Propagate Condition Result R} end}
end
% Unifies the values of the fields common to R1 and R2
proc {UnifyRecs R1 R2}
{Record.zip R1 R2 fun {$ A B} A = B end _}
end
local
Colors = [red white blue green purple]
Roles = [cook downstairs_maid chauffeur butler gardener]
proc {Clue1 Elts}
% Prof. Plum didn't dirve the red car
{NotEqual Elts.prof_Plum.car red}
end
proc {Clue2 Elts}
% Mr. Green Played the part of the cook
Elts.mr_Green.impersonated = cook
end
proc {Clue3 Elts}
%Mrs. Peacock drove green car
Elts.mrs_Peacock.car = green
%and not masquerade gardener
{NotEqual Elts.mrs_Peacock.impersonated gardener}
end
proc {Clue4 Elts}
%Mrs. White didn't drive purple car
{NotEqual Elts.mrs_White.car purple}
%Mrs. White impersonated chauffeur
Elts.mrs_White.impersonated = chauffeur
end
proc {Clue5 Elts}
Car
in
%The Person who arrive in the white car wasn't Prof. Plum
{NotEqual Elts.prof_Plum.car white}
%that Person played the part of butler
{PropagateAll properties(car:white) properties(impersonated:butler) Elts}
%by implication Prof. Plum drive blue car
Elts.prof_Plum.car = blue
end
fun {Masquerading}
Elts = {MakeRecord names [mr_Green mrs_Peacock mrs_White miss_Scarlett prof_Plum]}
Cs
Rs
Names = {Record.toList Elts}
in
% Create property records for each person.
{Record.forAll Elts proc {$ S} S = {Record.make properties [car impersonated]} end}
% Get the list of Car's Color and Roles variables.
% Constrain them to be distinct.
Cs = {GetFields car Names}
{AllDistinct Cs}
Rs = {GetFields impersonated Names}
{AllDistinct Rs}
% Run the clues
{Clue1 Elts}
{Clue2 Elts}
{Clue3 Elts}
{Clue4 Elts}
{Clue5 Elts}
% Ensure that every Colors and Roles has a value.
{AllInstantiated Cs Colors}
{AllInstantiated Rs Roles}
% Return Elts as the answer
Elts
end
in
{Browse {SearchAll Masquerading}}
end
