Courses/CS 460/Fall 2005/Homework/Kelly Breed/Oct 29
From CSWiki
Contents |
[edit] HW 5
[edit] Puzzle #1
I thought I had this great idea for this one. After a lot of work it's still not quite right. I get two possible solutions.
Five friends - Arnie, Glen, Jim, Mike, and Thomas grew up together in a small town in the Midwest. They had many things in common, but yet some of their life choices were very different. In high school each participated in a different sport - basketball, football, swimming, track, or wrestling. After high school each spent some time in one of the military forces - Air Force, Army, Coast Guard, Marines, or Navy, and then they all went to college and entered into a different profession - one became an architect, one a dentist, one a marine biologist, one a pilot, and one a veterinarian. From the clues, determine each man’s name and the choices he made in these three different areas of his life.
1. Glen, who joined the Coast Guard, isn’t the man who participated in basketball in high school and then later entered became a commercial airline pilot.
2. Arnie, who is now an architect, participated in track in high school, but isn’t the one who joined the Air Force.
3. One of the five friends became a marine biologist after leaving the Army.
4. Either Jim or Mike is the man who is the man who was a member of their high school’s swimming team and then joined the Navy after graduating.
5. Thomas was on their high school’s wrestling team.
6. The man who enlisted in the Navy after high school isn’t the man who became a veterinarian.
7. Mike didn’t become a dentist after leaving the armed forces.
local
Friend = [arnie glen jim mike thomas]
Sport = [basketball football swimming track wrestling]
Service = [airforce army coastguard marines navy]
Profession = [architect dentist biologist pilot veterinarian]
Props = [sport service profession]
%% Begin the borrowed code %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
proc {Append ?Xs ?Ys ?Zs}
choice
Xs = nil
Ys = Zs
[] Head XRest ZRest in
Xs = Head|XRest
Zs = Head|ZRest
{Append XRest Ys ZRest}
end
end
% 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
% Look at this neat definition for IsAMember/2.
% X is a member of Xs.
proc {IsAMember ?X Xs} {Append _ X|_ Xs} end
%% End the borrowed code %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% IsA... procs
proc {IsASport ?S} {IsAMember S Sport} end
proc {IsAService ?S} {IsAMember S Service} end
proc {IsAProfession ?P} {IsAMember P Profession}end
proc {IsAFriend ?F} {IsAMember F Friend} end
% This creates a list by taking the value of a particular field from each friend. A sort of "vertical" slice.
proc {RecordSliceList RecordsIn Slice ?ListOut}
H T in
RecordsIn = H|T
choice
H=nil fail
[] T = nil ListOut = H.Slice|nil
[] ListOut = H.Slice|{RecordSliceList T Slice}
end
end
% Make a list of the records within the record, then use that
% list to create 'vertical' lists that contains all like properties.
proc {UniqueProperties FRs}
Fr Sp Se Pr in
Fr = {Record.toList FRs}
Sp = {RecordSliceList Fr sport}
{AllDistinct Sp}
Se = {RecordSliceList Fr service}
{AllDistinct Se}
Pr = {RecordSliceList Fr profession}
{AllDistinct Pr}
end
proc {Clue1 FRs}
%1. Glen, who joined the Coast Guard, isn’t the man who participated in basketball
% in high school and then later entered became a commercial airline pilot.
FRs.glen.service = coastguard
thread FRs.glen.sport == basketball = false end
%thread FRs.glen.profession == pilot = false end
FRs.glen.profession = pilot % Correct? Weirdly worded clue.
end
proc {Clue2 FRs}
%2. Arnie, who is now an architect, participated in track in high school,
% but isn’t the one who joined the Air Force.
FRs.arnie.profession = architect
FRs.arnie.sport = track
thread FRs.arnie.service == airforce = false end
end
proc {Clue3 FRs}
%3. One of the five friends became a marine biologist after leaving the Army.
thread if FRs.arnie.profession == biologist then FRs.arnie.service = army end end
thread if FRs.glen.profession == biologist then FRs.glen.service = army end end
thread if FRs.jim.profession == biologist then FRs.jim.service = army end end
thread if FRs.mike.profession == biologist then FRs.mike.service = army end end
thread if FRs.thomas.profession == biologist then FRs.thomas.service = army end end
%thread if FRs.F.service == army then FRs.F.profession = biologist end end
end
proc {Clue4 FRs}
%4. Either Jim or Mike is the man who is the man who was a member of their high school’s
% swimming team and then joined the Navy after graduating.
thread FRs.arnie.sport == swimming = false end
thread FRs.glen.sport == swimming = false end
thread FRs.thomas.sport == swimming = false end
thread FRs.arnie.service == navy = false end
thread FRs.glen.service == navy = false end
thread FRs.thomas.service == navy = false end
thread if FRs.jim.sport == swimming then FRs.jim.service = navy end end
thread if FRs.mike.sport == swimming then FRs.mike.service = navy end end
end
proc {Clue5 FRs}
%5. Thomas was on their high school’s wrestling team.
FRs.thomas.sport = wrestling
end
proc {Clue6 FRs}
%6. The man who enlisted in the Navy after high school isn’t the man who became a veterinarian.
thread if FRs.arnie.service == navy then FRs.arnie.profession == veterinarian=false end end
thread if FRs.glen.service == navy then FRs.glen.profession == veterinarian=false end end
thread if FRs.jim.service == navy then FRs.jim.profession == veterinarian=false end end
thread if FRs.mike.service == navy then FRs.mike.profession == veterinarian=false end end
thread if FRs.thomas.service == navy then FRs.thomas.profession == veterinarian=false end end
%% This doesn't work:
% Frs F in
% Frs = {Record.toList FRs}
% {IsAMember F Frs}
% thread if F.service == navy then F.profession == veterinarian = false end end
%% How I was attempting to do this before, which also doesn't work:
% F in
% {IsAFriend F}
% thread if FRs.F.profession == veterinarian then FRs.F.service == navy=false end end
end
proc {Clue7 FRs}
%7. Mike didn’t become a dentist after leaving the armed forces.
thread FRs.mike.profession == dentist = false end
end
fun {Life}
FRs Sp1 Sp2 Sp3 Sp4 Sp5 Se1 Se2 Se3 Se4 Se5 Pr1 Pr2 Pr3 Pr4 Pr5 in
FRs = {MakeRecord friends Friend}
% Create property records for each friend.
{Record.forAll FRs proc {$ S} S = {MakeRecord properties Props} end}
% Make bindings based on clues
{Clue1 FRs}
{Clue2 FRs}
{Clue3 FRs}
{Clue4 FRs}
{Clue5 FRs}
{Clue6 FRs}
{Clue7 FRs}
% Make sure no two friends have the same sport, service or profession
{UniqueProperties FRs}
% Tedious fill-in of all potential properties
{IsASport Sp1}
FRs.arnie.sport = Sp1
{IsASport Sp2}
FRs.glen.sport = Sp2
{IsASport Sp3}
FRs.jim.sport = Sp3
{IsASport Sp4}
FRs.mike.sport = Sp4
{IsASport Sp5}
FRs.thomas.sport = Sp5
{IsAService Se1}
FRs.arnie.service = Se1
{IsAService Se2}
FRs.glen.service = Se2
{IsAService Se3}
FRs.jim.service = Se3
{IsAService Se4}
FRs.mike.service = Se4
{IsAService Se5}
FRs.thomas.service = Se5
{IsAProfession Pr1}
FRs.arnie.profession = Pr1
{IsAProfession Pr2}
FRs.glen.profession = Pr2
{IsAProfession Pr3}
FRs.jim.profession = Pr3
{IsAProfession Pr4}
FRs.mike.profession = Pr4
{IsAProfession Pr5}
FRs.thomas.profession = Pr5
FRs
end
in
{Browse {SearchAll Life}}
end
[edit] Puzzle #2
Done using the code from the Five Sisters example in order to increase my understanding.
One Saturday afternoon, five High School friends and their dates went on a picnic to the park. Each couple offered to provide one food item (buns, condiments, hot dogs, marshmallows, and pop and ice) and one other item (frisbees, insect repellent, paper plates and napkins, sun screen, and table cloth for the picnic. From the clues, determine the first name of each young man (one is Fabian), the name of his date, the food item each couple supplied, and the second picnic item each couple supplied.
1. Two couples were Ilene and Brad and Angie and Hugh.
2. Cherry and her date (who was not John) provided the paper plates and napkins, while another couple provided the pop and ice.
3. One couple provided hot dogs and a table cloth of the outing, while another couple provided the sun screen and condiments.
4. Ginger and her date arrived at the picnic site with a large bag of marshmallows and some long sticks for roasting them on.
5. Ilene and her date brought along a couple of frisbees to toss around later after they had all eaten.
6. Erica and her date are not the couple who provided the hot dogs.
7. Everyone was relieved when David and his date showed up with the insect repellent as flies and gnats had already started gathering around the picnickers.
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
Name = [angie cherry erica ginger ilene]
Date = [brad david fabian hugh john]
Food = [buns condiments hotdogs marshmallows pop]
PicnicItem = [frisbees repellent plates sunscreen tablecloth]
proc {Clue1 Elts}
Elts.ilene.date = brad
Elts.angie.date = hugh
end
proc {Clue2 Elts}
{NotEqual Elts.cherry.date john}
Elts.cherry.picnicitem = plates
{NotEqual Elts.cherry.food pop}
end
proc {Clue3 Elts}
{PropagateAll a(food:hotdogs) b(picnicitem:tablecloth) Elts}
{PropagateAll a(food:condiments) b(picnicitem:sunscreen) Elts}
end
proc {Clue4 Elts}
Elts.ginger.food = marshmallows
end
proc {Clue5 Elts}
Elts.ilene.picnicitem = frisbees
end
proc {Clue6 Elts}
{NotEqual Elts.erica.food hotdogs}
end
proc {Clue7 Elts}
{PropagateAll a(date:david) b(picnicitem:repellent) Elts}
end
fun {FiveSisters}
Elts = {MakeRecord couples Name}
Ds
Fs
Ps
Ns = {Record.toList Elts}
in
% Create property records for each sister.
{Record.forAll Elts proc {$ S} S = {Record.make properties [date food picnicitem]} end}
% Get the list of Month and Day variables.
% Constrain them to be distinct.
Ds = {GetFields date Ns}
{AllDistinct Ds}
Fs = {GetFields food Ns}
{AllDistinct Fs}
Ps = {GetFields picnicitem Ns}
{AllDistinct Ps}
% Run the clues
{Clue1 Elts}
{Clue2 Elts}
{Clue3 Elts}
{Clue4 Elts}
{Clue5 Elts}
{Clue6 Elts}
{Clue7 Elts}
% Ensure that every day and month has a value.
{AllInstantiated Ds Date}
{AllInstantiated Fs Food}
{AllInstantiated Ps PicnicItem}
% Return Elts as the answer
Elts
end
in
{Browse {SearchAll FiveSisters}}
end
